栈和队列

作者：寂-作业逆行者发布时间：2024-10-04

栈是一种单口进出的线性表，遵循先进后出、后进先出的原则，可以类比桶；队列是一种单向双口进出的线性表，遵循先进先出、后劲后出的原则，可以类比排队的队列。栈和队列可以用数组模拟，也可以用STL模版生成，可以解决很多实际问题。

栈的定义和原理

栈是一种单口进出的线性表，遵循先进后出（FILO，First In Last Out）、后进先出的原则（因此，栈又被称为“先进后出表”），可以类比桶。在桶中，只有一个口（桶顶）负责进出，同时先放入的物品在拿取时最后才拿取。这和C++的数据结构栈非常相像。栈是一种数据结构，和队列、链表属于同一类，用于有一定顺序地串联各项数据。

下面阐述栈的各项操作及其概念：

栈顶：栈的顶部，即栈的最高下标。

栈底：栈的底部，即栈的最低下标。

栈顶元素：位于栈顶的元素。

栈底元素：位于栈底的元素。

入栈：将元素添加到栈顶。

出栈：将栈顶元素删除。

栈长度：即栈内元素个数。

满栈：栈中无法再添加元素，即元素个数到达极限。

空栈：栈中没有元素。

使用数组模拟栈

栈可以使用我们常见的数据类型——数组进行模拟。

1. 构建栈。创建一个长为N的数组a，模拟栈体。创建top变量初始化为0，模拟栈顶下标。此时栈的最大长度为N。

2. 入栈。创建入栈函数push()，传入参数int x，代表传入值。top自增1，代表栈顶上移1；a数组的top下标处存入数值x，即可实现入栈操作。

注意：在满栈时无法继续入栈。

3. 出栈。创建出栈函数pop()，无需传值。a数组的top下标处归0，top自减1，代表栈顶下移1，即可实现出栈操作。

注意：在空栈时无法继续出栈。

$a%5Btop%5D%3D0%3B$ 一步不是必须的，因为每次入栈时该下标元素就会重置。但是，为了模拟栈的原理便于理解，这里我们添加该步，各位犇犇们可以按照自己的书写习惯选择适合的模拟方法。

4. 取栈顶元素。创建取栈顶函数getTop()，无需传值。直接返回a数组top下标的元素值。

5. 取栈长度。创建取栈长度函数size()，无需传值。直接返回top即可。

6. 判断栈是否为空。创建判断栈空函数empty()，无需传值。返回top==0的布尔结果。

以上就是数组模拟栈的功能。可能有点肝，但是在某些比赛中这是必备的【简单模拟】技能。挠着头皮看到这里的犇犇们，下面就是你们的轻松时间。

使用STL模版模拟栈

使用数组模拟栈是一个高难度动作，所以人类发明了STL模版，用来简化栈的操作。

下面介绍使用STL模板模拟栈的过程。

1. 构建栈。s为栈名，可自行更改，命名规则参照变量的命名规则。数据类型可以是基本数据类型、类对象数据类型（如字符串）、自定义数据类型（结构体、联合体等）。

2. 入栈。注意，STL栈是可以无限添加元素的，这是通过vector实现的。但是，添加数据x的类型必须和栈的数据类型匹配。

3. 出栈。没有任何参数，删除栈顶元素。

注意：栈空时不可出栈，否则会报错。

4. 取栈顶元素。

注意：栈空时不可取栈顶元素，否则会报错。一般说来，在取栈顶元素时，会首先判断栈是否为空。

5. 取栈长度。

注意：栈空时不可取栈长度，否则会报错。

6. 判断栈是否为空。

注意：栈为空时，函数返回1；栈不为空时，函数返回0。

$%3Cstack%3E$ 头文件（万能头者无视）。

队列的定义和原理

队列是一种双口分别进出的线性表，遵循先进先出（FIFO，First In First Out）、后进先出的原则（因此，队列又被称为“先进先出表”），可以类比排队的队列。在队列中，有两个口（队首和队尾）分别负责进出，同时先来排队的人先参加活动/办理业务。这和C++的数据结构队列非常相像。

下面阐述队列的各项操作及其概念：

队首：队头，即第一个入队的元素所在位置。

队尾：队尾，即最后一个入队的元素所在位置。

队首元素：位于队首的元素。

队尾元素：位于队尾的元素。

入队：将元素添加到队尾。

出队：将队首元素删除。

队列长度：即队内元素个数。

满队列：队列中无法再添加元素，即元素个数到达极限。

空队列：队列中没有元素。

使用数组模拟队列

栈可以使用我们常见的数据类型——数组进行模拟。

1. 构建栈。创建一个长为N的数组a，模拟队列。创建front, rear变量初始化为0，模拟队首和队尾。此时队列的最大长度为N。

2. 入队列。创建入队列函数push()，传入参数x，代表传入值。rear自增1，代表队尾上移1；a数组的rear下标处存入数值x，即可实现入队列操作。

注意：在满队列时无法继续入队列。

3. 出队列。创建出队列函数pop()，无需传值。a数组的front下标处归0，front自增，代表队首上移1，即可实现出队列操作。判断是否为空队列的方法即为判断front是否与rear相等。

