1 基本概念

队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。

2 抽象数据类型（ADT）

数据对象：{a1,a2,.....,an}，每个元素类型为DataType，与线性表类似。

数据关系：除第一个元素外，每一个元素有且只有一个直接前驱元素；除最后一个元素外，每个元素有且只有一个直接后驱。一对一  的对应关系。在队列中，允许插入的一端叫做队尾，允许删除的一端则称为队头。

基本操作：

                 InitQueue(*Q): 初始化队列。

                 DestroyQueue(*Q): 若队列存在，则销毁它。

                 ClearQueue(*Q): 清空队列。

                 QueueEmpty(*Q): 若队列为空，返回True，否则返回False。

                 GetHead(Q,*e): 若队列存在且非空，则返回队列Q的队头元素。

                 EnQueue(*Q,e): 若队列存在，插入元素e。

                 DeQueue(*Q,*e): 删除队头元素，并返回值给e。

                 QueueLength(Q): 返回队列元素个数

3 链队列

用链表表示的队列，需要头指针和尾指针。

#define ERROR 0 #define OK 1 #define TRUE 1 #define FALSE 0 #include <stdlib.h> #include <stdio.h> //链队列存储结构定义 typedef int ElemType; //元素的数据类型根据实际情况而定，这里假设为int typedef struct Node { ElemType data; //数据域，用于存储结点数据 struct Node *next; //指针域，存储下一个结点的地址信息 }QNode,*Queueptr; typedef struct { Queueptr front,rear; //定义头指针和尾指针 }LinkQueue; int InitQueue(LinkQueue*Q) //建立队列 { Q->front=(QNode*)malloc(sizeof(QNode)); //建立头结点 if (!Q->front) return ERROR; Q->front->next=NULL; Q->rear=Q->front; //头尾指针同时指向头结点，队列为空 return OK; } int DestroyQueue(LinkQueue*Q) //摧毁队列 { if (!Q->front) return ERROR; while(Q->front) //从头结点开始依次释放结点空间 { Q->rear=Q->front->next; free(Q->front); Q->front=Q->rear; } return OK; } int ClearQueue(LinkQueue*Q) //清空队列 { Q->front->next=NULL; //使头结点指向空 Q->front=Q->rear; //使头指针和尾指针同时指向头结点 return OK; } int QueueEmpty(LinkQueue*Q) //验证队列是否为空 { if (Q->front==Q->rear) return TRUE; return FALSE; } int GetHead(LinkQueue Q,ElemType*e) //得到队头元素 { if (Q.front==Q.rear) return ERROR; *e=Q.front->next->data; return OK; } int EnQueue(LinkQueue*Q,ElemType e) //插入元素e队列 { QNode*p; if (!Q->front) return ERROR; p=(QNode*)malloc(sizeof(QNode)); p->data=e; p->next=NULL; //使新节点next指针指向空 Q->rear->next=p; //使前一结点指向新节点 Q->rear=p; //使尾指针指向新节点 } int DeQueue(LinkQueue*Q,ElemType*e) //删除队头元素，返回值给e { QNode*p; if (!Q->front) 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; } int QueueLength(LinkQueue Q) //返回队列长度 { QNode*p; int num=0; if (!Q.front) return ERROR; p=Q.front->next; while(p) //遍历 { p=p->next; num++; } return num; } int main() { LinkQueue Q; QNode*p; int e,choice; do{ e=0; printf("输入操作: 0.退出 1.返回队列长度 2.插入 3.删除 4.获取队列头元素值 5.清空队列 6.创建队列 7.销毁队列 8.验证队列是否为空\n"); scanf("%d",&choice); switch (choice) { case 1: { e=QueueLength(Q); printf("%d\n",e); break; } case 2: { printf("输入插入元素值\n"); scanf("%d",&e); EnQueue(&Q,e); break; } case 3: { DeQueue(&Q,&e); printf("%d\n",e); break; } case 4: { GetHead(Q,&e); printf("%d\n",e); break; } case 5: { ClearQueue(&Q); break; } case 6: { InitQueue(&Q); break; } case 7: { DestroyQueue(&Q); break; } case 8: { printf("%d\n",QueueEmpty(&Q)); break; } } printf("["); p=Q.front->next; while (p) { printf("%d ",p->data); p=p->next; } printf("]\n"); }while(choice!=0); return 0; }

