一道编程题——两个栈实现队列

题目描述

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

题目分析

栈的特点是先进后出，队列为先进先出。

队列的功能只有2个，队尾进，队首出。

队尾进：这一功能和栈一致。

队首出：队列中第一个出队元素，在栈中为栈底元素。在栈中，要想取到栈底元素，必须所有元素出栈。而这些元素，只需要输出最后一个，其他的仍然需要保存。所以，我们可以把一个栈的元素依次取出，存入另一个栈。

解题思路

两个栈A，B，A用来接收入队的元素，B用来模拟出队的操作。

入队时，元素压入栈A，出队时，从栈B的栈顶弹出，如果B中没有元素，则依次取出A的元素压入栈B，再模拟出队操作。

比如：栈A = [1,2,3,4]，栈B = [ ]。

模拟入队操作时，元素直接压入栈A。

模拟出队操作，则需要取出第一个元素1，这时，需要把栈A中元素转到栈B。

栈A = [ ]，栈B = [ 4, 3, 2, 1]。然后再取出栈B的最后一个元素1。

下一次出队操作，再次从栈B取出栈顶元素。如果栈B为空，则将栈A所有的元素取出，压入栈B，再执行栈B的弹出栈顶操作。

代码

python实现

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack_a = []
        self.stack_b = []
    def push(self, node):
        # write code here
        self.stack_a.append(node)
    def pop(self):
        # return xx
        if self.stack_b == []:
            if self.stack_a == []:return
            self.stack_b = list(reversed(self.stack_a))
            self.stack_a = []
            return self.stack_b.pop()
        else:
            return self.stack_b.pop()

C++实现

class Solution
{
public:
    void push(int node) {
        stack2.push(node);
    }
    
    int pop() {
        if(stack1.empty()){
            while(!stack2.empty()){
                stack1.push(stack2.top());
                stack2.pop();
            }
        }
        int tmp = stack1.top();
        stack1.pop();
        return tmp;
    }

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