先把栈和队列想简单
栈和队列是最基础的数据结构之一。栈是后进先出，队列是先进先出。
单独看它们并不复杂，但在 ACM 里，真正常见的是它们的两个变体：单调栈和单调队列。它们的共同点是：在容器里维护某种单调顺序，把不可能成为答案的元素提前删掉。
栈：处理最近关系
普通栈最适合处理“最近的还没匹配的东西”。比如括号匹配：
bool ok(string s) {
stack<char> st;
for (char c : s) {
if (c == '(') st.push(c);
else {
if (st.empty()) return false;
st.pop();
}
}
return st.empty();
}栈的意义在于：如果一个左括号还没被匹配，它会留在栈里；新的右括号只能先匹配最近的那个左括号。
队列：处理先后顺序
队列适合处理先进先出的过程，比如 BFS。
queue<int> q;
q.push(start);
vis[start] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : g[u]) {
if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}BFS 之所以能一层一层扩展，就是因为队列保证先进入的点先被处理。
单调栈：下一个更大元素
单调栈常用来找“左边或右边第一个比我大/小的元素”。
比如对每个位置，找右边第一个更大的数：
vector<int> ans(n, -1);
stack<int> st; // 存下标，栈内对应值保持递减
for (int i = 0; i < n; i++) {
while (!st.empty() && a[i] > a[st.top()]) {
ans[st.top()] = a[i];
st.pop();
}
st.push(i);
}为什么弹栈？因为当前 a[i] 已经成为那些较小元素右边第一个更大的数。它们的答案确定了，就不需要再留在栈里。
单调栈的复杂度是 O(n)，因为每个元素最多进栈一次、出栈一次。
单调栈还能做什么
单调栈常见题型包括：
- 下一个更大元素、下一个更小元素；
- 每天温度这类“还要等几天”的问题；
- 柱状图中最大矩形；
- 每个元素作为最小值或最大值能影响多大区间。
看到“最近一个比它大”“最近一个比它小”“左右边界由大小关系决定”，就可以想单调栈。
单调队列：滑动窗口最大值
单调队列常用来维护滑动窗口里的最大值或最小值。
以窗口最大值为例，队列里存下标，并让对应值保持递减：
deque<int> dq;
vector<int> ans;
for (int i = 0; i < n; i++) {
while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
dq.push_back(i);
if (i >= k - 1) ans.push_back(a[dq.front()]);
}队首永远是当前窗口里最大的元素。队尾那些比当前元素小的值，以后不可能再成为最大值，因为当前元素更大、位置还更靠后，所以可以直接删掉。
单调结构的共同思想
单调栈和单调队列看起来一个用栈，一个用队列，但思想非常像：把没有未来的元素删掉。
- 单调栈删除的是“答案已经被当前元素确定”的元素；
- 单调队列删除的是“以后不可能成为窗口最值”的元素；
- 它们都依赖每个元素最多进出一次，所以是线性的。
刚开始学时，不需要急着记很多模板。先把“为什么能弹掉”想清楚，模板自然会稳。
这一篇先记住什么
- 栈适合处理最近未匹配关系，队列适合处理先进先出的层次关系。
- 单调栈常找最近更大或更小元素。
- 单调队列常维护滑动窗口最大值或最小值。
- 单调结构的核心是删掉不可能成为答案的元素。
下一篇可以继续往基础数据结构走：哈希表与计数，看看如何把“查找”和“统计”做得更快。