Part 0：序
其实本来这都是很基础的东西，可惜野路子出身基础并不扎实。
借着这个机会整合一下吧。也做了一些题了解了一些基本操作方法。
本文对于 栈 和 队列的原理不再过多赘述，默认读者掌握基本原理。
参考题单：
数据结构加强001：栈和队列
本文所讲例题来源以上题单。
【团队内部题单】
栈
所谓 “栈” 就是一种先进后出的数据结构，最典型的，可以用来进行运算顺序的处理。我们只需要在计算乘法的时候将 stack 顶弹出和当前数据乘法运算后再入栈即可。
典例：P1981 表达式求值
上述是栈的基本操作。接下来会给出几个例题来进一步强化栈的操作。
典例1:P4387 验证栈序列
Description
给定入栈序列 \(s\)，和一个序列 \(k\)，你需要判断在入栈顺序为 \(s\) 的前提下，出栈顺序是否可能为 \(k\)。
Analysis
Analysis
注意到我们需要判断出栈序列是否合法，显然我们可以直接递归搜索每一种可能的出栈顺序，然后比对即可。本题没有给定数据范围，但是会 TLE。
考虑“贪心地”去尽可能满足它所给定的出栈序列。
具体地，每次入栈后，如果此时的栈顶元素是当前应当出栈的（也就是给定出栈序列），则出栈。需要注意每次入栈后可以连续出栈，所以我们需要 while 循环，而不是默认只能出一个元素。
如此操作，我们确保了每次出栈操作是合法的。最后判断栈是否为空即可。
对于本题，我们所有的操作都可以在 main 函数里解决，所以 stack 开局部变量即可。避免忘记多测清空。
本题的本质就是模拟栈操作。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
const int N = 100010;
int a[N],b[N];
int q;
stack <int> s;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>q;
while(q--)
{
int cnt = 1;
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
for(int i=1;i<=n;i++)
{
s.push(a[i]);
while(!s.empty() && s.top() == b[cnt])
{
s.pop();
cnt++;
}
}
if(s.empty()) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
while(!s.empty()) s.pop();
}
return 0;
}
典例2：P3056
Description
给出一个偶数长度的括号序列，问最少修改多少个括号可以使其平衡。
Analysis
Analysis
首先明确，本题是 修改括号，而不是括号配对! 题意需要明确。
然后如何处理？我们不妨先将配对的括号全部配对，这很简单，使用 stack 即可完成。
接下来我们会剩下些许左括号和右括号，分别记为 \(s_1,s_2\)。
接下来考虑如何将这些 无法配对 的括号通过一系列修改使其配对。
考虑手动构造几组样例，如下：
（图1）
（图2）
通过构造样例，不难发现 对于无法配对的括号，只有可能是一连串的左括号和一连串的右括号，不可能出现形似 ”()“的，原因显然。
考虑对于这样的括号如何配对。
发现对于图1，左括号和右括号都是 偶数个，贪心地考虑，我们可以将左括号和右括号间隔排列，也就是需要更改 \(s_1\div 2 + s_2\div 2\) 个括号。
对于图2，像图1一样构造后一定会剩下一个 ")("，这样我们只能通过添加括号来配对，只需要在 \(s_1\div 2 + s_2\div 2\) 的基础上 \(+2\) 即可。由于 C++ 默认向 0 取整，对于正数也就是向下取整，所以无需特殊处理。
至此，本题的解。考虑到最后发现本题是个人类智慧贪心构造题！只不过在贪心前一定要处理好配对好的括号。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
stack <int> s;
int num = 0;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
char ch;
int cnt = 0;
while(cin>>ch)
{
if(ch == '(') s.push(++cnt);
else
{
if(!s.empty()) s.pop();
else num ++;
}
}
if(num % 2 == 0 && s.size() % 2 == 0) cout<<num/2+s.size()/2<<endl;
else cout<<num/2+s.size()/2+2<<endl;
return 0;
}
典例3：P2866
Description
Analysis
本题是单调栈的模板题，参见：SXqwq 的单调栈学习笔记
队列
所谓 "队列" 是一种先进先出的数据结构。具体地，队列一端进，一端出。
诚然，这只是最基础地队列，队列只是一种模型，大家千万不要被束缚。下面列举了几个基础应用。
STL 板子
Analysis
没啥好分析的，队列的两端都可以进出，直接 deque 即可。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <deque>
using namespace std;
int n;
int cow_cnt = 1;
deque <int> q;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
char ctl;
cin>>ctl;
if(ctl == 'A')
{
char ctl2;
cin>>ctl2;
if(ctl2 == 'L') q.push_front(cow_cnt++);
else q.push_back(cow_cnt++);
}
else if(ctl == 'D')
{
char ctl2;
int k;
cin>>ctl2;
if(ctl2 == 'L')
{
cin>>k;
while(k--)
{
q.pop_front();
}
}
else
{
cin>>k;
while(k--)
{
q.pop_back();
}
}
}
}
while(!q.empty())
{
cout<<q.front()<<endl;
q.pop_front();
}
return 0;
}
典例2：P3662
Description
共有N个信号灯，编号为1~N，有B个信号灯损坏，给你它们的编号。
问，最少修好几个信号灯，可以有K个编号连续的信号灯。
Analysis
记每个需要修理的路灯为 \(1\) ，其他为 \(0\)。
题目要求 最少修好多少个灯，可以有 \(K\) 个编号连续的信号灯
不妨首先算 \(1-k\) 号路灯有几个需要修的，然后滑块移动即可。
当然也有用前缀和处理的，我当时没想到ww
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010;
const int INF = 0x3f3f3f3f;
int n,k,b;
int num[N];
int sum;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>k>>b;
for(int i=1;i<=b;i++)
{
int p;
cin>>p;
num[p] ++;
}
for(int i=0;i<=k;i++) sum += num[i];
int l = 0,r = k;
int minn = INF;
minn = min(minn,sum);
while( r <= n)
{
// cout<<l<<" "<<r<<endl;
l ++;
r ++;
minn = min(minn,sum);
sum -= num[l];
sum += num[r];
minn = min(minn,sum);
}
cout<<minn<<endl;
return 0;
}