数据结构：队列（王道2022）
队列（Queue）是只允许在一端进行插入，在另一端删除的线性表
插入：入队
删除：出队
重要术语：
队头：允许删除的一端
队尾：允许插入的一端
空队列
//初始化队列，构造一个空队列
InitQueue(&Q);
//销毁队列。销毁并释放队列Q所占用的内存空间
DestroyQueue(&Q);
//入队，若队列Q未满，将x加入，使之成为新的队尾（增）
EnQueue(&Q,x);
//出队，若队列Q非空，删除队头元素，并用x返回（删）
DeQueue(&Q,&x);
//读队头元素，若队列Q非空，则将队头元素赋值给x （查）
Get(Q,&x);
顺序存储队列
定义
#define MaxSize 10 //定义队列中元素的最大个数
typedef struct {
ElemType data[MaxSize]; //用静态数组存放队列元素
int front,rear; //队头指针和队尾指针
}SqQueue;
初始化
void InitQueue(SqQueue &Q){
//初始时，队头，队尾指针指向0
Q.front = Q.rear = 0;
}
入队
//入队
bool EnQueue(SqQueue &Q,ElemType x){
if((Q.rear+1)%MaxSize == Q.front) //缺点，会牺牲一个单元
return false; //队满就报错
Q.data[Q.rear] = x; //新元素插入队尾
Q.rear = (Q.rear+1)%MaxSize; //队尾指针加1取模
return true;
}
出队
// 出队（删除一个队头元素，并用x返回）
bool DeQueue(SqQueue &Q,ElemType &x){
if(Q.rear == Q.front){
return false; //队空则报错
}
x = Q.data[Q.front];
Q.front = (Q.front+1)%MaxSize;
return true;
}
获取队头元素的值
//获取队头元素的值，赋值给x
bool Get(SqQueue Q,ElemType &x){
if(Q.rear == Q.front){
return false; //队空则报错
}
x = Q.data[Q.front];
return true;
}
判断队列已满/已空（重点）
队列已满条件：队尾指针再下一个位置是队头。
(Q.rear+1)%MaxSize == Q.front
队空条件：
Q.rear == Q.front
链式存储队列
定义
typedef struct LinkLNode{
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;
}
判空
//判断队列是否为空
bool IsEmpty(LinkQueue Q){
if(Q.front == Q.rear){
return true;
}else{
return false;
}
}
或者
//判断队列是否为空
bool IsEmpty(LinkQueue Q){
if(Q.front->next = NULL){
return true;
}else{
return false;
}
}
初始化（带头节点）
//初始化（不带头节点）
void InitQueue(LinkQueue &Q){
Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
Q.front = Q.rear = NULL;
}
判空
//判断队列是否为空
bool IsEmpty(LinkQueue Q){
if(Q.front = NULL){
return true;
}else{
return false;
}
}
入队（带头节点）
//入队（带头节点）
bool EnQueue(LinkQueue &Q,ElemType x){
LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
s->data = x;
s->next = NULL;
Q.rear->next = s; //新节点插入到rear之后
Q.rear = s; //修改表尾指针
return true;
}
入队（不带头节点）
//入队（不带头节点）
bool 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; //新节点插入到rear之后
Q.rear = s; //修改表尾指针
}
return true;
}
出队（带头节点）
//出队（带头结点）
bool DeQueue(LinkQueue &Q,ElemType &x){
if(Q.front == Q.rear){
return false; //空队
}
LinkNode *p = Q.front->next;
x = p->data;
Q.front->next = p->next; //修改头结点的next指针
if(Q.rear == p){ //此次时最后一个结点出队
Q.rear = Q.front; //修改rear指针
}
free(p); //释放结点空间
return true;
}
出队（不带头节点）
//出队（不带头结点）
bool DeQueue(LinkQueue &Q,ElemType &x){
if(Q.front == NULL){
return false; //空队
}
LinkNode *p = Q.front;
x = p->data;
Q.front = p->next; //修改头结点的next指针
if(Q.rear == p){ //此次时最后一个结点出队
Q.rear = Q.front = NULL; //修改rear指针
}
free(p); //释放结点空间
return true;
}
队列满的条件
一般不会队满，比顺序存储要好
双端队列（考察过）
双端队列：只允许从两端插入，两端删除的线性表
输入受限的双端队列
只允许从一端插入、两端删除的线性表
输出受限的双端队列
只允许从两端插入、一端删除的线性表
考点：判断输出序列的合法性
输入序列为1,2,3,4 合法性（栈、队列）
输入受限的双端队列，栈中合法，双端队列一定合法。
输出受限的双端队列，栈中合法，双端队列一定合法。