栈的应用场景非常广泛，包括代码中的解析、数据结构中的树和图的遍历以及计算机系统中的内存分配等等。下面会介绍栈。
1.基本知识
1.1 介绍
C++的栈是一种数据结构，它是一个后进先出（LIFO）的线性结构，具有两个基本操作：push和pop。push操作将数据压入栈顶，而pop操作将栈顶数据弹出。C++中的栈实现在STL中，可以使用std::stack来创建一个栈。
std::stack可以被视为一种容器适配器，它基于其他容器实现，例如std::deque和std::list。默认情况下，std::stack基于std::deque实现，因为它具有高效的随机访问和在两端进行插入和删除元素的能力。
在C++中，栈通常用于实现函数调用堆栈和表达式求值等场景。当一个函数被调用时，它的返回地址和其他必要数据被压入栈中，当函数返回时，这些数据被弹出。
1.2 基本存储方式
栈有两种基本存储方式:
（1）顺序存储：利用一段连续的内存空间进行存储。
（2）链式存储：利用非连续的内存空间存储，元素之间使用指针进行链接。（通常单链表实现，栈顶是表头，栈底的表尾）
1.3 栈的优点
便于多个栈共享存储空间，提高空间效率；
不存在栈满上溢的情况
1.4 栈的特性
先进后出
2.相关术语
2.1 栈顶（top）
线性表允许插入和删除的那一段。值得注意的是，栈顶指针top的指向是有些两种方式的，一种是指向栈顶当前元素，一种是指向栈顶的下一位置。两种指向方式对栈的操作影响不大，只是在判断栈顶位置的时候略有差异，本文以指向当前栈顶元素为例。另一种指向方式读者可以自行实践。
2.2 栈底（bottom）
固定的，不允许进行插入和删除的另一端。
2.3 空栈
不含有任何元素的空表。
3.基本操作
3.1 栈判空
bool isEmpty(SqStack S)
{
if (S.top==-1)
{
return true;
}
return false;
}3.2 栈判满
bool isFull(SqStack S)
{
if (S.top == MAXSIZE - 1)
{
return true;
}
return false;
}3.3 入栈
bool Push(SqStack& S, ElemType e)
{
bool flag = isFull(S);
if (flag==true)
{
printf("栈满\n");
return false;
}
S.top++;
S.data[S.top] = e;
return true;
}3.4 出栈
bool Pop(SqStack& S, ElemType& e)
{
bool flag = isEmpty(S);
if (flag)
{
printf("栈空\n");
return false;
}
e = S.data[S.top];
S.top--;
return true;
}3.5 取栈顶
//取栈顶
bool GetTop(SqStack& S, ElemType& e)
{
bool flag = isEmpty(S);
if (flag)
{
return false;
}
e = S.data[S.top];
return true;
}3.6 初始化一个空栈
InitStack(&s);粉丝福利， 免费领取C/C++ 开发学习资料包、技术视频/项目代码，1000道大厂面试题，内容包括（C++基础，网络编程，数据库，中间件，后端开发，音视频开发，Qt开发，游戏开发，Linux内核等进阶学习资料和最佳学习路线）↓↓↓↓有需要的朋友可以进企鹅裙927239107领取哦~↓↓
3.7 判断一个在栈是否为空
StackEmpty(s);3.8 入栈，若栈S未满，这将x加入栈，使之称为栈顶
Push(&s,x);3.9 出栈，若栈S非空，则弹出栈顶元素
Pop(&s);3.10 读栈顶元素
GetTop(s,x);3.11 销毁栈，释放栈S所占用内存空间
DestroyStack(&s);4.例题
字符串匹配问题(strs)
【题目描述】
字符串中只含有括号 (),[],<>,{},判断输入的字符串中括号是否匹配。如果括号有互相包含的形式，从内到外必须是<>,(),[],{}，例如。输入: [()] 输出:YES，而输入([])，([)]都应该输出NO。
【输入】
第一行为一个整数n，表示以下有多少个由括好组成的字符串。接下来的n行，每行都是一个由括号组成的长度不超过255255的字符串。
【输出】
在输出文件中有n行，每行都是YES或NO。
【输入样例】
5
{}{}<><>()()[][]
{{}}{{}}<<>><<>>(())(())[[]][[]]
{{}}{{}}<<>><<>>(())(())[[]][[]]
{<>}{[]}<<<>><<>>>((<>))(())[[(<>)]][[]]
><}{{[]}<<<>><<>>>((<>))(())[[(<>)]][[]]
【输出样例】
YES
YES
YES
YES
NO
设数组pri，pri[括号字符]是个整数表示括号的优先级。优先级从低到高为：<([{，左括号优先级为正数，右括号优先级为负数。
这里设pri[右括号] = -pri[左括号]，同类的左右括号的优先级数值是相反数的关系，这样就可以用pri来判断两个括号是否配对。
遍历整个字符串
如果遇到左括号：
如果栈空，则入栈。
如果栈不空
如果当前左括号优先级小于等于栈顶左括号优先级，左括号入栈。
否则不匹配。
如果遇到右括号
如果栈空，则不匹配。
如果栈不空
看栈顶左括号能否与该右括号配对，如果配对则出栈
否则不匹配。
结束遍历字符串后，看栈是否为空
如果栈空，则匹配。
如果栈不空，则不匹配。
#include<bits/stdc++.h>
using namespace std;
int pri[128];//pri[i]:字符i的优先级
void initPri()//初始化括号的优先级
{//左括号都是正数，右括号都是负数，配对的括号的优先级互为相反数
pri['<'] = 1;
pri['('] = 2;
pri['['] = 3;
pri['{'] = 4;
pri['>'] = -1;
pri[')'] = -2;
pri[']'] = -3;
pri['}'] = -4;
}
void solve()//求解一组数据
{
stack<char> stk;
string s;
cin >> s;
for(int i = 0; i < s.length(); ++i)
{
if(pri[s[i]] > 0)//如果s[i]是左括号
{
if(stk.empty())
stk.push(s[i]);
else
{
if(pri[s[i]] <= pri[stk.top()])
stk.push(s[i]);
else
{
cout << "NO" << endl;
return;
}
}
}
else//如果s[i]是右括号
{
if(stk.empty())
{
cout << "NO" << endl;
return;
}
else
{
if(pri[s[i]] + pri[stk.top()] == 0)
stk.pop();
else
{
cout << "NO" << endl;
return;
}
}
}
}
if(stk.empty())
cout << "YES" << endl;
else
cout << "NO" << endl;
}
int main()
{
initPri();
int n;
cin >> n;
while(n--)
solve();
return 0;
}