数据结构系列－队列的基本操作-蒲公英云

队列(Queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。允许插入的端是队尾，允许删除的端是队头。

所以说队列是一个先进先出的线性表，相应的也有顺序存储和链式存储两种方式。

顺序存储就是用数组实现，比如有一个ｎ个元素的队列，数组下标0的一端是队头，入队操作就是通过数组下标一个个顺序追加，不需要移动元素，但是如果删除队头元素，后面的元素就要往前移动，对应的时间复杂度就是O(n)，性能自然不高。

为了提高出队的性能，就有了循环队列，什么是循环队列呢？就是有两个指针，front指向队头，rear指向对尾元素的下一个位置，元素出队时front往后移动，如果到了对尾则转到头部，同理入队时rear后移，如果到了对尾则转到头部，这样通过下标front出队时，就不需要移动元素了。

![Image 1][]

同时规定，当队列为空时，front和rear相等，那么队列什么时候判断为满呢？按照循环操作rear依次后移，然后再从头开始，也是出现rear和front相等时，队列满。这样跟队列空的情况就相同了，为了区分这种情况，规定数组还有一个空闲单元时，就表示队列已满，因为rear 可能在front后面，也可能循环到front前面，所以队列满的条件就变成了(rear+1)%maxsize = front ,同时队列元素个数的计算就是(rear -front+maxsize)%maxsize。

如下是循环队列的数据结构及基本操作实现：

#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 11 //初始容量
typedef int Status;
typedef int QElemType;//定义数据类型
//循环队列的顺序存储结构
typedef struct{
    QElemType data[MAXSIZE];
    int front; //头指针
    int rear;//尾指针，队列非空时，指向队尾元素的下一个位置
}SqQueue;
Status visit(QElemType item){
    printf("%d",item);
    return OK;
}
//初始化空队列
Status InitQueue(SqQueue *sQ){
    sQ->front =0;
    sQ->rear =0;
    return OK;
}
//将队列清空
Status ClearQueue(SqQueue *Q){
    Q->front = Q->rear =0;
    return OK;
}
//判断队列是否为null
Status QueueEmpty(SqQueue Q){
    if(Q.front == Q.rear)
        return TRUE;
    else
        return FALSE;
}
//返回队列中的元素个数
int QueueLength(SqQueue Q){
    return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}
//返回队头元素
Status GetHead(SqQueue Q, QElemType *e){
    if(Q.front == Q.rear)//是否为空队列
        return ERROR;
    *e = Q.data[Q.front];
    return OK;
}
//在队尾插入元素
Status EnQueue(SqQueue *Q, QElemType e){
    if((Q->rear+1)%MAXSIZE == Q->front)//队列已满
        return ERROR;
    Q->data[Q->rear] =e;//插入队尾
    Q->rear = (Q->rear +1)%MAXSIZE;//尾部指针后移，如果到最后则转到头部
    return OK;
}
//元素出队
Status DeQueue(SqQueue *Q, QElemType *e){
    if(Q->front == Q->rear)//队列空
        return ERROR;
    *e = Q->data[Q->front];//返回队头元素
    Q->front = (Q->front+1)%MAXSIZE;//队头指针后移，如到最后转到头部
    return OK;
}
//遍历队列元素
Status QueueTraverse(SqQueue Q){
    int i = Q.front;
    while((i+Q.front) != Q.rear){
        visit(Q.data[i]);
        i=(i+1)%MAXSIZE;
    }
    printf("\n");
    return OK;
}
int main(){
    Status j;
    int i=0,l;
    QElemType d;
    SqQueue Q;
    InitQueue(&Q);
    //入队１０个元素
    for(int i =0;i< MAXSIZE-1; i++){
        EnQueue(&Q,i);
    }
    QueueTraverse(Q);
    printf("依次出队:");
    for(l=1;l<=MAXSIZE;l++)
    {
        DeQueue(&Q,&d);
        printf("d= %d,",d);
    }
    return 0;    
}

循环队列要事先申请好空间，整个过程都不能释放，而且要有固定的长度，如果长度事先无法估计，这种方式显然不够灵活；所以就引入了链式存储队列，其实就是线性表的单链表，只是它只能对尾进，队头出。并且规定队头指针指向链队列的头结点，对尾指针指向终端节点，当队列为空时，front和rear都指向头结点。

入队操作，就是在链表尾部插入结点；出队操作就是头结点的后继结点出队，然后将头结点的后继后移。如果最后除了头结点外，只剩一个元素了，就把rear也指向头结点。

![Image 1][]

数据结构及基本操作：

#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 
typedef int Status; 
typedef int QElemType; 
//结点结构
typedef struct QNode{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;
//队列的链表结构
typedef struct{
    QueuePtr front;//队头
    QueuePtr rear;//对尾
}LinkQueue;
Status visit(QElemType e)
{
    printf("%d ",e);
    return OK;
}
//初始化空的队列
Status InitQueue(LinkQueue *Q){
    Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q->front)
        exit(OVERFLOW);
    Q->front->next =NULL;
    return OK;
}
//销毁队列
Status DestroyQueue(LinkQueue *Q){
    while(Q->front){
        Q->rear=Q->front->next;//从队头开始销毁
        free(Q->front);
        Q->front = Q->rear;
    }
    return OK;
}
//清空队列，队头指针还在
Status ClearQueue(LinkQueue *Q){
    QueuePtr p,q;
    Q->rear =Q->front;//跟初始状态相同，Q->rear指向头结点
    p=Q->front->next;//开始销毁队头元素，队头，对尾依然保留
    Q->front->next =NULL;
    while(p){
        q=p;
        p=p->next;
        free(q);
    }    
    return OK;
}
//队列是否空
Status QueueEmpty(LinkQueue Q){
    if(Q.front == Q.rear)
        return TRUE;
    else
        return FALSE;
}
//取队列长度
int QueueLength(LinkQueue Q){
    int i=0;
    QueuePtr p = Q.front;
    while(Q.rear != p){
        i++;
        p = p->next;
    }
    return i;
}
//获取队头元素
Status GetHead(LinkQueue Q,QElemType *e){
    QueuePtr p;
    if(Q.front == Q.rear)//队空
        return ERROR;
    p=Q.front->next;
    *e = p->data;
    return OK;
}
//对尾插入元素
Status EnQueue(LinkQueue *Q,QElemType e){
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    if(!s)
        exit(OVERFLOW);
    s->data = e;
    s->next =NULL;
    Q->rear->next =s;//原来对尾的next指向新的元素
    Q->rear =s;//将新元素变为对尾
    return OK;
}
//队头元素出队
Status DeQueue(LinkQueue *Q,QElemType *e){
    QueuePtr p;
    if(Q->front == Q->rear)
        return ERROR;
    p=Q->front->next;//ｐ指向队头元素
    *e = p->data;
    Q->front->next = p->next;//头结点的后继指向队头的下一个元素
    if(Q->rear == p){//队头等于对尾了
        Q->rear = Q->front;//对尾指向头结点
    }    
    free(p);
    return OK;
}
//遍历元素
Status QueueTraverse(LinkQueue Q){
    QueuePtr p;
    p=Q.front->next;
    while(p){
        visit(p->data);
        p=p->next;
    }
    printf("\n");
    return OK;
}
int main(){
    int i;
    QElemType d;
    LinkQueue q;
    i=InitQueue(&q);
    //入队１０个元素
    for(int index=0;index<MAXSIZE;index++){
        EnQueue(&q,index);
    }
    QueueTraverse(q);
    DestroyQueue(&q);
    printf("队列已经销毁,q.front=%p q.rear=%p\n",q.front, q.rear);
    return 0;
}