数据结构基础-队列（循环队列、链式队列）以及STL中queue的使用

对于队列（Queue）是什么，再次不再赘述，与链表、栈的实现一样，队列作为一种特殊的线性表，也存在顺序存储以及链式存储两种方式。

顺序存储的队列

采用顺序存储的方式来存储队列，最简单的方式是对于n个元素的队列，开辟一个n大小的数组，入队操作即是在数组的尾部直接添加元素，出队操作即将0方向的元素移除，并将所有的后边元素全部前移一个，这与顺序表操作是一致的，但是自然会很麻烦，因此，又出现了另一种方式，在“移除”队首的元素之后，不进行前移操作，这样出队操作是简化了，但是又引发了另一个问题，也就是如果不断的进行出队操作，那么队列首与队列尾都指向了队列中较为靠后的一部分，那么队列前边的空间就浪费了，如果首尾指针重合了，虽然实际上空间是有的，但是也无法操作了，这被称作假溢出，而解决的方式就是采用循环队列的形式。

循环队列的基本操作：

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;

#define OK 1
#define ERROR -1
#define Status
#define MAXSIZE 100
typedef int QElemType;

typedef struct{
  QElemType data[MAXSIZE];
  int front;
  int rear;
}SqQueue;

Status InitQueue(SqQueue &Q){
  Q.front = 0;
  Q.rear = 0;
  return OK;
}
Status Length(SqQueue Q){
  return (Q.rear+MAXSIZE-Q.front)%MAXSIZE;        //注意不要忘了加MAXSIZE，因为循环队列有的时候rear会在front的前面（重用了前面的空闲空间）
}
Status EnQueue(SqQueue &Q, int n){
    if((Q.rear+1)==Q.front)
        return ERROR;
    Q.data[Q.rear] = n;
    Q.rear = (Q.rear+1)%MAXSIZE;                 //无论是入队，还是出队操作，都要对MAXSIZE取模，以便于重用空闲的空间，
    return OK;                                   //其实循环队列的最重要的方法就是通过对MAXSIZE的取模实现了“循环”
}
Status DeQueue(SqQueue &Q, int &e){
  if(Q.front == Q.rear)
    return ERROR;
  e = Q.data[Q.front];
  Q.front = (Q.front+1)%MAXSIZE;
  return OK;

}
int main(){
  SqQueue Q;
  InitQueue(Q);
  int n;
  cout<<"Enter n:"<<endl;
  cin>>n;
  QElemType temp;
  for(int i = 0; i<n; i++){
    cin>>temp;
    EnQueue(Q, temp);
  }
  for(int i=0; i<n; i++){
    DeQueue(Q, temp);
    cout<<temp<<" ";
  }
  cout<<endl;
  return 0;
}

队列的链式存储结构

队列的另一种实现方式，链式实现，说白了就是单链表，只不过是加了条件只能在末尾添加，在开头插入罢了，在这里仍然需要两个指针，队头指针指向头结点，队尾指针指向末尾的结点，这样，空队列的情况就是 front 与 rear 都指向头节点。

链式队列的基本操作：

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
#define ERROR -1
#define OK 1
#define Status
typedef int QElemType;

typedef struct qnode{
  QElemType data;
  struct qnode *next;
}QNode, *QueuePtr;
typedef struct {
  QueuePtr front,rear;
}LinkQueue;

Status InitQueue(LinkQueue &Q){
  QueuePtr q = (QueuePtr)malloc(sizeof(QNode));
  Q.front = q;
  Q.rear = q;
  return OK;
}
Status EnQueue(LinkQueue &Q, QElemType n){
  QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
  if(!p)
    return ERROR;                //内存分配失败
  else{
    p->data = n;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear=p;
    return OK;
  }
}
Status DeQueue(LinkQueue &Q, QElemType &e){
  if(Q.front==Q.rear)              //fornt,rear都指向头节点，队列为空
    return ERROR;
  else{
    QueuePtr p =Q.front->next;
    e=p->data;
    Q.front->next = p->next;
    if(p==Q.rear)
      Q.rear=Q.front;
      return OK;
  }
}

int main(){
  LinkQueue Q;
  InitQueue(Q);
  int N;
  cout<<"Enter n:"<<endl;
  cin>>N;
  QElemType temp;
  for(int i=0; i<N; i++){
    cin>>temp;
    EnQueue(Q, temp);
  }
  cout<<"DeQueue:"<<endl;
  for(int i=0; i<N; i++){
    DeQueue(Q, temp);
    cout<<temp<<" ";
  }
}

队列的两种实现方式各有优点吧，使用的时候根据情况具体使用，而在C++中的STL库中，已经为我们封装好了队列这一数据结构，我们可以直接通过引用queue头文件来使用：
queue模板类的基本操作

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;

int main(){
  //定义的结构为 queue <Element Type>
  //例如string 类型的队列： queue<string> s 等等
  queue<int> q;
  int n;
  cin>>n;   //输入n个数字
  int temp;
  for(int i=0; i<n; i++){
    cin>>temp;
    q.push(temp);                     //入队操作  .push()方法
  }
  cout<<q.size()<<endl;              //队列的大小
  if(!q.empty())
    cout<<"Not Empty."<<endl;        //判断队列是否为空 .empty()
  cout<<"Front "<<q.front()<<" Rear "<<q.back()<<endl;  //访问队首队尾元素
  for(int i=0; i<n; i++){
    cout<<q.front()<<" ";            //出队操作，这里使用的是pop，凑合着理解吧。。
    q.pop();                         //但是要注意并不会返回值
  }
  cout<<endl;
}