栈stack
#include<stack>
定义
通过二次封装双端队列(deque)容器，实现先进后出的栈数据结构
仅维护栈顶(top)，支持入栈(push)，查询栈顶(top)，查询大小(size)操作。常用于“单调栈”，“括号匹配”，“dfs”，“Tarjan求强连通分量”，“波兰表达式(计算器)”等算法和数据结构中。
常用方法
| 作用 | 用法 | 示例 |
构造 | stack<类型> stk | stack<int> stk; |
| 进栈 | .push(元素) | stk.push(1) |
| 出栈 | .pop( ) | stk.pop( ) |
| 取栈顶 | .top( ) | int a=stk.top() |
| 大小 | .size( ) | int a=stk.size( ) |
| 判空 | .empty( ) | stk.empty( ) |
初始化
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()<<endl;//50 stk.pop();//stk=[10,20(top)] cout<<stk.top()<<endl;//20栈是一种线性结构，可以把它看做一种“弱化版”的数组，他只能在栈顶进行数据的操作，而栈内部的元素都是不可能被访问的
取出栈顶元素
在c++中，top( )函数仅仅是取出栈顶元素，不会将栈顶元素pop()掉
cout<<stack.top()<<'\n';//50,stk=[10,20,50(top)]出栈
//弹出栈顶元素，注意判断非空 if(stk.size()) stk.pop();//stk=[10,20(top)] cout<<stk.pop()<<'\n';//20,stk=[10,20(top)]获取栈大小(元素个数)，判空
cout<<stk.size()<<'\n'; if(stk.empty())……//栈为空清空栈
while(stk.size()) stk.pop();在stack中不允许遍历，但是如果我们手写栈（或者直接用vector），即可实现
手写栈
用一个top变量表示栈顶下标即可，以下标1作为栈底
int stk[N],top=0; //入栈 stk[++top]=x; //出栈 top--; //取出栈顶元素 cout<<top<<'\n' //获取大小 cout<<top<<'\n' //判断是否为空 if(top)……//栈非空 //遍历栈 for(int i=1;i<=top;i++)…… //甚至可以在单调栈上进行二分
