《剑指offer》用两个栈实现队列-蒲公英云

《剑指offer》用两个栈实现队列

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

题目：

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

思路：

　　队列定义：先进先出

　　栈定义：先进后出

　　要实现入队操作：直接在栈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：

class MyQueue(object):
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack1 =[]                           #第一个栈进行队列的输入操作
        self.stack2 = []                          #第二个栈进行队列的出栈和查看操作
    def push(self, x):
        """
        Push element x to the back of queue.
        :type x: int
        :rtype: None
        """
        self.stack1.append(x)                     #进行入队操作，将元素先在第一个栈中缓存
    def pop(self):
        """
        Removes the element from in front of queue and returns that element.
        :rtype: int
        """
        if not self.stack2:                      #如果第二个栈是空的
            while self.stack1:                   #循环遍历第一个栈
                self.stack2.append(self.stack1.pop())#将第一个栈中的元素全部加入到第二个栈中
        return self.stack2.pop()                 #出栈最后一个元素
    def peek(self):
        """
        Get the front element.
        :rtype: int
        """
        if not self.stack2:                     #如果第二个栈是空的
            while self.stack1:                  #将第一个占中的所有元素全部加载到第二个栈中
                self.stack2.append(self.stack1.pop())
        return self.stack2[-1]                  #返回最后一个元素的值
    def empty(self):
        """
        Returns whether the queue is empty.
        :rtype: bool
        """
        if not self.stack1 and not self.stack2:#只有当两个栈同时(and)空时候，队列为空
            return True
        else:
            return False                       #否则队列中还有值
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()