深入理解 C++ 中的栈和队列
Yubo Feng
全栈学习者 / 五年级小学生 / c++进阶者
前言
数据结构(data)是一个庞大的结构,本篇记录了最基础的数据结构栈(stack)和队列(queue)的基础原理，也记录了我从蛙声一片到AC的记录，话不对说，我们开始吧！
栈
栈(stack)是一种后进先出的数据结构(LIFO)，栈的元素只能从栈的顶部添加或删除，栈的顶部称为栈顶，栈的底部称为栈底。栈的元素只能从栈的顶部添加或删除，栈的顶部称为栈顶，栈的底部称为栈底。栈的元素只能从栈的顶部添加或删除，栈的顶部称为栈顶，栈的底部称为栈底。栈的元素只能从栈顶进行添加或删除。
让我们来看题
题目描述
输入 n，紧接着需要进行 n 次操作，第 i 次操作为：“opi, xi”
- 如果 opi = 1，表示需要把 xi 压入栈。
- 如果 opi = 2，忽略 xi，表示需要输出当前栈顶元素。如果此时栈内没有元素，则输出 -1。
- 如果 opi = 3，忽略 xi，表示需要弹出栈顶元素。如果此时栈内没有元素，则忽略此次操作。
输入格式
第一行一个整数 n。
接下来 n 行，每行都是空格隔开的两个整数，第 i 行为：“opi, xi”。
输出格式
对每个操作 2，输出一行一个整数，即这个操作的答案。
输入数据
7 1 2 1 3 2 1 1 5 2 1 3 1 2 1
输出数据
3 5 3
数据规模与约定
对于 100% 的数据，保证 1 ≤ n ≤ 100，1 ≤ opi ≤ 3，1 ≤ xi ≤ 1000。
这里提供2种解法：
- 手写代码
- 借助STL库中的数据结构（设置好了函数及变量）
我们先看手写栈
1.注意弹出时判断是否空栈，是就输出-1
2.我们定义长度变量size就可以完成栈先进后出的操作了
3.输出栈顶元素时我们可以直接输出数组的最后一位，我们已经有size了，可以处理
想要代码？点这里窝们继续看第二种解法
STL库中的栈的常规用法
栈的基本操作:
push()- 在栈顶添加元素pop()- 移除栈顶元素top()- 获取栈顶元素empty()- 检查栈是否为空size()- 获取栈中元素的数量
这种代码较为简单，请各位记住,就不看代码了
队列
队列是一种先进先出的结构，比较像窝们买冰激凌时派对的时候，入队时加入最后，出队时有2种办法 1.空间换时间（指设定strat，为开始在下标是几的位置，出队时输出并进行递增操作，看起来像“删除”了） 2.时间换空间（指挪位值，最终队列新的元素开头），当然可能也有其他方法，蒟蒻还不知道，神犇们可以写电子邮件告诉我:)
队列的题
题目描述
输入 n，紧接着需要进行 n 次操作，第 i 次操作为：“opi, xi”
- 如果 opi = 1，表示需要把 xi 压入队列。
- 如果 opi = 2，忽略 xi，表示需要输出当前队头元素。如果此时队列内没有元素，则输出 -1。
- 如果 opi = 3，忽略 xi，表示需要弹出队头元素。如果此时队列内没有元素，则忽略此次操作
输入格式
第一行一个整数 n。
接下来 n 行，每行都是空格隔开的两个整数，第 i 行为：“opi, xi”。
输出格式
对每个操作 2，输出一行一个整数，即这个操作的答案。
输入数据
7 1 2 1 3 2 1 1 5 2 1 3 1 2 1
输出数据
2 2 3
数据规模与约定
对于 100% 的数据，保证 1 ≤ n ≤ 100，1 ≤ opi ≤ 3，1 ≤ xi ≤ 1000。
这里仍然提供2种方法
1.手写
2.使用STL库进行制作
手写代码需要注意队列是先进先出的
不会？看这里！STL库是需要引的（万能头不用）
队列的基本操作（STL库中）:
push()或enqueue()- 在队尾添加元素pop()或dequeue()- 移除队首元素front()- 获取队首元素back()- 获取队尾元素empty()- 检查队列是否为空size()- 获取队列中元素的数量
相信已经很简单了