队列

前面说到过栈和队列都是逻辑结构的一种

那么什么是队列呢?

队列就是两端都开口,数据只能一端进,一端出

所以队列遵循的规律正好和栈相反

栈是先进后出,而队列是先进先出

不要忘记了队列也是一种线性存储结构

所以它同样有两种实现方式


顺序队

一般的顺序队底层使用的是数组

除此之外我们还需要两个指针top和rear分别指向队头和队尾

一开始两个指针都指向0

进队rear+1,出队top+1

但是这样做有个问题

在不断的进队出队的过程中顺序表会不断后移

之前的空间就用不了了

所以我们直接使用环形队列来实现

判断队满的条件改变为(rear+1)%队列上限 == front

这样队列指针就可以继续向下移动并且指向之前经过的位置

#include<iostream>
#define Maxsize 6 
typedef char Elemtype;
using namespace std;

class SqQueue{
    public:
        SqQueue();
        void enter(Elemtype e);
        void out();
        void ifempty();
        void deletedata();
        
    private:
        Elemtype data[Maxsize];
        int front;//队头指针 
        int rear;//队尾指针 
};//在这里实际上只是代指下标
//如果按照书上写的引用那应该确实是指针 

SqQueue::SqQueue(){
    front = 0;
    rear = 0;
} 

void SqQueue::enter(Elemtype e){
    if((rear+1)%Maxsize == front){
        cout<<"队列溢出了"<<endl;
    }else{
        rear=(rear+1)%Maxsize;
        data[rear]=e;
    }
}//进队列

void SqQueue::out(){
    if(front == rear){
        cout<<"队列中没有元素"<<endl;
    }else{
        front=(front+1)%Maxsize;
        cout<<data[front]<<" ";
    }
}//出队列

void SqQueue::ifempty(){
    if(front == rear){
        cout<<"队列中没有元素"<<endl;
    }else{
        cout<<"队列中有元素"<<endl;
    }
}//判断是否为空

void SqQueue::deletedata(){
    
} 

int main(){
    SqQueue s;
    s.enter('a');
    s.enter('b');
    s.enter('c');
    s.out();
    s.enter('d');
    s.enter('e');
    s.enter('f');
    s.out();
    s.out();
    s.out();
    s.out();
    s.out();
    
    return 0;
}

栈队

基本和顺序队实现一样

只不过底层不用数组空间是实时分配的

其它没有太大区别

#include<iostream>
#define Maxsize 6
typedef char Elemtype;
using namespace std;

struct qNode{
    Elemtype data;
    qNode *next;
};//单链表里的最小结点

class LinkQnode{
    public:
        LinkQnode();
        void enter(Elemtype e);
        void out();
        void ifempty();
        void deletedata();
        
    private:
        qNode *front;
        qNode *rear;
};

LinkQnode::LinkQnode(){
    front = NULL;
    rear = NULL;
}//初始化指针 

void LinkQnode::enter(Elemtype e){
    qNode *p;
    p = new qNode;
    p->data = e;
    p->next = NULL;
    if(rear == NULL){
        front = rear = p;//如果队列为空,新节点既是队首也是队末 
    }else{
        rear->next = p;
        rear = p;//如果不为空让p去队尾,rear指向它 
    }
}//进队列 

void LinkQnode::out(){
    qNode *t;
    if(rear == NULL){
        cout<<"队列为空"<<endl;
    }
    t = front;
    if(front == rear){
        front = rear = NULL;//只有一个数据节点时 
    }else{
        front = front->next;//有两个及两个结点以上时 
    }
    cout<<t->data<<" ";
}//出队列 

void LinkQnode::ifempty(){
    if(rear == NULL){
        cout<<"队列为空"<<endl;
    }else{
        cout<<"队列不为空"<<endl;
    }
}

void LinkQnode::deletedata(){
    
}

int main(){
    LinkQnode l;
    l.enter('a');
    l.enter('b');
    l.enter('c');
    l.out();
    l.enter('d');
    l.enter('e');
    l.enter('f');
    l.out();
    l.out();
    l.out();
    l.out();
    l.out();
    return 0;
}

发表评论

您的电子邮箱地址不会被公开。