数据结构——队列_stl 环形队列

  首先，什么是队列呢。队列和栈相似（都是一种操作受限的线性表）他的限制主要表现在只允许在表的一端进行插入操作，而在表的另一端进行删除操作。

• 队列基本知识
• 队列的顺序存储结构以及环形队列
• 数组模拟实现队列的基本操作
• 链表实现队列
• C++ 中的STL实现队列

队列的基本知识

队列一般分为两端：
1.队头（队首）：进行删除元素操作的一端（这个操作也叫作出队/离队）
2.队尾：进行插入新元素的一端（这个操作叫做入队/进队）。

因此我们可以通过队列两端的性质发现队列其实是下图的一个线性表

  我们可以发现 a ₁ 肯定是第一个进入队列的元素，而 a ₁ 也是第一个出队的元素因此队列也叫作**先进先出表**这就像有n个人走独木桥一般，永远都是第一个走上独木桥的人先走出来。

队列的顺序存储结构以及环形队列

顺序队列

   因为队列中的数据元素的逻辑关系呈线性关系，所以队列可以线性表一样采用顺序存储结构进行存储。我们可以通过分配一块连续的空间来存放队列中的元素，并用两个整型变量来反映队列中的元素变化，他们分别存储队首元素和队尾元素的下表位置，分别叫做队首指针以及队尾指针这样的队列也叫作顺序队
因此我们可以将顺序队定义成：

typedef struct{
	int data[1010];	//假设Maxsize 为 1010
	int front,rear; //设置头指针和尾指针
}SqQue;
1
2
3
4

首先我们假设这个队列的名字 为 q
如上图所示，第一个队列和最后一个队列为空时我们可以发现队空的条件就是q->front == q->rear
从第二个队列我们可以发现当队列是满队时有5个元素，而我们的存储方式从0开始所以我们可以假设这个队列的最多存储Maxsize个元素也因此我们可以得到队满的条件即为q->rear == Maxsize - 1假设Maxsize为5那么队满的条件就是 q -> rear == 4所以根据上图可以得证

队空条件：q->front == q->rear
队满条件：q->rear == Maxsize - 1
元素进队操作：（1）先将rear增1 （2）将元素放在data数组的rear位置
出队操作：（1）先将front增1 （2）取出data数组中front位置的元素

基本操作如下

