队列详解
infinite2021 · · 个人记录
队列详解
1.谈谈队列
什么是队列？
相信这是刚开始学习队列的同学的第一个问题
队列这个名字源于生活，例如当我们去食堂排队打饭时，所形成的就是一个队列
本章我们将引进一个新的概念——————数据结构
何为数据结构？你可以看成数据结构就是数组的变形，本质上数组也是一种数据结构，而其他的数据结构则会让解决某些题目更加简便
下面我们来看一下队列的概念
前置知识队列
2.队列基本操作
1.向队尾插入一个数(push)
2.从队头弹出一个数(pop)
3.判断队列是否为空(empty)
4.查询队头元素(query)
上述就是队列的基本操作
可是，现在有一个问题，如何实现队列呢？
(1)数组模拟
用数组模拟是一种不错的方法，而数组模拟的是队列先进先出(你排队时后进先出试试看)的思想
我们用两个指针(变量)hh,tt来模拟
hh表示的是队头(第一个)元素，tt表示的是队尾(最后一个)元素
先来解决push操作
push操作只需在数组的最后加上一个元素，并把tt+1即可
即：q[++tt]=x//x为插入元素
pop更加简便，因为是删除队头元素，只需把hh+1即可
hh++
判断队列非空hh,tt这两个指针都需要用到，判断hh是否≤tt即可(不贴代码了)
查询即输出q[hh]即可
(2)STL
这里讲一下STL队列的定义
假如要定义一个整型队列q
就是queue<int>q
而四种基本操作就变成了
1.q.push(x)
2.q.pop()
3.q.empty()
4.q.front()
再次强调，初学者先不要用STL，尽量用数组模拟，来熟悉队列的思维