本题来自《剑指offer》 用两个栈实现队列

题目：

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

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

思路：

　　队列定义：先进先出

　　栈定义：先进后出

　　要实现入队操作：直接在栈1中入栈，将元素压入到栈1中。

　　要实现出队操作：

　　　　如果栈2中没有元素则将栈1的全部数据压入栈2；

　　　　如果栈2中有元素，则直接返回栈顶元素即可。

C++ Code：

class Solution
{
public:
    void push(int node) {
        stack1.push(node);                //入队是直接压入栈1中
    }

    int pop() {
        if (stack2.size()<=0){            //如果栈2中没有值
            while(stack1.size()>0){       //则将栈1的值全部压入栈2中
                int val = stack1.top();
                stack1.pop();
                stack2.push(val);
            }
        }
        int head = stack2.top();          //取栈2的栈顶，即为出队
        stack2.pop();                     //栈2顶出栈
        return head;
    }

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

Python Code：

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):                                 #首先定义两个栈
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        # write code here
        self.stack1.append(node)                        #入队是将元素加入到栈1中
        
    def pop(self):
        # return xx
        if len(self.stack2) <= 0:                       #若栈2中没有元素
            while len(self.stack1):                     #退出条件是栈1为空
                self.stack2.append(self.stack1.pop())   #则将栈1的元素全部加入到栈2中
        return self.stack2.pop()                        #出队是栈2的栈顶

思考：

　　我思故我在。

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