【算法】两个栈实现一个队列
1 基本概念
- 队列（Queue）
队列是一种先进先出（FIFO, First-In-First-Out）的数据结构。入队的第一个元素一定是出队的第一个元素。
- 栈（Stack）
栈是一种后进先出（LIFO, Last-In-First-Out）的数据结构。新加入的元素在栈顶，取出时也是从栈顶取。
2 用两个栈实现队列的思绪
由于队列要求开始进入的元素开始被处置处罚，而栈恰好相反（末了进入的元素开始被处置处罚），因此直接用一个栈无法模拟队列的举动。解决方法是利用两个栈，分别称为：
- 输入栈（inStack）：用于保存全部入队的元素。
- 输出栈（outStack）：用于执行出队操作和访问队首元素。
为什么需要两个栈？
当你把元素依次压入第一个栈（inStack）时，它们在栈中的顺序是逆序的。假设依次入队元素 1, 2, 3，在 inStack 中，出栈顺序为：3，2，1，这并不是队列的正确顺序（应为 1 先出）。
关键： 通过将 inStack 中的全部元素一次性弹出并压入第二个栈（outStack），顺序就会被反转：
- 弹出顺序：3, 2, 1
- 压入 outStack 后：弹出顺序：1，2，3
此时，outStack 的栈顶恰好是最早进入的元素，也就是队列的队首元素。
3 操作流程详细解释
1. 入队操作（push）
- 操作： 直接将新元素压入 inStack。
- 缘故起因： 入队时只需要保存元素，临时不思量顺序题目，因为出队时会举行转换。
- 时间复杂度： O(1)
假设执行 push(1)、push(2)、push(3) 后，inStack 状态（从栈底到栈顶）：[1, 2, 3]。
2. 出队操作（pop）
- 环境1：当 outStack 非空
- 直接从 outStack 弹出栈顶元素，这个元素就是队首。
- 环境2：当 outStack 为空
- 将 inStack 中全部元素依次弹出，然后压入 outStack（在这个过程中，顺序被完全反转）。
- 弹出 outStack 的栈顶元素作为出队的结果。
详细步骤：
- 检查 outStack 是否为空：
- 如果不为空，直接 pop() 即可。
- 如果为空，进入下一步。
- 将 inStack 元素转移到 outStack：
- 利用 while 循环：
- while (!inStack.empty()) {
- outStack.push(inStack.top());
- inStack.pop();
- }
- 转移完成后，原本开始入队的元素现在位于 outStack 的栈顶。
- 从 outStack 弹出栈顶元素：
留意：
- 转移操作只在 outStack 为空时举行，以是每个元素最多只会被移动一次，保证了均派时间复杂度为 O(1)。
详细示例
假设举行如下操作：
- 入队：
- push(1)
- push(2)
- push(3)
此时：
- inStack: [1, 2, 3] （1在底部，3在顶部）
- outStack: 空
- 第一次出队（pop 或 peek）：
- outStack 为空，以是把 inStack 全部转移到 outStack。
转移过程：
- 弹出 3（inStack 变为 [1, 2]），压入 outStack → outStack: [3]
- 弹出 2（inStack 变为 [1]），压入 outStack → outStack: [3, 2]
- 弹出 1（inStack 变为 []），压入 outStack → outStack: [3, 2, 1]
- 现在 outStack 的栈顶为 1，即队首元素。
- 执行 pop 时，弹出 outStack 顶部的 1。
- 第二次出队：
- 此时 outStack 非空（当前状态为 [3, 2]，栈顶为 2），直接 pop 出 2。
- 后续操作：
- 继续按上述规则举行，始终保持入队操作只对 inStack 举行，出队或 peek 操作如果 outStack 为空则转移，否则直接操作 outStack。
总结
- 入队时：直接将新元素压入 inStack，保持 O(1) 时间。
- 出队时：如果 outStack 为空，将 inStack 全部转移到 outStack，这个转移过程会将元素顺序反转，从而使得最早入队的元素出现在 outStack 栈顶；如果 outStack 非空，直接操作其栈顶。由于每个元素最多只转移一次，以是整体的均派时间复杂度是 O(1)。
这种设计利用了两个栈之间的顺序反转特性，有用地模拟了队列的 FIFO 举动，同时在实际应用中表现出了高效性。
- class Solution {
- public:
- void push(int node) {
- inStack.push(node);
- }
- int pop() {
- if (outStack.empty()) {
- while(!inStack.empty()) {
- int n = inStack.top();
- inStack.pop();
- outStack.push(n);
- }
- }
- int n = outStack.top();
- outStack.pop();
- return n;
- }
- //设置两个栈 一个用来push数据，一个用来pop数据
- private:
- stack<int> inStack;//push
- stack<int> outStack;//pop
- };
- };
|