4 循环队列

头尾相接的顺序存储队列结构，需要头指针和尾指针。

#define ERROR 0 #define OK 1 #define TRUE 1 #define FALSE 0 #include <stdlib.h> #include <stdio.h> //队列的顺序存储结构定义 #define MAXSIZE 10 typedef int ElemType; //元素的数据类型根据实际情况而定，这里假设为int typedef struct { ElemType * base; //基地址 int front; //头指针，指向第一个元素 int rear; //尾指针，指向最后一个元素的下一个位置 ，当头指针和尾指针指向相同时，队列为空 }Queue; int InitQueue(Queue*Q) //建立队列 { Q->base=(ElemType*)malloc(MAXSIZE*sizeof(ElemType)); //申请存储空间 if (!Q->base) return ERROR; Q->front=0; //头尾指针初始化 Q->rear=0; return OK; } int DestroyQueue(Queue*Q) //摧毁队列 { if (!Q->base) return ERROR; free(Q->base); Q->front=0; Q->rear=0; return OK; } int ClearQueue(Queue*Q) //清空队列 { if (!Q->base) return ERROR; Q->front=0; Q->rear=0; return OK; } int QueueEmpty(Queue*Q) //验证队列是否为空 { if (!Q->base) return ERROR; if (Q->front==Q->rear) return TRUE; return FALSE; } int GetHead(Queue Q,ElemType*e) //得到队头元素 { if (!Q.base) return ERROR; *e=*(Q.base+Q.front); return OK; } int EnQueue(Queue*Q,ElemType e) //插入元素e队列 { if ((Q->rear+1)%MAXSIZE==Q->front) return ERROR; //若队列已满，返回错误 *(Q->base+Q->rear)=e; Q->rear=(Q->rear+1)%MAXSIZE; //尾指针下移一个单位，若到达存储空间最后，则回到开头。 return OK; } int DeQueue(Queue*Q,ElemType*e) //删除队头元素，返回值给e { if (Q->front==Q->rear) return ERROR; *e=*(Q->base+Q->front); Q->front=(Q->front+1)%MAXSIZE; //头指针下移一个单位，若到达存储空间最后，则回到开头。 return OK; } int QueueLength(Queue Q) //返回队列长度 { if (Q.rear>=Q.front) return Q.rear-Q.front; //若尾指针在头指针后 else return MAXSIZE-(Q.front-Q.rear); //若尾指针在头指针前 } int main() { Queue Q; ElemType*p; int e,choice; do{ e=0; printf("输入操作: 0.退出 1.返回队列长度 2.插入 3.删除 4.获取队列头元素值 5.清空队列 6.创建队列 7.销毁队列 8.验证队列是否为空\n"); scanf("%d",&choice); switch (choice) { case 1: { e=QueueLength(Q); printf("%d\n",e); break; } case 2: { printf("输入插入元素值\n"); scanf("%d",&e); EnQueue(&Q,e); break; } case 3: { DeQueue(&Q,&e); printf("%d\n",e); break; } case 4: { GetHead(Q,&e); printf("%d\n",e); break; } case 5: { ClearQueue(&Q); break; } case 6: { InitQueue(&Q); break; } case 7: { DestroyQueue(&Q); break; } case 8: { printf("%d\n",QueueEmpty(&Q)); break; } } printf("["); p=Q.base+Q.front; while (p!=(Q.base+Q.rear)) { printf("%d ",*p); p++; if (p==Q.base+MAXSIZE) p=Q.base; } printf("]\n"); }while(choice!=0); return 0; }

5 总结

循环队列和链队列的大部分基本操作（返回长度的时间复杂度为O(n)）时间复杂度都为O(1)。循环队列长度固定，而链队列的长度则可以扩展，因此链队列更为灵活。在队列长度可以确定的情况下，循环队列较好，在队列长度不确定时，链队列比较好。