//1.初始化队列
void InitQueue(SqQue*&q)
{
	q = new SqQue;
	q -> front = q->rear = -1;	
}
//2.销毁队列
void DestroyQueue(SqQue *&q)
{
	delete q;
}
//3.判断是否为空
bool Empty(SqQue* q)
{
	return q->front == q->rear; //返回true代表队列为空
}
//4.进队列的操作
bool enQueue(SqQue *&q, int e)
{
	if( q->rear == Maxsize - 1)
		return false;
	q -> rear ++;
	q -> data[q->rear] = e;
	return true;
}
//5.出队操作
bool popQueue(SqQue *&q,int &e)
{
	if(q -> front == q -> rear)
		return false;
	q -> front ++;
	e = q -> data[q -> front];
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

以上就是顺序队的基本操作了；
返回目录

环形队列

为了解决顺序队列出现的假溢出的情况因此我们可以将队列的首尾连接起来形成一个环形队列

队头指针front循环增一:front = (font + 1) % Maxsize;
队尾指针rear循环增一:rear = (rear + 1) % Maxsize;
上图就是环形队列的示意图因此
环形队列队空的条件为：q -> front == q -> rear;
队满的条件为：(q -> rear + 1) % Maxsize == q -> front

环形队列基本运算算法如下：

//1.初始化队列
void InitQueue(SqQue*&q)
{
	q = new SqQue;
	q -> front = q->rear = 0;	
}
//2.销毁队列
void DestroyQueue(SqQue *&q)
{
	delete q;
}
//3.判断是否为空
bool Empty(SqQue* q)
{
	return q->front == q->rear; //返回true代表队列为空
}
//4.进队列的操作
bool enQueue(SqQue *&q, int e)
{
	if( (q -> rear + 1) % Maxsize == q -> front )
		return false;
	q -> rear = (q -> rear + 1) % Maxsize;
	q -> data[q->rear] = e;
	return true;
}
//5.出队操作
bool popQueue(SqQue *&q,int &e)
{
	if(q -> front == q -> rear)
		return false;
	q -> front= (q -> front+ 1) % Maxsize;
	e = q -> data[q -> front];
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

以上就是环形队列的基本知识了，如果我们想把环形队列中的所有位置都利用起来的话，那我们就可以设计如下的环形队列类型

typedef struct{
	int data[Maxsize];
	int front;  //头指针
	int count;  //队列中元素的个数
}Qutype;
1
2
3
4
5

这样就可以有效的利用环形队列中的所有位置
返回目录

数组模拟队列

数组模拟队列是非常便捷的，我们依照0为第一个位置的下标模式定义如下操作

int hh = 0; 		//队头指针
int tt = 0; 		//队尾指针
int queue[Maxsize]; //队列数组 Maxsize == 100010
1
2
3

从如上的代码我们可以轻易的得出以下操作

队空：return tt > hh ? YES : NO
队满：tt == Maxsize
入队：queue[++tt] = e e为入队元素
出队：hh++
访问队首元：int t = queue[hh+1]

因此我们可以通过一个题目来把这些操作表现得更加清晰——题目选自AcWing算法基础课
实现一个队列，队列初始为空，支持四种操作：

---

AcWing.829 模拟队列
-push x – 向队尾插入一个数 x；
-pop– 从队头弹出一个数；
-empty – 判断队列是否为空；

• query – 查询队头元素。

现在要对队列进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。
输出格式
对于每个empty 和 query操作都要输出一个查询结果，每个结果占一行。
其中，empty 操作的查询结果为 YES 或NO，query 操作的查询结果为一个整数，表示队头元素的值。
数据范围
1 ≤ M ≤ 100000;
1 ≤ x ≤ 10⁹;
输入样例

10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6
1
2
3
4
5
6
7
8
9
10
11

输出样例

NO
6
YES
4
1
2
3
4

代码如下：

#include <iostream>
using namespace std;
const int N=1e5+10;
int queue[N],hh,tt;
int main()
{
     int m;cin>>m;
     while(m--)
     {
         int n;
         string op;
         cin>>op;
         if(op=="push") {cin>>n; queue[++tt]=n;}
         else if(op=="pop") hh++;
         else if(op=="query") cout<<queue[hh+1]<<endl;
         else 
         {
             if(tt>hh) cout<<"NO"<<endl;
             else cout<<"YES"<<endl; 
         }
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

以上就是数组模拟队列的方法
返回目录

---

链表实现队列

队列中的数据元素的逻辑关系呈线性关系，所以队列可以像线性表一样采用链式存储结构————链队
使用队头指针front和队尾指针rear两个指针，用front指向队首结点，用rear指向队尾结点，和链栈一样，链队中也不会存在队满上溢出的情况。
结构图如下所示

我们以DataNode为链队类型，声明如下

typedef ElemType 数据类型
typedef struct qnode{
	ElemType data;
	qnode *next;
}DataNode;
//链队头结点的类型LinkQuNode声明如下
typedef struct{
	DataNode *front;
	DataNode *rear;
}LinkQuNode;	
1
2
3
4
5
6
7
8
9
10

在以q为链队结点指针的链队中，可以归纳出如下四个要素

1.队空的条件：q -> rear == NULL(或者 q -> front == NULL)
2.队满的条件：哈哈哈链队不需要考虑队满
3.元素e的进队操作：新建一个节点存放元素e（由p指向它），将结点p插入作为尾结点
4.出队操作：出去队首结点的data值并将其删除

那么在链队上对应队列的基本运算算法设计如下：

//1.初始化队列
void InitQueue(LinkQuNode *& q)
{
	q = new LinkQuNode;
	q -> front = q -> rear = NULL;
}
//2.销毁队列
void DestroyQueue(LinkQuNode *& q）
{
	DataNode *pre = q -> front, *p;
	if(pre)//即if(pre!=NULL)
	{
		p = pre -> next;
		while(p)
		{
			delete pre;
			pre = p;
			p = p ->next;
		}
		delete pre;		//释放最后一个数据结点
	}
	delete q;			//释放链队结点
}
//3.判断队列是否为空
bool QueueEmpty(LinkQuNode)
{
	return q -> rear = NULL;
}
//4.进入列队
void Push(LinkQuNode *& q,ElemType e)
{
	DataNode *p;
	p = new LinkQuNode;
	p ->data = e;
	if( q -> rear == NULL)
		q -> front = q -> rear = p;
	else
	{
		q -> rear -> next = p;
		q -> rear = p;
	} 
}
//5.出队操作
bool pop(LinkQuNode *&q,int &e)
{
	DataNode *p;
	if(q -> rear == NULL)
		return false;
	p = q -> front;
	if(q -> front == q -> rear)
		q ->front = q ->rear = NULL;
	else
		q -> front = q -> front -> next;
	e = p -> data;
	delete p;
	return true;
}	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

以上就是链队的基本操作的实现了。
返回目录

---

C++ 中的STL实现队列

C++的封装可以很方便实现一个队列和双端队列分别在头文件#include <queue>和#include <deque>中
下面我们来分别介绍队列和双端队列的基本操作

1.队列

#include <iostream>
#include <queue>
using namespace std;

int main()
{
	queue<int>q;//创建一个int类型的队列q
	q.push(3);  //将数字3压入队列中
	q.pop();    //弹出队尾元素
	int t = q.front();//将对首元素赋值给t
	int len = q.size();//将队列q的元素个数赋给len即求出队列的长度
	if(q.empty())//判断队列是否为空
	{
		cout << "Is empty!";
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.双端队列

#include <deque>//头文件
deque<int>q; //双端队列的声明
q.empty()//判断是否为空
q.pop_back()//从队尾弹出元素
q.pop_front()//从对头弹出元素
q.back()//取队尾元素
q.fornt()//取对头元素
q.push_back()//从队尾插入元素
q.push_front()//从对头插入元素
q.clear()//清空双端队列中元素
q.size()//返回向量中元素的个数
1
2
3
4
5
6
7
8
9
10
11

返回目录
以上就是我对队列的一个小小的总结，感谢你的阅读！