-
队列(Queue)：队列是只允许在一端进行插入，在另一端进行删除的线性表，简称队
-
操作特性：FIFO
-
队头(Front)：允许删除的一端
-
队尾(Rear)：允许插入的一端
-
入队：向队列中插入元素
-
出队：从队列中删除元素
-
基本操作
- InitQueue(&Q)：初始化队列，构造一个空队列
- DestroyQueue(&Q)：销毁一个队列并释放队列所占用的存储空间
- EnQueue(&Q, x)：入队，若队列未满，则将x加入，使之成为新队尾
- DeQueue(&Q, &x)：出队，若队列非空，删除队头元素，并用x返回
- GetHead(Q, &x)：若队列非空，获取队头元素并用x返回
-
队列的顺序实现：分配一块连续的存储单元存放队列的元素，并附设两个指针：队头指针(front)指向队头元素，队尾指针(rear)指向队尾元素的下一个位置
-
队列的顺序存储类型描述
#define MaxSize 50 typedef struct{ ElemType data[MaxSize]; int front,rear; }SqQueue;-
初始状态/队空条件：Q.front == Q.rear == 0
void InitQueue(SqQueue &Q){ Q.front=Q.rear=0; } -
入队操作：队不满时，先送值到队尾元素，队尾指针+1
bool EnQueue(SqQueue &Q, ElemType x){ // 这种判断是错误的 if(Q.rear==MaxSize) return false; Q.data[Q.rear]=x; Q.rear++; return true; } -
出队操作：队非空时，取出队头元素，队头指针+1
bool DeQueue(SqQueue &Q, ElemType &x){ // 这种判断是错误的 if(Q.rear==Q.front) return false; x=Q.data[Q.front]; Q.front++; return true; }
-
-
假溢出：如下图所示，由于进行多次出队操作会导致Q.front不断+1，因此Q.front会不断向Q.rear靠近，然后Q.front前面的元素并没有被真正删除，实际上仍然占用着队列空间而却没有被使用，因此Q.front==Q.rear不能作为队满的判断条件
-
循环队列：为了避免队列出现假溢出的情况，把顺序队列臆造为一个环状的空间，即把顺序队列元素的表从逻辑上视为一个环，称为循环队列
- 实现原理：利用取余运算，在队首/尾指针到达MaxSize-1位置后，再前进一个位置就自动到0
- 队首指针进1：Q.front=(Q.front+1)%MaxSize
- 队尾指针进1：Q.rear=(Q.rear+1)%MaxSize
- 队列长度：(Q.rear+MaxSize-Q.front)%MaxSize
-
循环队列判满空条件
-
牺牲一个单元来区分对空和队满：队头指针为队尾指针的下一位置则为队满
- 队满：Q.front==(Q.rear+1)%MaxSize
- 队空：Q.front==Q.rear
-
增加表示队列长度的数据成员：
- 队满：Q.size==MaxSize
- 对空：Q.size==0
-
队列中增加tag数据成员
- 最近一次执行删除操作，则tag=0：若因删除导致Q.front==Q.rear，则队空
- 最近一次执行插入操作，则tag=1：若因插入导致Q.front==Q.rear，则队满
-
-
初始化
void InitQueue(SqQueue &Q){ Q.rear=Q.front=0; } -
判队满
bool isFull(SqQueue Q){ // 牺牲法 if(Q.front==(Q.rear+1)%MaxSize) return true; else return false; // 设Q.size if(Q.size==MaxSize) return true; else return false; // 设Q.tag if(Q.front==Q.rear && tag==1) return true; else return false; } -
判队空
bool isEmpty(SqQueue Q){ if(Q.front==Q.rear) return true; else return false; } -
入队
bool EnQueue(SqQueue &Q, ElemType e){ if(!isFull(Q)) return false; Q.data[Q.rear]=e Q.rear=(Q.rear+1)%MaxSize; return true; } -
出队
bool DeQueue(SqQueue &Q, ElemType &e){ if(!isEmpty(Q)) return false; e=Q.data[Q.front]; Q.front=(Q.front+1)%MaxSize; return true; }
-
链队列：队列的链式表示，它实际上是一个同时带有队头指针和队尾指针的单链表，头指针指向队头结点，尾指针指向队尾结点
-
适用：数据元素变动大，数据元素不确定
-
队列的链式存储类型描述
// 结点 typedef struct LinkNode{ ElemType data; struct LinkNode *next; }LinkNode; // 链式队列 typedef struct{ LinkNode *front, *rear; }LinkQueue; -
初始化
// 带头结点 void InitQueue(LinkQueue &Q){ Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode)); Q.front->next=NULL; } // 不带头结点 void InitQueue(LinkQueue &Q){ Q.front=NULL; Q.rear=NULL; }
-
入队
// 带头结点 void EnQueue(LinkQueue &Q, ElemType x){ LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode)); s->data=x; s->next=NULL; Q.rear->next=s Q.rear=s; } // 不带头结点 void EnQueue(LinkQueue &Q, ElemType x){ LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode)); s->data=x; s->next=NULL; if(Q.front==NULL){ Q.front=s; Q.rear=s; } else{ Q.rear->next=s; Q.rear=s; } } -
出队
// 带头结点 void DeQueue(LinkQueue &Q, ELemType &x){ if(Q.front->next==NULL) return false; LinkNode *p=Q.front->next; x=p->data; Q.front->next=p->next; if(Q.rear==p){ Q.rear=Q.front; } free(p); } // 不带头结点 void DeQueue(LinkQueue &Q, ELemType &x){ if(Q.front==NULL) return false; LinkNode *p=Q.front; x=p->data; Q.front=p->next; if(Q.rear==p){ Q.rear=NULL; Q.front=NULL; } free(p); }
-
双端队列：指两端都可以进行入队和出队操作的队列
-
输出受限的双端队列：允许在一端进行插入和删除操作，但在另一端只允许插入的双端队列
-
输入受限的双端队列：允许在一端进行插入和删除操作，但在另一端只允许删除的双端队列
