stack是栈, 一种后进先出(Last In First Out)的容器, 它仅维护栈顶, 支持入栈(push), 查询栈顶(), 出栈(), 查询大小()操作。
常用于”单调栈”、”括号匹配”、”dfs”、”Tarjan求连通分量”、”波兰表达式(计算器)”等算法或数据结构中。
可以看作是一个弱化版的数组, 数组能做的 栈 不一定可以做, 栈可以做的数组一定可以做到。
初始化

stack<int> stk;     // 创建一个空栈, 栈不允许列表初始化或填充相同元素
// 但是可以从已有的栈进行拷贝构造
stack<int> stk2(stk);
stack<int> stk3 = stk2;

入栈

stk.push(10);       // stk = [10(top)]
stk.push(20);       // stk = [10, 20(top)]
stk.push(50);       // stk = [10, 20, 50(top)]
cout << stk.top() << '\n';      // 50, stk = [10, 20, 50(top)]
stk.pop();      // stk = [10, 20(top)]
cout << stk.top() << '\n';      // 20, stk = [10, 20(top)]

取出栈顶元素
在c++中，top()函数仅仅是取出栈顶元素, 不会将栈顶元素pop()掉, 请注意!

cout << stk.top() << '\n';      //50, stk = [10, 20, 50(top)] 

出栈

//弹出栈顶元素, 注意判断非空!
if(stk.size()) stk.pop();       // stk = [10, 20(top)]
cout << stk.top() << '\n';      // 20, stk = [10, 20(top)]

获取栈大小(元素个数), 判空

cout << stk.size() << '\n';
if(stk.empty())...      //栈为空

清空栈

while(stk.size()) stk.pop();    //时间复杂度O(n)

在stack中不允许遍历, 但是如果我们手写栈(或者干脆用vector好了), 就可以实现这个功能
手写栈
手写栈非常简单, 用一个top变量表示栈顶下标即可, 以下标1作为栈底

int stk[N], top = 0;

//入栈
stk[++ top] = x;
//出栈
top --;
//取出栈顶元素
cout << stk[top] << '\n';
//获取大小
cout << top << '\n';
//判断是否为空
if(top)... //栈非空
//遍历栈
for(int i = 1; i <= top; ++ i)...
//甚至可以在单调栈上进行二分