【总结】数据结构-队列

队列即先进先出（FIFO）的线性表。怎么来比喻队列呢？相当于有一排座位，只能依次从右边入座，从左边离开。入座的时候，第一个人坐最左边，第二个人坐左边的第二个位置，依次类推；出场的时候，最左边的人先走。

 

1. 循环（顺序）队列

       普通顺序队列有一个问题，假如中场的时候，最左边走了几个人，那么此时最左边的人，坐的却不是最左边的座位，因为最左边的人走后，头指针就移动到了此时最左边的人身上（而人无需移动），所以那些空位置就再也用不上了，造成了“假上溢”。所以普通顺序队列没意思，循环队列才可行。

       注意：自始至终，这些座位都是编好号的，从左到右依次为0,1,2,…类似于数组，座位的总个数即MAXSIZE，但是只能坐MAXSIZE-1个人，队头和队尾之间要留一个空位，即sq->rear+1=MAXSIZE时就意味着坐满了。

       循环队列的关键算法是，判断队尾是否还有空座，如果没有了，就再看看最左边是否有人离开而腾出来的空座位，如果左边头上有人，证明头尾都坐满了人，如果左边有空位，说明已经有人离开了，后来的人就直接坐到左边去。即：

if( sq->rear+1>= MAXSIZE )

       sq->rear=0; //坐不下了，转到队头去，看看队头有没有人。

else

       sq->rear++; //坐得下，直接坐到后面

将上面两句改成如下形式：

sq->rear =(sq->rear+1)%MAXSIZE;

       二者等价。实际上，sq->rear+1不会大于MAXSIZE，最多等于MAXSIZE，所以说上面那个if正确的写法应该是if( sq->rear+1==MAXSIZE )，如果sq->rear+1= MAXSIZE，则sq->rear就等于0，否则sq->rear=余数= sq->rear+1，所以说if else和求模运算是等价的。

 

循环队列的数据结构如下

typedef struct

{

       DataType data[QueueSize];

       int front;//头指针

       int rear;//尾指针    

}CirQueue;  

 

其他操作如下：

// 置队列空

void Initial(CirQueue *Q)

{

       Q->front=Q->rear=QueueSize-1;//注意这个绝对不能写作-1等，写成0也可以

}

 

// 判队列空

int IsEmpty(CirQueue *Q)

{

       return Q->front==Q->rear;

}

 

//判队列满

int IsFull(CirQueue *Q)

{

       return (Q->rear+1)%QueueSize==Q->front;//这句很多地方都要用到

}

 

//入队

void EnQueue(CirQueue *Q,DataType x)

{

       /*关键算法：新元素存入队尾，队尾再后移一位*/

       Q->data[Q->rear]=x;                 //新元素插入队尾

       Q->rear=(Q->rear+1)%QueueSize;      //循环意义下将尾指针加1

}

 

//出队

void DeQueue(CirQueue *Q)

{

       /*关键算法：最左边的人走后，就将队头front往右移一位（即循环意义下+1）*/

       Q->front=(Q->front+1)%QueueSize;   //循环意义下的头指针加1

}

 

2. 链队列

数据结构如下：

typedef struct node{

       DataType data;

       struct node *next;

}LinkQueue;

typedef struct{

       LinkQueue *front;  //头指针

       LinkQueue *rear;

}QueueNode;

同样（见上一篇文章"栈"），关于QueueNode我们也可以用数组LinkQueue *QueueNode[2]来实现。

 

基本操作

// 置队列空

void Initial(QueueNode *Q)

{

    Q->front=Q->rear=NULL;

}

//判队列空

int IsEmpty(QueueNode *Q)

{

    return Q->front==NULL&&Q->rear==NULL;

}

//进队列

void Push(QueueNode *Q,DataType x)

{//将元素x插入链队列尾部

       LinkQueue *p=(LinkQueue *)malloc(sizeof(LinkQueue));//申请新结点

       p->data=x;

       p->next=NULL;

    if(IsEmpty(Q))

              Q->front=Q->rear=p;  //将x插入空队列

       else

       {

              Q->rear->next=p; //(Q->rear)是队尾的指针，即：使队尾结构体的next指针指向p

              Q->rear=p;     //队尾指针指向新的尾

       }

}

//出队列

DataType Pop(QueueNode *Q)

{

       LinkQueue *p;

       p=Q->front;                   //保存队头结点

       Q->front=p->next;             //使队头指向p后面的一位

    if(Q->rear==p)//原队中只有一个结点的情况，删去后队列变空，所以尾指针也应置空

              Q->rear=NULL;

       free(p);   //释放被删队头结点

}

 

注意上面列出的只是算法的关键部分，并不完整，删减了一些无碍算法逻辑的内容。