关于c++:CSTL教程3stack栈入门简明教程小白都能理解

在学习之前，先理解一下什么是stack。

std::stack 类是容器适配器，它给予程序员栈的性能——特地是 FILO（先进后出）数据结构。
该类模板体现为底层容器的包装器——只提供特定函数汇合。栈从被称作栈顶的容器尾部推弹元素。

FILO指的是 First In Last Out，也就是说第一个进来的，是最初一个进来的。咱们能够将stack 了解为一个上端闭口的铁箱子，咱们能够从顶部拿出物品或放入物品，且记录物品个数。

stack仅保护一个栈顶，意味着咱们只能从一端对数据进行操作。

本文仅从入门和实用角度介绍 queue 的用法，次要针对初学者或比赛向。如有不谨严的中央欢送斧正！

初始化

在应用 stack 之前，须要先引入头文件。

#include <stack>

初始化的语法如下：

stack<T> stk;// T 为数据类型

stack<int> stk_int;// 申明一个栈，寄存类型为 int

和其余的 stl 容器一样，stack只能寄存雷同类型的元素，默认初始化为空栈。

入栈

stk.push(x)将元素 x 推入栈 stk 的栈顶，复杂度O(1)。

每入栈一个新元素，会使得栈的大小 +1。

// 右边为栈顶
// stk: empty

stk.push(1);
// stk : 1

stk.push(5);
// stk : 5 1

还有一种办法是用 emplace() 函数进行入栈，两者差异能够临时疏忽。

stk.emplace(7);
// stk : 7 5 1

出栈

stk.pop()将 stk 的栈顶元素弹出栈，复杂度O(1)。

// stk : 7 5 1

stk.pop();
// stk : 5 1

stk.pop();

// stk : 1

在出栈时要留神栈是否为空，空栈不容许出栈。这和 queue 出队相似，感兴趣的能够看看这篇文章：https://www.eriktse.com/technology/1063.html

你问一个人“push”的反义词是什么？如果他答复“pop”那他肯定是程序员。（答案兴许是“pull”）

获取栈顶元素

语法：stk.top()能够获取栈顶元素，然而不会主动将栈顶元素弹出。须要自行pop()。复杂度O(1)。

// stk : 7 5 1

cout << stk.top() << '\n';// 7

留神获取栈顶元素的时候也须要保障栈不为空，否则将导致谬误！

获取栈的大小

语法：stk.size()，返回值为一个非负整数，当返回 0 时示意栈为空，复杂度O(1)。

// stk : 1
cout << stk.size() << '\n';// 1

stk.push(9);
// stk : 9 1
cout << stk.size() << '\n';// 2

本文由 eriktse 原创，未经容许禁止转载！

判断栈是否为空

语法：stk.empty()，返回值为一个 bool 值，当返回 true 时示意栈为空，当返回值为 false 时示意栈非空。复杂度O(1)。

// stk : 9 1
cout << st.empty() << '\n';// false
stk.pop(), stk.pop();
// stk : empty
cout << st.empty() << '\n';// true

当然你也能够用 stk.size() == 0 来判断栈是否为空。

清空栈

和清空 queue 相似，stack没有 clear() 函数，然而能够通过多种方法来实现。

// 办法一：只有栈不为空就始终弹出，直到为空
while(!stk.empty())stk.pop();

// 办法二：间接赋值一个新的 stack，默认为空栈
stk = stack<int>();

替换栈

语法：stk1.swap(stk2)，返回值为void()，复杂度O(1)。

stack<int> s, t;
s.emplace(1);
t.emplace(2);
cout << s.top() << '\n';// 1
s.swap(t);
cout << s.top() << '\n';// 2

罕用函数总结

• push(x)将元素 x 入栈
• emplace(x)在栈顶结构元素 x，并入栈（能够简略了解 push()和 emplace()差异不大）
• pop()无参数，将栈顶元素弹出
• size()返回栈的大小（元素个数）
• empty()返回 bool 值示意栈是否为空
• stk1.swap(stk2)替换两个栈

补充常识

栈在解决一些问题的时候十分好用，比方在做 深度优先搜寻 dfs的时候，须要须要用到栈的思维，其中节点的遍历程序能够用栈程序示意。

同时利用栈能够结构一些非凡的数据结构比方 枯燥栈 从而求出一些非凡的货色，比方 最大回升 / 降落子序列 ，从而优化一些dp 问题。