队列、循环队列、双端队列详解（含完整代码）_循环双端队列

一、释义

1.队列的定义

 2.基本术语

        二、队列的顺序存储

        1.队列的存储结构

        2.循环队列

        2.循环队列基本操作

        1.队列初始化

        2.入队操作

        3.出队操作

        4.判断队空

        5.获取队头元素

        6.完整代码

三、双端队列

1.释义

2.输入受限的双端队列

3.输出受限的双端队列

---

一、释义

1.队列的定义

        队列是一种操作受限的线性表。只允许在表的一端进行插入，在表的另一端进行删除。和日常生活中的队列一样 先入队的元素优先出队，即先进先出。如图：

 2.基本术语

入队：向队列中插入元素。

出队：向队列中删除元素。

队头：允许删除元素的一端。

队尾：允许插入元素的一端。

空队列：不含任何元素的空表。

        队列同栈一样，都是操作受限的线性表，操作受限的含义是有的操作不能进行比如队列，不能随机访问队列中的某个元素。

二、队列的顺序存储

1.队列的存储结构

        队列的顺序实现是指提前申请一块连续的存储空间来存放队列中的元素，并开辟两个指针。队头指针front指向队头元素，队尾指针rear指向队尾元素或者队尾元素的下一个位置，不同的教材有不同的说法，但是道理都一样。

#define MaxSize 10
typedef struct{
	int data[MaxSize];
	int front,rear;
}SqQueue;   
//注：在队列中 先插入的是队头front在数组底下 后插入的是队尾rear 
	//队尾指针有可能是指向队尾元素 也可能是指向队尾元素的下一个位置 

如代码所示提前分配一块空间大小为10的存储空间。 再看它在内存中的样子(初始化后)：

入队操作：队不满时，先送值到队尾元素，在将队尾指针+1；如图所示（10个元素入队）：

出队操作：队不空时，先取队头元素值，再将队头指针+1；如图所示（5个元素出队）

        容易知道通过front、rear两个指针能判断队列是否空，即front=rear。但是如何判断队列满条件呢？显然不可以用rear==MaxSize来判断因为入队的同时也可能会有元素出队（front指针也在移动）。通过臆想的循环队列即可实现判断队列是否满，具体见下文循环队列。

2.循环队列

        顺序队列有缺点，是因为无法判断队列是否满 故引出循环队列，其实循环队列就是将顺序队列臆想为一个环状的空间，即把存储队列元素的表视作一个环而rear、front指针都在此环上运动。如图所示两者区别：

        注意  循环队列的实质就是：rear指针指向顺序队列的最后一个元素的下一个位置是顺序队列的第一个位置。即实现了队列的循环。

        而怎么实现front、rear指针的循环呢？取余。当front指针=MaxSize-1时再前进一个位置就到了0，同理rear指针=MaxSize-1时也自动到0。故引出一些对队列的判断操作：

初始状态：front=rear=0;

队头指针+1（一个元素出队）：front=（front+1）%MaxSize

队尾指针+1（一个元素入队）：rear=（rear+1）%MaxSize

求队长：（rear+MaxSize-front）%MaxSize 

注意：若rear指向的是最后一个元素 而不是最后一个元素的下一个位置时又怎么求队长呢？

（rear+front+MaxSize+1）%MaxSize

对于循环队列，元素入队或者出队时 指针按顺时针方向+1。如图三个元素入队：

 但是如何判断循环队列队空队满呢？如图所示队空队满状态：

        此时rear、front都指向相同的位置，但是一个是队空一个是队满，显然不能用rear=front来判定队列是否为空。故有三种方式来判断队满还是队空：

1.牺牲一个存储单元来区分队满还是队空（也是最常用的方式）

        约定以队头指针在队尾指针的下一个位置作为队满的标志   看一下如果队空这个条件就无法满足是吧 如图：

队满条件为：（rear+1）%MaxSize=front

队空条件为：rear = front

队列中的元素个数为：（rear+front-MaxSize）%MaxSize

2.类型中增加表示元素个数的数据成员

        比如多添加一个size变量，初始时size=0，每入队一个元素size+1；出队一个元素size-1；最后通过rear=front（不是满就是空）和size=MaxSize来判定是否队满。很明显这种方式开销大了不建议。

3.类型中增加tag数据成员

        tag和size差不多，tag一般取值为0或1，如果最近一次操作是入队则tag赋值为1；如果最近一次操作是出队则tag赋值为0。说白了就是使用不同的操作tag值会变一下，而最后如果是入队操作且还有（rear=front）则一定是队满。

2，3种方式都增加了时间开销，而1只使用了一个存储空间就达到2，3种方式的效果

2.循环队列基本操作

1.队列初始化

初始时，让front指针和rear指针都为0

