【数据结构】—栈

Stack 简介

栈是 OI 中常用的一种线性数据结构，请注意，本文主要讲的是栈这种数据结构，而非程序运行时的系统栈/栈空间。
栈的修改是按照后进先出的原则进行的，因此栈通常被称为是后进先出（last in first out）表，简称 LIFO 表。

在c++ 中,stack的头文件是 #include <stack>

stack 的使用

1、使用数组模拟栈

int st[N];
// 这里使用top=0表示栈顶下标
// 压栈 ：
st[++top] = var1;
// 取栈顶 ：
int u = st[top];
// 弹栈 ：注意越界问题, top == 0 时不能继续弹出
if (top) --top;
// 清空栈
top = 0;

2、使用STL中的stack容器

STL 中的 stack 容器提供了一众成员函数以供调用，其中较为常用的有：
元素访问
st.top() 返回栈顶

修改
st.push() 插入传入的参数到栈顶
st.pop() 弹出栈顶

容量
st.empty() 返回是否为空
st.size() 返回元素数量

也可使用 = 为stack 赋值
// 新建两个栈 st1 和 st2
stack<int> st1, st2;
// 为 st1 装入 1
	st1.push(1);
// 将 st1 赋值给 st2
	st2 = st1;
// 输出 st2 的栈顶元素
	cout << st2.top() << endl; 
	

例题：

表达式括号匹配
【题目描述】
假设一个表达式有英文字母（小写）、运算符（+，—，*，/）和左右小（圆）括号构成，以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“NO”。表达式长度小于255，左圆括号少于20个。

【输入】
一行数据，即表达式。

【输出】
一行，即“YES” 或“NO”。

【输入样例】
2*(x+y)/(1-x)@

【输出样例】
YES