编程之禅
0%

用两个栈模拟一个队列

发表于 更新于 分类于 阅读次数： Disqus：

思路

本题是考察栈和队列的常见问题。要解答本题必须知道栈的队列的基本原理。

栈：一种后进先出的数据结构，想象一个单车道，汽车一辆接一辆往里开，最先进入的在最里面，最后进入的在最外面，当需要出去的时候，最后进入的先出，最先进入的最后出去。符合类似进出原则的数据结构就叫做栈。 往栈中存入数据也叫压栈，取出数据也叫弹栈。

队列：先进先出的数据结构。顾名思义，就像排队一样，最先进入在队头，后进入在队尾，队头先出队，队尾后出队。往队列中存入数据叫入队，往队列中取数据叫出队。

说完了栈和队列的基本概念，那怎么用两个栈来模拟一个队列呢？ 假设两个栈分别为 stack1，stack2

举个例子，现有一个入队顺序如下：1 2 3 4 5 6 7

它的合法出队顺序应该如下：1 2 3 4 5 6 7

我们先用一个栈，例如 stack1 入队信息依次压栈：1 2 3 4 5 6 7，那么弹栈顺序为：7 6 5 4 3 2 1，很明显和入队顺序刚好相反，那该怎么办呢？这就需要借助第二个栈了。

我们将 stack1 弹栈，然后按弹栈顺序入栈 stack2 中（方法一），这样 stack2 中的数据为：7 6 5 4 3 2 1，这样 stack2 的输出就符合队列的输出要求了，也就是：1 2 3 4 5 6 7

现在还有一个问题，后续的入队和出队问题，也很简单。每次入队，都将其存入 stack1 中，出队时，首先判断 stack2 是否为空，如果为空就使用采取方法一，如果不为空，就从 stack2 中弹出一个数据，就是正确的出队顺序。关键：只有当 stack2 为空时，才将 stack1 中的数据按出栈顺序压入 stack2 中。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class CQueue {
public:
    stack<int>stack1;
    stack<int>stack2;
    CQueue() {
    }
    
    void appendTail(int value) {
        stack1.push(value);
    }
    
    int deleteHead() {
        if(stack2.empty()){                     // stack2 为空才执行方法一
            while(!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
        }

        if(stack2.empty())                     // 不存在数据的情况
            return -1;
        int ret = stack2.top();
        stack2.pop();
        return ret;
    }
};

时间复杂度分析

时间复杂度 O(1)，上述方法一虽然是需要消耗时间 O(n)，但是均摊下来，每个元素的入队和出队，都是 O(1)

空间复杂度 O(n)

题目链接