本文主要内容：介绍了队列的基本概念和基本操作，详细介绍了队列的顺序存储和链式存储。并介绍了循环队列和双端队列（以及输入/输出受限的双端队列），及其基本操作。

队列

一、队列的基本概念

1、基本概念

只允许在表的一端进行插入，而在表的另一端进行删除。插入端称为队尾，删除端称为队头。插入元素称为入队，删除元素称为出队。

这与我们日常生活中的排队一致，最早排队的最早离队。

队头(Front)：允许删除的一端
队尾(Rear)：允许插入的一端
空队列：不含任何元素的空表

2、基本操作

InitQueue(&Q)//初始化队列，构造一个空队列Q
QueueEmpty(Q)//判队列空，若队列Q为空返回true，否则返回false
EnQueue(&Q,x)//入队，若队列Q未满，将x加入，使之成为新的队尾
DeQueue(&Q,&x)//出队，若队列Q非空，删除队头元素，并用x返回
GetHead(Q,&x)//读队头元素，若队列Q非空，则将队头元素赋值给x

二、队列的顺序存储结构

1、队列的顺序存储

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针front指向队头元素，队尾指针rear指向队尾元素（或指向队尾元素的下一个位置）
队列的顺序存储类型：

#define MaxSize 50//队列中元素的最大个数
typedef struct{
	ElemType data[MaxSize];
	int front,rear;//队头指针和队尾指针
}SqQueue;

初始状态（队空条件）：Q.front== Q.rear== 0
进队操作：队不满时，先送值到队尾元素，再将队尾指针+1（队尾指针指向队尾元素的下一个位置）
出队操作：队不空时，先取队头元素值，再将队头指针+1

队列的初始状态和出队入队操作如下图所示。队列的初始状态有Q.front== Q.rear== 0成立。可以用Q.front ==Q.rear作为队列判空的条件，但不能用Q.rear ==MaxSize作为队列满的条件，如下图中的最后一种情况，满足Q.rear ==MaxSize但队列不是满的，这种情况称为“上溢出”，但不是真正的溢出，所以是一种假溢出。
操作受限的线性表——队列-LMLPHP

2、循环队列

把存储队列元素的表从逻辑上视为一个环，称为循环队列。当队首指针Q.front=MaxSize-1后，再前进一个位置就自动到0，可以利用除法取余运算（%）来实现。
初始时：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
循环队列出队入队的操作如下图所示：
操作受限的线性表——队列-LMLPHP
为了区分队空和队满，常常牺牲一个一个存储单元来区分是队空还是队满：
队满条件：(Q.rear+1)%MaxSize ==Q.front
队空条件：Q.front ==Q.rear
队列中元素的个数：(Q.rear-Q.frront+MaxSize)%MaxSize

此外，还有其他方式（不牺牲队列的存储单元）可以判断对空队满：
1.增设表示元素个数的数据成员Q.size。
队空的条件为Q.size ==0&&Q.front ==Q.rear
队满的条件为Q.size ==MaxSize&&Q.front ==Q.rear
2.增设tag数据成员
因为只有删除操作会导致队空，只有插入操作会导致队满，所以在每次删除操作后将tag置为0，在每次插入操作后将tag置为1。
队空条件：tag ==0&&Q.front ==Q.rear
队满条件：tag ==1&&Q.front ==Q.rear

1、循环队列的基本操作

（1）初始化

void InitQueue(SqQueue &Q){
	Q.rear=Q.front=0;//初始化队首、队尾指针
}

（2）判队空

bool isEmpty(SqQueue Q){
	if(Q.rear==Q.front) return true;
	else return false;
}

（3）入队

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;//更新队尾指针
	return true;
}

（4）出队

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;
}

三、队列的链式存储结构

1、队列的链式存储

队列的链式表示称为链队列。单链表的头指针指向队头结点，尾指针指向队尾结点（单链表的最后一个结点）。
队列的链式存储如下图所示。通常将链式队列设计成一个带头结点的单链表。
操作受限的线性表——队列-LMLPHP

2、链式队列的基本操作

1）初始化

void InitQueue(LinkQueue &Q){
	Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));//建立头结点
	Q.front->next=NULL;//初始化为空
}

2）判队空

bool IsEmpty(LinkQueue Q){
	if(Q.front==Q.rear) return true;
	else return false;	
}

3）入队

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;
}

4）出队

bool DeQueue(LinkQueue &Q,ElemType &x){
	if(Q.front==Q.rear) return false;
	LinkNode *p=Q.front->next;//p为头结点后第一个元素
	x=p->data;
	Q.front->next=p->next;//删除元素p
	if(Q.rear==p) Q.rear=Q.front;//p结点是队列中唯一一个元素
	free(p);
	return true;
}

四、双端队列

双端队列是指允许两端都可以进行入队和出队操作的队列。双端队列形式如下图所示：
操作受限的线性表——队列-LMLPHP
在双端队列进队时，前端进的元素排列在队列中后端进的元素的前面，后端进的元素排列在队列中前端进的元素的后面。
在双端队列出队时，前端和后端都是先出的元素排列在后出的元素的前面。
【思考，如何由入队序列abcd得到出队序列dcab？见下图所示（答案不唯一）】
操作受限的线性表——队列-LMLPHP
【独立思考，如何由入队序列1234得到出队序列4132？】

双端队列其余比较常见的形式有两种，分别为：输入受限的双端队列和输出受限的双端队列。
顾名思义，输入受限的双端队列允许在一端进行插入和删除，但在另一端只允许删除；输出受限的双端队列允许在一端进行插入和删除，但在另一端只允许插入。如下图所示：
操作受限的线性表——队列-LMLPHP
本文内容为个人学习总结所得，如有问题欢迎评论区指正，感谢观看。

小橘子xxb

操作受限的线性表——队列

目录

队列