队列（Queue）基本概念
-
定义
队列（Queue）时只允许在一端进行插入，在另一端删除的线性表。
特点：先进入队列的元素先出队
先进先出 First In First Out(FIFO)
-
重要术语
队头、队尾、空队列
-
-
基本操作
-
创、销
InitQueue(&Q):初始化队列。构造一个空队列Q。
DestroyQueue(&Q):销毁队列。销毁并释放队列Q所占用的内存空间。
-
增、删
EnQueue(&Q,x):入队，若队列Q未满，则将x加入使之成为新队尾
DeQueue(&Q,&x):出队，若队列Q非空，则删除对头元素，并用x返回。
删除队头元素
-
查：队列的使用场景中大多之访问对头空间。
GetHead(Q,&x):读队头元素。若队列Q非空，则将对头元素赋值给x。
不删除队头元素
-
其他常用操作
QueueEmpty(Q):判队列空。若队列Q为空返回true，否则返回false
-
队列的顺序实现
-
用顺序存储实现队列
#define MaxSize 10 //定义队列中元素的最大个数
typedef struct{
//静态数组：连续的存储空间，大小MaxSize*sizeof(ElemType)
ElemType data[MaxSize]; //静态数组存放队列中元素
int front,rear; //队头指针和队尾指针
}SqQueue;
void testQueue(){
SqQueue Q; //声明一个队列（顺序存储）
//……后续操作……
} 
-
基本操作
-
创（初始化）
#define MaxSize 10 //定义队列中元素的最大个数 typedef struct{ ElemType data[MaxSize] //静态数组存放队列中元素 int front,rear; //队头指针和队尾指针 }SqQueue; //初始化队列 void InitQueue(SqQueue &Q){ //初始时 队头、队尾指针指向0 Q.rear = Q.front = 0; } void testQueue(){ //声明一个队列（顺序存储） SqQueue Q; InitQueue(Q); //……后续操作…… } //判断队列是否为空 bool QueueEmpty(SqQueue Q){ if(Q.rear==Q.front) //对空条件 return true; else return false; } -
增（入队）只能从队尾入队
#define MaxSize 10 //定义队列中元素的最大个数 typedef struct{ ElemType data[MaxSize] //静态数组存放队列中元素 int front,rear; //队头指针和队尾指针 }SqQueue; //判断队列是否为空 bool QueueEmpty(SqQueue Q){ if(Q.rear==Q.front) //对空条件 return true; else return false; } //入队 bool EnEmpty(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; }
{0,1,2,……,MaxSize-1}将存储空间在逻辑上变成了“环状”——循环队列
队列已满的条件：队尾指针的再下一个位置是对头，即(Q.rear+1)%MaxSize==Q.front
-
???? 队列元素个数：(rear+MaxSize-front)%MaxSize
-
❔ 不浪费一个存储单元 → 增设一个size数据成员
#define MaxSize 10 //定义队列中元素的最大个数 typedef struct{ ElemType data[MaxSize] //静态数组存放队列中元素 int front,rear; //队头指针和队尾指针 int size; //队列当前长度 }SqQueue;❔ 不浪费一个存储单元 → 增设一个tag数据成员
#define MaxSize 10 //定义队列中元素的最大个数 typedef struct{ ElemType data[MaxSize] //静态数组存放队列中元素 int front,rear; //队头指针和队尾指针 int tag; //最近进行的是删除/插入 //每次删除操作成功时，都令tag=0; //每次插入操作成功时，都令tag=1; }SqQueue; -
删（出队）只能从对头元素出队
//出队 bool DeQueue(SqQueue &Q,ElemType &x){ if(Q.rear+1==Q.front) return false; //队满则报错 x = Q.data[Q.front]; Q.front = (Q.front + 1)%MaxSize;//队头指针后移 return true; } -
查（获取队头元素）
//获得对头元素的值，用x返回 bool GetHead(SqQueue Q,ElemType &x){ if(Q.rear==Q.front) return false; //队空则报错 x = Q.data[Q.front]; return true; }
-
-
其他出题方式
????❄️ 队尾指针rear指向队尾元素
入队操作：
Q.rear = (Q.rear + 1)%MaxSize;
Q.data[Q.rear] = x;初始化：
让front指向0的位置；让rear指向n-1的位置
判空：
(Q.rear+1)%MaxSize=Q.front
判满：
(Q.rear+1)%MaxSize=Q.front ❌
方案一：牺牲一个存储单元（头指针再尾指针后两个位置）
方案二：增加辅助变量（size/tag）
总结：
队列链式实现
-
定义
typedef struct LinkNode{ //链式队列结点 ElemType data; struct LinkNode *next; }LinkNode; typedef struct{ //链式队列 LinkNode *front,*rear; //队列的队头和队尾指针 }LinkQueue;
链队列——链式存储实现的队列
-
带头结点
初始化
typedef struct LinkNode{
ElemType data;
struct LinkNode *next;
}LinkNode;
typedef struct{
LinkNode *front,*rear;
}LinkQueue;
//初始化队列
void InitQueue(LinkQueue &Q){
//初始时 front rear都指向头结点
Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
Q.front->next=NULL;
}
void testLinkQueue(){
LinkQueue Q; //声明一个队列
InitQueue(Q); //初始化队列
//……后续操作……
}
//判断队列是否为空
bool IsEmpty(LinkQueue Q){
if(Q.front == Q.rear)
return true;
else
return false;
} 
入队
//新元素入队
void 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; //修改表尾指针
}出队
//新元素出队
void DeQueue(LinkQueue &Q,ElemType &x){
if(Q.front == Q.rear)
return false; //空队
LinkNode *p=Q.front->next;
x=p->data; //用变量x返回队头元素
Q.front->next=p->next;//修改头结点的next指针
if(Q.rear==p) //此次时最后一个结点出队
Q.rear=Q.front; //修改rear指针
free(p); //释放结点空间
return true;
}不带头结点
初始化
//初始化队列
void InitQueue(LinkQueue &Q){
//初始时 front rear都指向NULL
Q.front=NULL;
Q.rear=NULL;
}
//判断队列是否为空
bool IsEmpty(LinkQueue Q){
if(Q.front == NULL)
return true;
else
return false;
}入队
//新元素入队
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; //新结点插入到rear之后
Q.rear=s; //修改rear指针
}
}出队
//新元素出队
void DeQueue(LinkQueue &Q,ElemType &x){
if(Q.front ==NULL)
return false; //空队
LinkNode *p=Q.front; //p指向此次出队的结点
x=p->data; //用变量x返回队头元素
Q.front=p->next;//修改front指针
if(Q.rear==p) //此次时最后一个结点出队
Q.front=NULL; //front指向NULL
Q.rear=NULL; //rear指向NULL
free(p); //释放结点空间
return true;
}???? 链式存储——一般不对队满，除非内存不足
双端队列
栈：只允许从一端插入和删除的线性表
队列：只允许从一端插入，另一端删除的线性表
双端队列：允许从两端插入、两端删除的线性表
输入受限的双端队列：只允许一端插入、两端删除的线性表
输出受限的双端队列：只允许两端插入、一端删除的线性表
-
考点：判断输出序列合法性
若数据元素输入序列为1/2/3/4，则哪些输出序列是合法的？哪些是非法的？
-
合法
-
栈
1/2/3/4；1/2/4/3；1/3/2/4；1/3/4/2；1/4/3/2；
2/1/3/4；2/1/4/3；2/3/1/4；2/3/4/1；2/4/3/1；
3/2/1/4；3/2/4/1；3/4/2/1
4/3/2/1；
14种合法出栈序列
-
输入受限的双端队列（栈中合法的序列，双端队列中一定也合法）
在栈中非法在该方法下合法：
1/4/2/3；2/4/1/3；3/1/2/4；3/1/4/2；3/4/1/2；4/1/2/3；4/1/3/2；4/3/1/2
-
输出受限的双端队列（栈中合法的序列，双端队列中一定也合法）
-
在栈中非法在该方法下合法：
1/4/2/3；2/4/1/3；3/1/2/4；3/1/4/2；3/4/1/2；4/1/2/3；4/2/1/3；4/3/1/2
-
-
-