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

╰+攻爆jí腚メ 2021-10-29 15:32 322阅读 0赞

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

### 题目： ###

用两个栈来实现一个队列，完成队列的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()

### 思考： ###

我思故我在。

转载于:https://www.cnblogs.com/missidiot/p/10757487.html

[Link 1]: https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6?tpId=13&tqId=11158&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking