232. Implement Queue using Stacks && 剑指offer-用两个栈实现队列

Implement the following operations of a queue using stacks.

push(x) -- Push element x to the back of queue.
pop() -- Removes the element from in front of queue.
peek() -- Get the front element.
empty() -- Return whether the queue is empty.
Notes:
You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

题解：

用栈实现队列；
栈和队列的特点：Leetcode225: https://www.jianshu.com/p/fc567af89e52
思路和leetcode225一样：

image.png

要想让栈实现队列，我们只需要将元素逆序进栈，实现先进先出即可（如图，即将stack变更为new_stack的存储方式）；
创建一个临时栈tem_s来帮助s实现逆序存储；

image.png

如图，当存入一个元素3时：

1. 将q中已逆序的元素依次取出存入temp_s中，直到取出s中所有元素(s为空)；注：刚开始push第一个元素时，s本来就是空的，所以直接跳到第二步；
2. 将（元素3）push 到空的临时栈中；
   将tem_s中逆序的元素依次取出存入s中，直到取出所有元素为止（tem_s为空）；
   自此，后进入的（元素3）也成功变为栈s的栈底元素，实现了后进后出（队列）；

My Solution（C/C++完整实现）：

#include <cstdio>
#include <iostream>
#include <stack>

using namespace std;

class MyQueue {
public:
    /** Initialize your data structure here. */
    MyQueue() {

    }

    /** Push element x to the back of queue. */
    void push(int x) {
        stack<int> tem_s;
        while (!s.empty()) {
            tem_s.push(s.top());
            s.pop();
        }
        tem_s.push(x);
        while (!tem_s.empty()) {
            s.push(tem_s.top());
            tem_s.pop();
        }
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        int x = s.top();
        s.pop();
        return x;
    }

    /** Get the front element. */
    int peek() {
        return s.top();
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return s.empty();
    }
private:
    stack<int> s;
};

int main() {
    MyQueue q;
    q.push(1);
    q.push(2);
    q.push(3);
    while (!q.empty()) {
        printf("%d ", q.peek());
        q.pop();
    }
    return 0;
}

结果：

1 2 3

My Solution（Python）：

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack = []
        self.temp_stack = []

    def push(self, x):
        """
        Push element x to the back of queue.
        :type x: int
        :rtype: void
        """
        while self.stack:
            self.temp_stack.append(self.stack.pop())
        self.temp_stack.append(x)
        while self.temp_stack:
            self.stack.append(self.temp_stack.pop())

    def pop(self):
        """
        Removes the element from in front of queue and returns that element.
        :rtype: int
        """
        return self.stack.pop()

    def peek(self):
        """
        Get the front element.
        :rtype: int
        """
        x = self.stack.pop()
        self.stack.append(x)
        return x

    def empty(self):
        """
        Returns whether the queue is empty.
        :rtype: bool
        """
        return self.stack == []


# 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()