[数据结构]队列(Queue)

• 1 队列的基本概念
• • 1.1 队列的定义
  • 1.2 队列的基本操作
• 2 队列的顺序存储结构
• • 2.1 队列顺序存储结构的实现
  • 2.2 循环队列
  • 2.3 循环队列的基本操作实现
• 3 队列的链式存储结构
• • 3.1 队列的链式存储结构的实现
  • 3.2 链式队列的基本操作实现
• 4 双端队列

队列也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除，它与栈的主要区别就在于插入、删除操作的限定不同。因此，队列具有先进先出(First In First Out，FIFO)的操作特性。

入队(进队)：向队列中插入元素。
出队(离队)：从队列中删除元素。
队头(Front)：队列中允许删除的一端。
队尾(Rear)：队列中允许插入的一端。
空队列：不含任何元素的空表。

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

队列的顺序存储结构是利用一块连续的存储单元来存放队列中的元素，并设置两个指针：队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置(这个并不是固定的，也有front和rear分别指向队头元素和队尾元素的情况)

队列的顺序存储结构可以用下面结构体描述，其中QueueSize视情况而定，队头指针和队尾指针并不是指针类型的变量。

typedef struct{
	ElemType data[QueueSize];	// 存放队列元素
	int front,rear;             // 队头指针和队尾指针
}SqQueue

队空的条件：Q.front == Q.rear == 0
进队操作：队列不满时，先将值插入到队尾，再将队尾指针加1；
出队操作：队列非空时，先将队头元素取出，再将队头指针加1；

但是这样的队列结构有一个问题——就是如何去判断队列已满，用下图所示：

如果以Q.rear == QueueSize 来当做队列已满的条件，在上图中可以看到在插入五个元素之后确实队列已满了，此时Q.rear == QueueSize。但是在后续删除四个元素之后，Q.rear仍然等于QueueSize，但是可以看出队列并没有满(给队列分配的连续的存储空间内还有空闲的空间)。为了解决队列这个假溢出缺点，就需要用到循环队列

循环队列是从逻辑结构的角度(在存储结构上还是一块连续的地址)，把顺序队列看成环状，利用取余运算来实现各参数的变换。

队空的条件：Q.front == Q.rear == 0
进队操作：队列不满时，先将值插入到队尾，Q.rear = (Q.rear + 1 ) % QueueSize
出队操作：队列非空时，先将队头元素取出，Q.front = (Q.front + 1) % QueueSize
队列长度：(Q.rear + QueueSize - Q.front) % QueueSize

前面提到循环队列可以用来解决假溢出的缺点，那么循环队列要如何判断队列已满呢？先看下面的几个图

队列已满的时候，可以知道Q.front == Q.rear，这跟队列的初始状态是一样的，如果用这个来当做队列已满的条件，就不能区分队列到底是空还是满了。
为了区分队列是空还是满，有三种处理方式

1. 牺牲一个单元来区分对空还是堆满。(即上图队列未满的时候就当做是队列已满)

   此时队满的条件为：(Q.rear + 1) % QueueSize == Q.front
   队列为空的条件：Q.front == Q.rear
   队列长度为：(Q.rear - Q.front + QueueSize) % QueueSize
   

2. 增设表示元素个数的数据成员。这样队空的条件就是Q.Size == 0，队满的条件就是Q.Size == QueueSize。

3. 增设tag数据成员，用于区分是队空还是队满，如果tag == 0 且有 Q.front == Q.rear，则队列为空，若tag == 1 且有 Q.front == Q.rear，则队列为满。

(1)初始化队列

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

(2)判断队列是否为空

bool QueueEmpty(SqQueue Q){
	if(Q.rear == Q.front)
		return true;		      //队列为空
	else
		return false;             //队列不为空
}

(3)入队

bool EnQueue(SqQueue &Q, ElemType x){
	if((Q.rear + 1) % QueueSize == Q.front)
		return false; 			   //队列已满，不能再入队
	Q.data[Q.rear] = x;					
	Q.rear = (Q.rear + 1) % QueueSize;	//先将x入队，再对队尾指针加1取余
	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) % QueueSize;  //先将x出队，再对队头指针加1取余
	return true;
}

因为队列也是线性表，所以队列也能够利用链式存储结构来实现。利用链式存储结构的队列成为链队列。队列的链式存储可以用下面的结构体来描述

typedef struct LinkNode{		//链队列的节点
	ElemType data;
	struct LinkNode *next;
}LinkNode;
typedef struct{					//链队列的队头指针和队尾指针
	LinkNode *front, *rear;     
}LinkQueue;

如果没有设定头结点，那么当Q.front和Q.rear都为NULL时，队列为空。
没有设定头结点时，入队和出队的操作比较麻烦

入队：建立新结点并插入链队列尾部，并让Q.rear指向这个新插入的节点，如果原队列为空，则令Q.front指向该结点。
出队：首先判断队列是否为空，不为空则取出队头元素，并让Q.front指向下一个结点。取出的元素是最后一个元素，则将Q.front和Q.rear都设置为NULL

设定头结点之后，入队和出队的操作就没有那么麻烦了，无需因为链队列是否为空，而进行额外的操作。初始状态Q.front和Q.rear都指向头结点，入队只需要在Q.rear的后插入新结点(即便原队列为空，也不用令Q.front指向该结点)，出队只需要删除头结点后的结点(不过删除的元素如果是最后一个元素，还是要将Q.rear指向头结点)。
链队列适合于数据元素变动比较大的情形，而且它不存在队列满且产生溢出的问题。

(1)初始化链队列

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

(2)判断队是否为空

bool QueueEmpty(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;			
	return true;			
}

(4)出队

void 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;	
	if(Q.rear == p)			//若队头元素是最后一个元素，将Q.rear指向头结点。
		Q.rear = Q.front;
	free(p);
	return true;
}

双端队列是指允许两端都可以进行入队和出队操作的队列。其逻辑结构仍然是线性结构。队列的两端分别称为前端和后端。(用于考察给定输入序列，能否出现一种输出序列)
双端队列可以理解为是栈和队列的结合，从同一端进行插入和删除操作，就是栈，从不同端进行插入和删除操作，就是队列。
双端队列还有输入受限的双端队列和输出受限的双端队列。
顾名思义，输入受限的双端队列就是一端可以进行插入和删除操作，另一端只能进行删除操作(即限制了插入操作)的队列。输出受限的双端队列就是一端可以进行插入和删除操作，另一端只能进行插入操作(即限制了删除操作)的队列。