数据结构——顺序队列

1.队列特点

1 .栈：（First in last out)
2.队列：（First in first out)

队列可以在表的两端进行操作。栈只能在栈顶进行插入和删除。

两端允许操作的类型不一样：可以进行删除的一端称为队头，这种操作也叫出队；

可以进行插入的一端称为队尾，这种操作也叫入队。总的来说，队头只能出队，队尾只能入队

队列也是一种特殊的线性表；所以队列的实现也有两种形式，一种是数组实现队列，一种是用链表实现队列。
数组形式又分为顺序对列和循环队列

2.顺序队列功能实现

0.顺序队列类的定义

//队列的顺序存储 #include<iostream>usingnamespace std;typedefint Elemtype;#defineMAX_SIZE25classqueue{private:int head;int rear;
    Elemtype *data;public://1.队列的无参构造函数 queue();//2.队列的有参构造函数 queue(int size);//3.队列的析构函数 ~queue();//4.入队操作 voidpush(Elemtype t);//5.出队操作
    Elemtype pop();//6.判断队列是否为空 boolisEmpty();//7.判断队列是否满了boolisFull();//8.返回队尾元素
    Elemtype GetRear();//9.返回队头元素
    Elemtype GetHead();//10.清空队列voidClear();//11.打印队列voidPrintQueue();};

1.队列的无参构造函数

//1.队列的无参构造函数 
queue::queue(){
    head=-1;
    rear=-1;
    data=new Elemtype[MAX_SIZE];}

2.队列的有参构造函数

//2.队列的有参构造函数
queue::queue(int size){
    head=-1;
    rear=-1;if(size>MAX_SIZE)
        data=new Elemtype[MAX_SIZE];else
        data=new Elemtype[size];}

3.队列的析构函数

//3.队列的析构函数queue::~queue(){delete[]data;}

4.入队操作

//4.入队操作 void queue::push(Elemtype t){if(!isFull()){
        data[++rear]=t;}else{
        cout<<"队列已满"<<endl;return;}if(rear==0)
        head=0;}

5.出队操作

//5.出队操作
Elemtype queue::pop(){if(!isEmpty())return data[head++];}

6.判断队列是否为空

//6.判断队列是否为空 bool queue::isEmpty(){bool flag = head > rear;//当head和tail不为-1时if(head ==-1&& rear ==-1)//当head=tail=-1时{
        flag =true;}if(flag){
        head = rear =-1;}return flag;}

7.判断队列是否满了

//7.判断队列是否满了bool queue::isFull(){return rear==MAX_SIZE-1;}

8.返回队尾元素

//8.返回队尾元素
Elemtype queue::GetRear(){if(!isEmpty()){return data[rear];}return0;}

9.返回队头元素

//9.返回队头元素
Elemtype queue::GetHead(){if(!isEmpty()){return data[head];}return0;}

10.清空队列

//10.清空队列void queue::Clear(){
    head=-1;
    rear=-1;}

11.打印队列

//11.打印队列void queue::PrintQueue(){if(!isEmpty()){for(int i=head;i<=rear;i++){
            cout<<data[i]<<" ";}
        cout<<endl;}}

12.测试案例

//12.测试案例voidtest01(){
    queue Queue;
    Queue.push(56);
    Queue.push(59);
    Queue.push(98);
    Queue.push(15);
    Queue.push(46);
    Queue.push(78);
    cout<<"队头元素为："<<Queue.GetHead()<<endl;
    cout<<"队尾元素为："<<Queue.GetRear()<<endl;
    cout<<"打印队列元素："; 
    Queue.PrintQueue();
    cout<<"弹出元素："<<Queue.pop()<<endl;
    cout<<"打印队列元素："; 
    Queue.PrintQueue();}

3.顺序队列总源码

//队列的顺序存储 #include<iostream>usingnamespace std;typedefint Elemtype;#defineMAX_SIZE25classqueue{private:int head;int rear;
    Elemtype *data;public://1.队列的无参构造函数 queue();//2.队列的有参构造函数 queue(int size);//3.队列的析构函数 ~queue();//4.入队操作 voidpush(Elemtype t);//5.出队操作
    Elemtype pop();//6.判断队列是否为空 boolisEmpty();//7.判断队列是否满了boolisFull();//8.返回队尾元素
    Elemtype GetRear();//9.返回队头元素
    Elemtype GetHead();//10.清空队列voidClear();//11.打印队列voidPrintQueue();};//1.队列的无参构造函数 
queue::queue(){
    head=-1;
    rear=-1;
    data=new Elemtype[MAX_SIZE];}//2.队列的有参构造函数
queue::queue(int size){
    head=-1;
    rear=-1;if(size>MAX_SIZE)
        data=new Elemtype[MAX_SIZE];else
        data=new Elemtype[size];}//3.队列的析构函数queue::~queue(){delete[]data;}//4.入队操作 void queue::push(Elemtype t){if(!isFull()){
        data[++rear]=t;}else{
        cout<<"队列已满"<<endl;return;}if(rear==0)
        head=0;}//5.出队操作
Elemtype queue::pop(){if(!isEmpty())return data[head++];}//6.判断队列是否为空 bool queue::isEmpty(){bool flag = head > rear;//当head和tail不为-1时if(head ==-1&& rear ==-1)//当head=tail=-1时{
        flag =true;}if(flag){
        head = rear =-1;}return flag;}//7.判断队列是否满了bool queue::isFull(){return rear==MAX_SIZE-1;}//8.返回队尾元素
Elemtype queue::GetRear(){if(!isEmpty()){return data[rear];}return0;}//9.返回队头元素
Elemtype queue::GetHead(){if(!isEmpty()){return data[head];}return0;}//10.清空队列void queue::Clear(){
    head=-1;
    rear=-1;}//11.打印队列void queue::PrintQueue(){if(!isEmpty()){for(int i=head;i<=rear;i++){
            cout<<data[i]<<" ";}
        cout<<endl;}}//12.测试案例voidtest01(){
    queue Queue;
    Queue.push(56);
    Queue.push(59);
    Queue.push(98);
    Queue.push(15);
    Queue.push(46);
    Queue.push(78);
    cout<<"队头元素为："<<Queue.GetHead()<<endl;
    cout<<"队尾元素为："<<Queue.GetRear()<<endl;
    cout<<"打印队列元素："; 
    Queue.PrintQueue();
    cout<<"弹出元素："<<Queue.pop()<<endl;
    cout<<"打印队列元素："; 
    Queue.PrintQueue();}intmain(){test01();}

测试结果