剑指offer - 用两个栈实现队列

发表于 | 更新于

题目

https://www.nowcoder.com/questionTerminal/54275ddae22f475981afa2244dd448c6

题意

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

题解

栈的特点是先进后出，队列的特点是先进先出，假设两个栈A和B
入队操作：栈A入栈
出队操作：出队要出的是栈底的元素，所以可以将栈A全部出栈依次存入B栈，这样顺序颠倒了过来，再次出队时，再从B中弹出一个即可，如果B空了，再将A中的元素搬过来，并弹出一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int ans = stack2.top();
        stack2.pop();
        return ans;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

扩展题目

用两个队列来实现一个栈，完成栈的Push和Pop操作。 栈中的元素为int类型。

题解

假设两个队列A和B
入栈操作：入队列A
出栈操作：这时要出队的元素其实应该是队尾的元素，但队列只能出队首的元素，所以我们让队A中除队尾以外的元素全部到队B中去，然后队A出队，然后再将队B中的元素回到队A。
其实在这个过程中，队B只是起到一个调度的作用，在将队B中的元素移回队A中时，其实做的是无用的操作，我们只需要将两个队列的角色互换，这样便省去多余的移动操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution
{
public:
    void push(int node){
        if(queue1.empty())
            swap(queue1,queue2);
        queue1.push(node);
    }
    int pop(){
        if(queue1.empty())
            swap(queue1,queue2);
        while(queue1.size()>1){
            queue2.push(queue1.front());
            queue1.pop();
        }
        int ans = queue1.front();
        queue1.pop();
        return ans;
    }
private:
    queue<int> queue1;
    queue<int> queue2;
};