2.队列
大约 2 分钟
队列的顺序存储结构
顺序存储
定义
分配一块连续的存储单元，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置[1]
- 初始化：
Q.front=Q.rear=0 - 进队：队不满时，先送值，队尾再加
1 - 出队：队不空时，先取值，队头再加
1 - 队为空：
Q.front=Q.rear=0 - 队满：
Q.rear == MaxSize可能存在“假溢出”
#define MaxSize 50
typedef struct{
ElemType data[MaxSize];
int front,rear;
}SqQueue;
循环队列
解决假溢出
采用循环队列解决假溢出现象，存储队列元素的表从逻辑上视为一个环。
- 初始时：
Q.front=Q.rear=0。 - 队首指针进1：
Q.front=(Q.front+1)%MaxSize。 - 队尾指针进1：
Q.rear=(Q.rear+1)%MaxSize。 - 队列长度：
(Q.rear+MaxSize-Q.front)%MaxSize。 - 出队入队时：指针都按顺时针方向进1。
区分队空队满
- 牺牲一个单元来区分，队头指针在队尾指针的下一个位置视为队满。
- 队满：
(Q.rear+1)%MaxSize==Q.front - 队空：
Q.front==Q.rear - 元素个数：
(Q.rear+MaxSize-Q.front)%MaxSize
- 队满：
- 类型中增设表示元素个数的数据成员。这样，队空的条件为
Q.size==0；队满的条件为Q.size==MaxSize。这两种情况都有Q.front==Q.rear。 - 类型中增设
tag数据成员，以区分是队满还是队空。tag等于0时，若因删除导致Q.front==Q.rear,则为队空：tag等于1时，若因插入导致Q.front==Q.rear,则为队满。
队列的链式存储结构
实际是一个同时带有队头指针和队尾指针的单链表[2]，头指针指向队头结点，尾指针指向队尾结点
typedef struct LinkNode{
ElemType data;
struct LinkNode *next;
}LinkNode;
typedef struct{
LinkNode *front,*rear;
}*LinkQueue;
- 队空：
Q.front==NULL && Q.rear==NULL - 进队：将新结点插入到链表的尾部，并让
Q.rear指向这个新插入的结点[3]。 - 出队：若不为空，取出队头元素将其从链表中摘除，并让
Q.frot指向下一个结点[4]。
双端队列
两端都可以入队出队