栈是先进后出，队列是先进先出，自我感觉y总的比喻不好，重新比喻一下。
栈就像乒乓球桶，挨个放进乒乓球，拿出来的只能是最后一个球。
队列像隧道，进去车后只能等前面的车走了自己才能走，如果堵车就只能待着，不能回去。

栈

普通栈

每次只有两个操作，1.放进去，2.拿出来，也只能查看栈顶的元素。

做法：

注：这里的栈与队列都是用数组模拟

用$stk[N]$数组当栈，$tt$当栈顶下标。

代码：

// 插入
stk[++tt] = x;
// 弹出
tt--;
// 判断栈是否为空
if (tt > 0) not empty;
else empty;
// 栈顶
stk[tt];

结束，实际上普通的栈和队列都挺简单的，就是单调栈和单调队列……

单调栈

例题几乎只有一道，拿这道例题来理解。

思路：

考虑暴力做法：遍历整段区间，然后从$i-1$往前遍历，只要遍历到比它小的，就输出，如果没有，就输出$-1$。
这样我们发现可以用一个栈来解决事情。
当i往后遍历的时候，遍历一个往栈里面放一个，这样遍历到$i$点的时候，栈里面是$a_1, a_2, …, a_{i-1}$。
我们看一下有什么性质，就是有没有某一个点怎么着都不会被选到，最后可以发现，当$a_x \ge a_y $且$x < y$ 时$a_x$可以删掉，删完之后，整个序列就变成单调上升的了。
如果栈顶大于当前数，就删，一直删到找到了或没数了为止，然后把当前值插到里面去，删完之后正好就完成了上面的操作。

代码（就当单调栈的模板吧，上面说的思路就是单调栈的实现方式）：

for (int i = 1; i <= n; i++){
    int x;
    cin >> x;
    while (tt && stk[tt] >= x) tt--;
    if (tt) cout << stk[tt] << ' ';
    else cout << -1 << ' ';
    stk[++tt] = x;
}

队列

普通队列

每次也只有两个操作，1.在队尾插入元素，2.在队头弹出元素，也只能查看队头的元素。

做法：

用$q[N]$数组当队列，$hh$当队头，$tt$当队尾。

代码：

// 插入
q[++tt] = x;
// 弹出
hh++;
// 判断栈是否为空
if (hh <= tt) not empty;
else empty;
// 队头
q[hh];

单调队列

例题也就那么几道，还是用一道例题滑动窗口来理解。

思路：

窗口可以用队列来模拟，每次移动窗口，从前面插入一个元素，从后面弹出一个元素。’
先考虑暴力做法，然后再推出正解。
暴力做法是直接遍历一遍整个队列，复杂度是$O(k)$，总体的复杂度就是$O(nk)$，很恐怖。

那怎么优化呢？

如果$a_x \ge a_y $且$x < y$ 的话$a_x$可以删掉（跟单调栈这不一样吗）。
注意：在队列里面存的是下标，不是值。
可以判断队列中那个下标在不在$i-k+1$ ~ $i$，如果不在就删掉。
还有，数组模拟的队列比STL要快一些。

小于部分的代码（也可以理解成单调队列的模板）：

for (int i = 1; i <= n; i++){
    if (hh <= tt && i - k + 1 > q[hh]) hh++;
    while (hh <= tt && a[q[tt]] > a[i]) tt--;
    q[++tt] = i;
    if (i >= k - 1) cout << a[q[hh]];
}

-------------------------------------------------------------------结束--------------------------------------------------------------------