当前位置：网站首页>队列与栈

队列与栈

2022-08-02 14:10:00 【WANGHAOXIN364】

前置知识：数组+模拟
为了保证学习效果，请保证已经掌握前置知识之后，再来学习本章节！

知识总览

队列是一种模拟现实生活中排队过程的线性数据结构，具有先入先出的特点
队列支持入队、出队、求队列长度、判空等操作，不支持遍历操作
队列的基础实现有两种，STL queue 和数组模拟队列，各有优缺点

q.size()

q.empty()

q.front() / q.back()

q.pop()

q.push(element)

STL queue

数组模拟：一个数组 + 两个指针

求大小

判队空

取队首 / 队尾

出队：将当前队首元素移除队列，其后面的元素成为新的队首

入队：将某元素放到当前队列末尾，成为新的队尾

队尾：排在队列末尾的元素

队首：排在队列最前端的元素

定义：模拟现实生活中的队列

注意：取队首和出队前一定要保证队列不空

实现

操作

基本概念

队列

问题引入

上面“拓尔思舞会-1”这个问题用普通数组模拟就可以，那么下面“拓尔思舞会-2”这个问题呢？数组模拟也很麻烦。

类似这种需要处理元素排队的过程，“队列”这种数据结构就派上了用场。

队列的原理

队列是一种操作受到限制的线性表，用于模拟类似生活中的排队类型的数据结构，它支持在一端插入元素，在另外一端删除元素。

模拟现实生活中的排队过程。若干对象排成一条线性的队伍，等待某种操作（结账、处理银行业务、看病打针等等）。只有队首才能进行某种操作。队首对象处理完后，排在队首后面的人成为新的队首，然后才可以进行某种操作。

因此，队列有下列几种概念：

（1）队首：队列中的第一个元素

（2）队尾：队列中的最后一个元素

（3）队列长度/大小：队列中的元素个数

（4）队列判空：判断队列是否为空

（5）取队首：取得队首元素的值，注意，队列为空时，取队首操作是非法的

（6）入队：向队列尾部添加一个元素

（7）出队：队首元素移出队列，注意，队列为空时，出队操作是非法的

转存失败重新上传取消

队列的操作

想一想生活中排队可能会出现哪些过程？

加入队列：有一个人也想去排队，就要加入进去，并且排到队列的尾部，也就是当前队列的最后一个人的后面。（插队？不允许的，非法操作！）
出队操作：队首元素离开队列
求队列大小：队列中元素的个数
判断队列为空：
获取队首元素
获取队尾元素

代码实现

速记：一个数组+两个指针，队首指针，队尾指针，指针永远只会向前移动

方法一、使用数组+变量

int q[1000];            // 定义一个最大历史容量是 1000 的队列
int head=0, tail=0;     // 定义队列头 队列尾，初始值依个人习惯而设

int len = tail - head;   // 获取队列的长度
if(head == tail)         // 判断队列为空
int h = q[head];         // 取队首
q[tail++] = t;           // 将 t 入队
head++;                  // 队首出队，前提是队列不为空

Copy

方法二、STL 队列 queue

queue<int> q;            // 定义一个空队列
int len = q.size();      // 获取队列的长度
if(q.empty())            // 判断队列为空
int h = q.front();       // 取队首
int t = q.back();        // 取队尾
q.push(t);               // 将 t 入队
q.pop();                 // 队首出队，前提是队列不为空   
......                   // 更多 STL 队列的使用方法可自行百度

Copy

对比

属性和操作	手写队列	STL队列
头文件	无	#include
定义(重点)	int a[100], head = 0, tail=0; // 队列大小为100	queue a;
队列的大小(重点)	int size = tail - head;	int size = a.size();
判空	head == tail // 表示队列为空	a.empty() == true // 表示队列为空
取队首	a[head] // 前置条件：队列不为空 head != tail	a.front() // 前置条件：队列不为空 !a.empty()
入队	a[tail++] = t; // 将 t 入队	a.push(t); // 将 t 入队
出队	head++; // 前置条件：队列不为空	a.pop(); // 前置条件：队列不为空 !a.empty()
清空队列	head =tail=0；	a = queue (); // 或将一个空队列复制给 a
优点	运行速度快，使用灵活，可以遍历队列元素、修改队列元素	定义方便，不用关心队列的大小限制
缺点	书写稍微麻烦，入队次数有限	运行速度比手写队列慢一些，操作完全受限