//队列初始化
void Init(SqQueue &Q){
	Q.front=0;
	Q.rear=Q.front;
} 

2.入队操作

        首先第一步一定是判断是否队满，给队尾指针指向的空间赋值，队尾指针再+1

//入队操作
bool EnQueue(SqQueue &Q,int e){
	if((Q.rear+1)%MaxSize==Q.front){  //判断队满 实际是牺牲了一个储存单元 否则与队空条件冲突 也可以选择不牺牲 还有另外两种办法 设置length，tag； 
		return false;
	}
	Q.data[Q.rear]=e;  //这里就不能用 Q.data[Q.rear++]=e 来简写了 因为rear需要进行取余 有可能到了下面
	Q.rear=(Q.rear+1)%MaxSize; //因为rear 指向的是队尾下一个位置 如果满了的时候 rear其实已经为9了 rear+1与 MaxSize取模就到了初始第一个位置0
	return true;
} 

3.出队操作

        首先判断队是否空，再拿到出队的元素；队头指针+1即可（元素没有彻底删除，而是后面来的队尾元素将其覆盖掉）

//出队操作
bool DeQueue(SqQueue &Q,int &e){
	if(Q.rear==Q.front){
		return false;
	}
	e=Q.data[Q.front];  //front指向的是队头元素
	Q.front=(Q.front+1)%MaxSize;  //队头指针向后移动 因为队头起初在底下 故+1表示后移1位 
	return true;
} 

4.判断队空

//判空操作
bool QueueEmpty(SqQueue &Q){
	if(Q.front==Q.rear){
		return true;
	}
	return false;
} 

5.获取队头元素

//获得队头元素 
bool GetHead(SqQueue Q,int &e){
	if(Q.rear==Q.front){
		return false;
	}
	e=Q.data[Q.front];  //front指向的是队头元素
	return true;
} 

6.完整代码

#include<stdio.h>
#include<stdlib.h>
#define MaxSize 10
typedef struct{
	int data[MaxSize];
	int front,rear;
}SqQueue;   
//注：在队列中 先插入的是队头front在数组底下 后插入的是队尾rear 
	//队尾指针有可能是指向队尾元素 也可能是指向队尾元素的下一个位置 
 
//队列初始化
void Init(SqQueue &Q){
	Q.front=0;
	Q.rear=Q.front;
} 
 
//判空操作
bool QueueEmpty(SqQueue &Q){
	if(Q.front==Q.rear){
		return true;
	}
	return false;
} 
 
//入队操作
bool EnQueue(SqQueue &Q,int e){
	if((Q.rear+1)%MaxSize==Q.front){  //判断队满 实际是牺牲了一个储存单元 否则与队空条件冲突 也可以选择不牺牲 还有另外两种办法 设置length，tag； 
		return false;
	}
	Q.data[Q.rear]=e;  //这里就不能用 Q.data[Q.rear++]=e 来简写了 因为rear需要进行取余 有可能到了下面
	Q.rear=(Q.rear+1)%MaxSize; //因为rear 指向的是队尾下一个位置 如果满了的时候 rear其实已经为9了 rear+1与 MaxSize取模就到了初始第一个位置0
	return true;
} 
 
//出队操作
bool DeQueue(SqQueue &Q,int &e){
	if(Q.rear==Q.front){
		return false;
	}
	e=Q.data[Q.front];  //front指向的是队头元素
	Q.front=(Q.front+1)%MaxSize;  //队头指针向后移动 因为队头起初在底下 故+1表示后移1位 
	return true;
} 
 
//获得队头元素 
bool GetHead(SqQueue Q,int &e){
	if(Q.rear==Q.front){
		return false;
	}
	e=Q.data[Q.front];  //front指向的是队头元素
	return true;
} 
 
//test 
int main(){
	SqQueue Q;
	Init(Q);
	EnQueue(Q,5);
	EnQueue(Q,9);
	EnQueue(Q,8);
	int e;
	DeQueue(Q,e);
	GetHead(Q,e);
	printf("%d\n",e);	
}

三、双端队列

1.释义

        双端队列是指：允许两端都可以进行入队和出队操作的队列。将队列的两端分为前端或者后端。两端都可以出队或者出队 如图：

         在双端队列里：前端进的元素排在队列后端进的元素前；后端进的元素排在前端进的元素后；在双端队列出队时 无论是前端还是后端出队，先出的元素排在后厨的元素前面。

2.输入受限的双端队列

        输入受限的双端队列是指：允许在一端进行插入和删除，但是另一端只能进行删除的双端队列，如图所示：

3.输出受限的双端队列

        输出受限的双端队列是指：允许在一端进行插入和删除，但是另一端只能进行插入的双端队列，如图所示：