1. stack
1.1 栈的概念
数据结构与算法⑧(第三章_上)栈的概念和实现(力扣：20. 有效的括号)_GR C的博客-CSDN博客
① 栈是一种特殊的线性表，它只允许在固定的一端进行插入和删除元素的操作。
② 进行数据插入的删除和操作的一端，称为栈顶 。另一端则称为 栈底 。
③ 栈中的元素遵守后进先出的原则，即 LIFO原则（Last In First Out）。
压栈：栈的插入操作叫做 进栈 / 压栈 / 入栈 ，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
1.2 stack 的介绍和使用
https://cplusplus.com/reference/stack/stack/?kw=stack
stack 是一种容器适配器，（下一篇会讲解）专门用在具有后进先出操作的上下文环境中，
其删除只能从容器的一端进行 元素的插入与提取操作。
stack 是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，
并提供一组特定 的成员函数来访问其元素，将特定类作为其底层的，
元素特定容器的尾部(即栈顶)被压入和弹出。
标准容器 vector、deque、list 均符合这些需求，默认情况下，
如果没有为 stack 指定特定的底层容器， 则使用 deque。
stack 的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，
这些容器类应该支持以下操作：
empty：判空操作
back：获取尾部元素操作
push_back：尾部插入元素操作
pop_back：尾部删除元素操作
看看接口函数：
通过观察文档我们发现，接口相较于之前的 string、vector 和 list 少了很多。
它甚至连拷贝构造和析构都没有自己实现，然而这些都得益于容器适配器的使用。
不难发现， stack、queue 也没有迭代器，这也不难理解，
毕竟能让你随便遍历，不就破坏了栈和队列的原则了。
常用函数：
简单使用：
#include <iostream> #include <stack> using namespace std; void test_stack() { stack<int> st; st.push(1); st.push(2); st.push(3); st.push(4); st.push(5); cout << "st.size() = " << st.size() << endl; while (!st.empty()) { cout << st.top() << " "; // 后进先出 st.pop(); } cout << endl; } int main() { test_stack(); return 0; }
2. queue
2.1 队列的概念
数据结构与算法⑨(第三章_下)队列的概念和实现(力扣：225+232+622)_GR C的博客-CSDN博客
① 队列只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。② 入队列，进行插入操作的一端称为 队尾。出队列，进行删除操作的一端称为 队头。
③ 队列中的元素遵循先进先出的原则，即 FIFO 原则（First In First Out）
2.2 queue 的介绍和使用
https://cplusplus.com/reference/queue/queue/
队列是一种容器适配器，（下一章会讲解）专门用于在FIFO上下文(先进先出)中操作，
其中从容器一端插入元素，另一端 提取元素。
队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，
queue 提供一组特定的 成员函数来访问其元素。元素从队尾入队列，从队头出队列。
标准容器类 deque 和 list 满足了这些要求。默认情况下，
如果没有为 queue 实例化指定容器类，则使用标准容器 deque。
底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。
该底层容器应至少支持以下操作：
empty：检测队列是否为空
size：返回队列中有效元素的个数
front：返回队头元素的引用
back：返回队尾元素的引用
push_back：在队列尾部入队列
pop_front：在队列头部出队列
常用函数：
简单使用：
#include <iostream> #include <stack> #include <queue> using namespace std; void test_stack() { stack<int> st; st.push(1); st.push(2); st.push(3); st.push(4); st.push(5); cout << "st.size() = " << st.size() << endl; while (!st.empty()) { cout << st.top() << " "; // 后进先出 st.pop(); } cout << endl; } void test_queue() { queue<int> q; q.push(1); q.push(2); q.push(3); q.push(4); q.push(5); cout << "q.size() = " << q.size() << endl; while (!q.empty()) { cout << q.front() << " "; // 先进先出 q.pop(); } cout << endl; } int main() { test_stack(); test_queue(); return 0; }
3. 栈和队列的相关选择题
1. 下列代码的运行结果是（ ）
void main() { stack<char> S; char x, y; x = 'n';y = 'g'; S.push(x);S.push('i');S.push(y); S.pop();S.push('r');S.push('t');S.push(x); S.pop();S.push('s'); while (!S.empty()) { x = S.top(); S.pop(); cout << x; }; cout << y; }
A.gstrin
B.string
C.srting
D.stirng
2. 下列代码的运行结果是（ ）
void main() { queue<char> Q; char x, y; x = 'n';y = 'g'; Q.push(x);Q.push('i');Q.push(y); Q.pop();Q.push('r');Q.push('t');Q.push(x); Q.pop();Q.push('s'); while (!Q.empty()) { x = Q.front(); Q.pop(); cout << x; }; cout << y; }
A.gstrin
B.grtnsg
C.srting
D.stirng
3. 一个栈的输入顺序是a,b,c,d,e则下列序列中不可能是出栈顺序是( )
A.e,d,a,c,b
B.a,e,d,c,b
C.b,c,d,a,e
D.b,c,a,d,e
4. 以下是一个tree的遍历算法，queue是FIFO队列，请参考下面的tree，正确的输出是( )
1
2 3
4 5 6 7
queue.push(tree.root )
while(true)
node = queue.pop()
output(node.value)//输出节点对应数字
if(null==node)
break
for(child_node in node.children)
queue.push(child_node)
A.1376254
B.1245367
C.1234567
D.1327654
答案：
1. B
分析:S.push(x);S.push('i');S.push(y); 入栈了字母“nig” 左边栈底 右边栈顶
S.pop();S.push('r');S.push('t');S.push(x); 字母g出栈，然后入栈字母“rtn”，此时栈数据 为"nirtn"
S.pop();S.push('s');字母n出栈，s入栈，最终的栈数据为nirts
while(!S.empty()){} 栈不空出栈打印，按相反顺讯出栈，所以打印结果为：strin
cout<<y;最后还打印了字母g
2. B
分析：Q.push(x);Q.push('i');Q.push(y); 入队数据为:nig 左边对头，右边队尾
Q.pop();Q.push('r');Q.push('t');Q.push(x); n出队，rtn入队，队里数据为：igrtn
Q.pop();Q.push('s'); i出队，s入队，队里数据为：grtns
while(!Q.empty()){} 队不空，在出队打印为：grtns
cout<<y; 最后在打印一个g
3. A
分析：首先此题要保证入栈的顺序不能改变，其次，某个字母出栈前，必须把其栈顶的元素都要出栈
A:e要先出栈，就必须把a b c d e 全部入栈，然后e才能出栈，对于e d 的出栈没有问题，只是a要出栈，就必须c d 先出栈后，才能轮到a出栈，因此A是不可能得到的出栈顺序，其他答案可以自行验证
4. C
分析:此题是一个层次遍历的伪代码，能够看出是层次遍历，其结果就迎刃而解
从C语言到C++_18(stack和queue的常用函数+相关练习)力扣（中）：https://developer.aliyun.com/article/1521377