注意：在空队列时无法继续出队列。

$a%5Bfront%5D%20%3D%200%3B$ 一步不是必须的，因为每次出队列时该下标元素再也不会使用了（详见假上溢）。但是，为了模拟队列的原理便于理解，这里我们添加该步，各位犇犇们可以按照自己的书写习惯选择适合的模拟方法。

4. 取队首元素。创建取队首函数getFront()，直接返回a数组front下标的元素值。

5. 取队尾元素。创建取队尾函数getRear()，直接返回a数组rear - 1下标的元素值。

6. 取队列长度。创建取队列长度函数size()，无需传值。直接返回rear - front即可。

7. 判断队列是否为空。创建判断队列空函数empty()，返回front == rear的布尔结果。

以上就是数组模拟队列的功能。

队列溢出和真假上溢

当队列元素超出数组限制时，就发生了溢出。溢出分三种类型：

上溢。当rear下标到达数组最大下标限制时继续执行入队列操作，就会发生上溢。
下溢。当front == rear，即队列空时继续执行出队列操作，就会发生下溢。

上溢还分两种类型：真上溢和假上溢。

真上溢。当front等于0，rear到达数组最大下标限制时继续执行入队列操作，就会发生真上溢。发生真上溢时，数组内所有下标处均填充了元素，没有任何可以利用的空间。
假上溢。当front不等于0，rear到达数组最大下标限制时继续执行入队列操作，就会发生假上溢。发生假上溢时，front下标前的空间没有元素（实际上没有爆数组，所以称为假上溢），浪费了很多空间。

由此可以看出，假上溢会造成空间浪费。于是，建议使用STL模版模拟队列或使用循环队列。

使用STL模版模拟队列

下面介绍使用STL模板模拟队列的过程。

1. 构建队列。q为队列名，可自行更改，命名规则参照变量的命名规则。数据类型可以是基本数据类型、类对象数据类型（如字符串）、自定义数据类型（结构体、联合体等）。

2. 入队列。注意，STL队列是可以无限添加元素的，这也是通过vector实现的。但是，添加数据x的类型必须和队列的数据类型匹配。

3. 出队列。没有任何参数，删除队首元素。

注意：队列空时不可出队列，否则会报错。

4. 取队首元素。

注意：队空时不可取队首元素，否则会报错。

警告：std::queue的STL类不提供取队尾元素的函数！

5. 取队列长度。

注意：队列空时不可取队列长度，否则会报错。

6. 判断队列是否为空。

注意：队列为空时，函数返回1；队列不为空时，函数返回0。

$%3Cqueue%3E$ 。

双端队列

上文提到，std::queue容器不提供取队尾元素的函数，并且只能队尾入队，队首出队，非常的不方便。双端队列解决了这个问题。双端队列（std::deque）提供两个进出均可的口（队首、队尾），并提供取队尾元素的函数 $back()$ ，是对于队列双端操作的最优解。

下面示范用STL模版模拟双端队列。概念同队列概念。

1. 构建双端队列。dq为队列名，参考队列的创建方式。

2. 从队尾入队。参照队列要求。

3. 从队首入队。参照队列要求。

4. 从队首出队。参照队列要求。

5. 从队尾出队。参照队列要求。

6. 取队首元素。参照队列要求。

7. 取队尾元素。参照队列要求。

8. 取队列长度。参照队列要求。

9. 判断队列是否为空。参照队列要求。

$%3Cdeque%3E$ 。

优先队列

观察以下题目：

聪明的犇犇们已经想到了：

那就是使用sort函数进行排序。

但是，现在请跟着我计算一下时间复杂度。

sort函数默认使用快速排序对数组进行排序，采用分治法，所以其时间复杂度为 $O(n%5Clog_2%20n)%20$ ，再加上前后的输入输出需要 $O(n)$ 的时间复杂度，综合考虑，上述算法的时间复杂度为：

$O(n%2Bn%5Clog_2%20n%2Bn)%3DO(n%5Clog_2%20n)$

$1%20%5Cleq%20n%20%5Cleq%2010%5E5$ 时，循环次数最高即为：

$10%5E5%2B10%5E5%5Ctimes%20%5Clog_2%2010%5E5%2B10%5E5%3D700000$

这么炸裂的循环次数，放在哪个OJ都会TLE（Time Limit Exceeded）的……

那么，让我们来了解一下优先队列吧！

优先队列（std::priority_queue）允许我们从队尾插入元素，并从队首取出元素。其特殊之处在于，优先队列可以保持队列中的元素以从大到小的顺序排列，不需要手动排序，无论如何入队，可以自动保持！构建优先队列的格式为：

pq为队列名，参照队列命名方式。

其它方法参照队列要求（入队push()，出队pop()，队首front()，长度size()和判空empty()）。

需要注意，和sort类似的是，当我们需要让优先队列从小到大或者结构体排序时，构建优先队列的格式就会变为：

数据类型不用解释了吧，参照队列。

实现方法就是优先队列自动排序的底层实现，有动态数组 $vector%20%3Cpq%E7%9A%84%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B%3E$ 和双端队列 $deque%20%3Cpq%E7%9A%84%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B%3E$ 两种选择，区别不大，自行选择。