目录
队列的相关概念
定义
逻辑结构
存储结构
运算规则
实现方式
队列的基本操作
循环队列——队列的顺序表示和实现
队列的顺序存储结构
假溢出-引出循环队列
判断循环队列队空队满
循环队列的操作
队列的初始化
求循环队列长度
循环队列入队
循环队列出队
取循环队列队头元素
队列-链式队列
队列的链式存储结构
链队列的类型定义
链式队列的操作
链队的初始化
链队的入队
链队的出队
取链队的队头元素
销毁链队列
队列的相关概念
定义
只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表（头删尾插）。
逻辑结构
与线性表相同，仍为一对一关系。
存储结构
顺序队或链队，以循环顺序队列更常见。
队列的物理存储可以用顺序存储结构，也可用链式存储结构。相应地，队列的存储方式也分两种，即顺序队列和链式队列。
运算规则
只能在队首和队尾运算，且访问节点时依照先进先出（FIFO）的原则。
实现方式
关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。
队列的基本操作
ADTQueue{
数据对象：D={ai | ai∈ElemSet, i = 1,2,...,n,n≥0 }
数据关系：R={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}约定其中a1端为队列头，an端为队列尾。
}ADTQueue
InitQueue(&Q) 操作结果：构造空队列Q
DestroyQueue(&Q) 条件：队列Q已存在；操作结果：队列Q被销毁
ClearQueue(&Q) 条件：队列Q已存在；操作结果：将Q清空
QueueLength(Q)条件：队列Q已存在；操作结果：返回Q的元素个数，即队长
GetHead(Q, &e)条件：Q为非空队列；操作结果：用e返回Q的队头元素
EnQueue(&Q, e)条件：队列Q已存在；操作结果：插入元素e为Q的队尾元素
DeQueue(&Q, &e) 条件：Q为非空队列；操作结果：删除Q的队头元素，用e返回值
……还有将对列置空、遍历队列等操作……
循环队列——队列的顺序表示和实现
队列的顺序存储结构
用一维数组base[MAXQSIZE]
#define MAXQSIZE 100 // 最大队列长度Typedef struct {QElemType *base; // 初始化的动态分配存储空间int front;// 头指针int rear; // 尾指针}SqQueue;
假溢出-引出循环队列
假设当前队列分配的最大空间为 6, 则当队列处于图(d) 所示的状态时不可再继续插入新的队尾元素，否则会出现溢出现象， 即因数组越界而导致程序的非法操作错误。 事实上，此时队列的实际可用空间并未占满，所以这种现象称为 “假溢出＂。这是由 ＂队尾入队，队头出队” 这种受限制的操作造成的。
怎样解决这种 “假溢出” 问题呢？ 一个较巧妙的办法是将顺序队列变为一个环状的空间，如图所示，称之为循环队列。
base[0]接在hase[MAXQSIZE -1]之后，若rear+1==M，则令rear=0；
实现方法：利用模（mod，C语言中：%）运算。
插入元素：Q.base[Q.rear]=x;
Q.rear=(Q.rear+1)%MAXQSIZE;
删除元素：x=Q.base[s.front]
Q.front=(Q.front+1)%MAXQSIZE
循环队列：循环使用为队列分配的存储空间。
判断循环队列队空队满
少用一个元素空间
队空：front==rear
队满：(rear+1)%MAXQSIZE==front
循环队列的操作
队列的初始化
Status InitQueue(SqQueue &Q){Q.base = new QElemType[MAXQSIZE] // 分配数组空间// Q.base = (QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!Q.base) exit(OVERFLOW); // 存储分配失败Q.front=Q.rear=0; // 头指针尾指针置为0，队列为空return OK;}
求循环队列长度
对于非循环队列，尾指针和头指针的差值便是队列长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXQSIZE，然后与MAXQSIZE求余。
int QueueLength(SqQueue Q){// 返回Q的元素个数，即队列的长度return(Q.rear-Q.front+MAXQSIZE) % MAXQSIZE;}
循环队列入队
入队操作是指在队尾插入一个新的元素。
Status EnQueue(SqQueue &Q, QElemType e) {// 插入元素e为Q的新的队尾元素if((Q.rear+1) % MAXQSIZE == Q.front) // 尾指针在循环意义上加1后等于头指针，表明队满return ERROR;Q.base[Q.rear] = e; // 新元素插入队尾Q.rear = (Q.rear + 1) % MAXQSIZE; // 队尾指针加1return OK;}
循环队列出队
出队操作是将队头元素删除。
Status DeQueue(SqQueue &Q, QElemType &e) {// 删除Q的队头元素，用e返回其值if(Q.front==Q.rear) return ERROR; // 队空e = Q.base[Q.front]; // 保存队头元素Q.front = (Q.front + 1) % MAXQSIZE; // 队头指针加1return OK;}
取循环队列队头元素
当队列非空时， 此操作返回当前队头元素的值， 队头指针保持不变。
SElemType GetHead(SqQueue Q) {// 返回Q的队头元素，不修改队头指针if(Q.front != Q.rear) // 队列非空return Q.base[Q.front]; // 返回队头元素的值，队头指针不变}
队列-链式队列
若用户无法估计所用队列的长度，则宜采用链队列。
队列的链式存储结构
链队列的类型定义
#define MAXQSIZE 100 // 最大队列长度typedef struct Qnode {QElemType data;stuct Qnode *next;}QNode, *QueuePtr;typedef struct {QueuePtr front; // 队头指针Queueptr rear;// 队尾指针}LinkQueue;
链式队列的操作
链队的初始化
Status InitQueue(LinkQueue &Q) {// 构造一个空队列QQ.front = Q.rear = new QNode; // 生成新结点作为头结点，队头和队尾指针指向此结点Q.front -> next = NULL;// 头结点的指针域置空return OK;}
链队的入队
Status EnQueue(LinkQueue &Q, QElemType e) {// 插入元素e为Q的新的队尾元素p = new QNode; // 为入队元素分配结点空间，用指针p指向p -> data = e; // 将新结点数据域置为ep -> next = NULL; Q.rear -> next = p; // 将新结点插入到队尾Q.rear = p; // 修改队尾指针return OK;}
链队的出队
Status DeQueue(LinkQueue &Q, QElemType &e) {// 删除Q的队头元素，用e返回其值if(Q.front == Q.rear) return ERROR; // 若队列空，则返回ERRORp = Q.front -> next; // p指向队头元素e = p -> data;// e保存队头元素的值Q.front -> next = p -> next; // 修改头指针if(Q.rear == p) Q.rear = Q.front;// 最后一个元素被删，队尾指针指向头结点delete p;// 释放原队头元素的空间return OK;}
需要注意的是，在链队出队操作时还要考虑当队列中最后一个元素被删后，队列尾指针也丢失了，因此需对队尾指针重新赋值（指向头结点）。
取链队的队头元素
SElemType GetHead(LinkQueue Q) {// 返回Q的队头元素，不修改队头指针if(Q.front != Q.rear){ // 队列非空return Q.front -> next -> data; // 返回队头元素的值，队头指针不变}}
销毁链队列
Status DestroyQueue(LinkQueue &Q) {while(Q.front) {p= Q.front -> next; free(Q.front);Q.front = p;} // Q.rear = Q.front -> next; free(Q.front); Q.front = Q.rear;return OK;}
