数据结构 —— 队列_数据结构的应用场景中,与食堂排队打饭、收银台排队付款相对应的数据结构是树结构

队列
1.队列的介绍
队列是一种先进先出的数据结构，这和栈有所不同，但又更容易理解。类似于食堂排队打饭，车站排队买票。
后来的人排在队伍最后边，先来的人先打饭或者买票走。如图

队列总是从队尾插入元素,而从队首移除元素，满足先进先出的规则。因此需要一个队首指针front指向队首元素的前一个位置，而使用一个队尾指针rear来指向队尾元素。
，需要一个队首指针front来指向队首元素的前一个位置，而使用一个队尾指针rear来指向队尾元素。和栈类似，当使用数组来实现队列时，队首指针front和队尾指针rear为int型变量(数组下标从0开始);而当使用链表来实现队列时，则为int*型变量的指针。这样当使用数组来实现上面的例子时，队首指针front和队尾指针rear的指向情况如图7-3所示。接下来介绍队列的常用操作，包括清空(clear)、 获取队列内元素的个数(size)、 判空(empty)、入队(push)、 出队(pop)、取队首元素(get_ front). 取队尾元素(get _rear) 等。下面将使用数组q[ ]来实现队列，而int型变量front存放队首元素的前一个元素的下标、rear存放队尾元素的下标(数组下标从0开始)。下面对常见操作进行示范实现:

(1)清空(clear)

使用数组来实现队列时，初始状态为front=-1、rear=-1, 前面的图中第一步rear指向0是因为此时队列中已经有一一个元素了，如果没有元素，rear 应当是指向-1位置的。

void clear()
{
    front=rear=-1;
}
1
2
3
4

(2) 获取队列元素的个数（size）
显然 rear-front即为队列元素的个数，从上图很容易看出。

int size()
{
    return rear-front;
}
1
2
3
4

(3)判空（empty）
判断队列为空的条件为front==rear.

bool empty()
{ 
  if(front==rear) return true;
  else return false ;
}
1
2
3
4
5

(4) 入队（push）
由于队尾指针rear指向队尾元素，因此把元素入队时，需要先把rear加1，然后再存到rear指向的位置。

void push(int x)
{
  q[++rear]=x;
}
1
2
3
4

(5)出队（pop）
可以直接把队首指针加1来实现出队的效果。

void pop()
{
   front++;
}
1
2
3
4

(6)取队首元素（get_front）
由于队首指针front指向的是队首元素的前一个元素，因此front+1才是队首元素的位置。

int get_front()
{
   return q[front+1];
}
1
2
3
4

(7)取队尾元素，队尾指针指向的是队尾元素，因此可以直接访问rear的位置。

int get_rear()
{
   return q[rear];
   }
1
2
3
4

当然这里我更习惯于另一种写法
给出 模板

//front表示队头，rear表示队尾
int q[N],front = 0, rear = -1;
//向队尾插入一个数
q[++rear] = x;
//从队头弹出一个数
front++;
//队头的值
q[front];
//队尾的值
q[rear];
//判断队列是否为空
if (front <= rear)
{
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

实现一个队列，队列初始为空，支持四种操作：

(1) “push x” – 向队尾插入一个数x；

(2) “pop” – 从队头弹出一个数；

(3) “empty” – 判断队列是否为空；

(4) “query” – 查询队头元素。

现在要对队列进行M个操作，其中的每个操作3和操作4都要输出相应的结果。

输入格式
第一行包含整数M，表示操作次数。

接下来M行，每行包含一个操作命令，操作命令为”push x”，”pop”，”empty”，”query”中的一种。

输出格式
对于每个”empty”和”query”操作都要输出一个查询结果，每个结果占一行。

其中，”empty”操作的查询结果为“YES”或“NO”，”query”操作的查询结果为一个整数，表示队头元素的值。

数据范围
1≤M≤100000,
1≤x≤109,
所有操作保证合法。

输入样例：
10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6
输出样例：
NO
6
YES
4

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
const int maxn = 1e5 + 10;
int q[maxn],hh=0,tt=-1;
int main()
{
	int M;
	cin >> M;
	while (M--)
	{
		string order;
		int x;
		cin >> order;
		if (order == "push")   //插入
		{
			cin >> x;
			q[++tt] = x;
		}
		else if (order == "query") //查询队头
		{
			cout << q[hh] << endl;
		}
		else if (order == "pop")  //弹出队头
		{
			hh++;
		}
		else
		{
			if (hh <= tt)
			{
				cout << "NO" << endl;
			}
			else
			{
				cout << "YES" << endl;
			}
		}
	}
	return 0;
}
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

STL
(1) push()
push(x)将x进行入队，时间复杂度为0(1).
(2)front()和back()
front()和back()可以分别获得队首元素和队尾元素，时间复杂度为O(1)
(3)pop()
pop()令队首元素出队，时间复杂度为O(1)。

#include<iostream>
#include<queue>
using namespace std;
int main()
{
	queue<int>q;
	for (int i = 1; i <= 5; i++)
	{
		q.push(i);  //将1 2 3 4 5 依次入队
	}
	for (int i = 1; i <= 3; i++)
	{
		q.pop();   //将 1 2 3 依次出队
	}
	cout << q.front() << endl; //输出4
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

(4) empty()
empty()检测队列是否为空，为空返回true,否则返回false，时间复杂度为O(1)。
(5)size()
size()返回queue内元素的个数，时间复杂度为O(1)。

#include<iostream>
#include<queue>
using namespace std;
int main()
{
	queue<int>q;
	for (int i = 1; i <= 5; i++)
	{
		q.push(i);
	}
	if (q.empty() == true)
	{
		cout << "NO" << endl;  //队列非空
	}
	cout << q.size() << endl;   //输出5
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

优先队列
priority_ _queue 又称为优先队列，其底层是用堆来进行实现的。在优先队列中，队首元素一定是当前队列中优先级最高的那一个。例如在队列有如下元素，且定义好了优先级:

桃子(优先级3)
梨子(优先级4)
苹果(优先级1)

那么出队的顺序为梨子(4) →桃子(3)→苹果(1)。

当然，可以在任何时候往优先队列里面加入(push)元素，而优先队列底层的数据结构堆(heap)会随时调整结构，使得每次的队首元素都是优先级最大的。

关于这里的优先级则是规定出来的。例如上面的例子中，也可以规定数字越小的优先级越大(在德国课程中，评分1分为优秀，5、6分就是不及格了)。

1. priority_ _queue 的定义

要使用优先队列，应先添加头文件#include ， 并在头文件下面加上“usingnamespace std;"，然后就可以使用了。

其定义的写法和其他STL容器相同，typename 可以是任意基本数据类型或容器:priority_ queue< typename > name;

2. priority_ queue 容器内元素的访问

和队列不一样的是， 优先队列没有front()函数与back()函数，而只能通过top(()函数来访问队首元素(也可以称为堆顶元素)，也就是优先级最高的元素。

#include <stdio.h>

#include <queue>

using namespace std;

int main() {

priority_ queue<int> q;

q.push(3) ;

q.push(4);

q.push(1);

printf("%d\n", q.top());   //输出4

return 0;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

有关优先队列的知识点随后补充。