代码随想录—栈与队列 | Aryue的个人博客

type

status

date

slug

summary

📝基础理论

首先回答以下四个问题：

在C++中，栈（stack）和队列（queue）通常被归类为容器适配器（container adapters），而不是容器（containers），因为它们的底层容器可以有多种不同的实现。我们常用的SGI STL默认使用dequeue作为栈的底层结构。

如果了解C++栈的底层实现，就会知道其元素不是连续分布的。因此，理解底层知识至关重要！

这些问题虽然看似没有意义，但非常考察基础。要用栈实现队列，最少需要两个栈；而要用队列实现栈，可以使用一个队列，也可以使用两个队列。

这道题是关于栈数据结构的基础问题，一看到这种题目就应该立刻想到栈。

关键在于了解逆波兰表达式是什么，了解中序、后序遍历以及中缀、后缀表达式之间的关系。后缀表达式容易被计算机识别并计算，而中缀表达式则更容易被人理解。

这道题非常难，因为思路很难想到。需要我们自己实现一个单调队列，单调队列中永远维护最大值即可。在添加元素时，保证前方的元素都大于要添加的元素；在移除元素时，先判断窗口出口处元素是否等于要移除的元素。这样每次要获得窗口最大值时，实际上就是拿到窗口出口的值。

使用 优先级队列 实现，优先级队列实际上就是一个堆。只不过我们需要构造一个小顶堆，当堆的元素数量大于K时，就弹出堆顶元素即最小值，这样到最后遍历一遍堆即可。

在栈和队列的问题中，需要特别重视两种类型的问题：一是基础问题，需要用栈实现队列和用队列实现栈；另一种是涉及优先级队列和单调队列的问题，需要自己设计或修改数据结构的底层实现。

致谢：

💡

Written by Aryue，editted by Notion AI.