Leetcode-225Implement Stack usin

225. Implement Stack using Queues

Implement the following operations of a stack using queues.

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

题解：

使用队列实现栈：
首先，我们给出栈和队列的特点：
栈（stack）中的数据是先进后出的（First In Last Out: FILO）:
std::stack<int> S;
STL的栈头文件：
#include <stack>
包括五种基本操作：
S.top(); // 取栈顶元素；
S.push(x); // 将x添加进栈；
S.pop(); // 弹出栈顶元素；
S.empty(); // 判断栈是否为空；
S.size(); // 栈中元素的个数；
队列（queue）中的数据是先进先出的（First In First Out: FIFO）:
std::queue<int> Q;
STL的队列头文件：
#include <queue>
包括六种基本操作：
Q.front(); // 取队列头部元素；
Q.back(); // 取队列尾部元素；
S.push(x); // 将x添加进队列；
S.pop(); // 弹出队列头部元素；
S.empty(); // 判断队列是否为空；
S.size(); // 队列中元素的个数；
下面我们来分析如何用列表来实现栈：

image.png
如图：我们想要让左侧的queue来实现右侧的stack，只需要让队列的元素以先进后出的方式存入队列即可；所以我们要让queue的元素存储顺序变更为new_queue的元素存储顺序。
我想到的解决办法是，创建一个临时列表tem_q来帮助q实现逆序存储；
image.png
如图，当存入一个元素3时：

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

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

#include <cstdio>
#include <iostream>
#include <queue>

using namespace std;

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

    }
    /** Push element x onto stack. */
    void push(int x) {
        queue<int> tem_q;
        tem_q.push(x);
        while (!q.empty()) {
            tem_q.push(q.front());
            q.pop();
        }
        while (!tem_q.empty()) {
            q.push(tem_q.front());
            tem_q.pop();
        }
    }

    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int x = q.front();
        q.pop();
        return x;
    }

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

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

int main() {
    MyStack s;
    s.push(1);
    s.push(2);
    s.push(3);
    while (!s.empty()) {
        printf("%d ", s.top());
        s.pop();
    }
    return 0;
}

结果：

3 2 1

My Solution（Python）:

import queue
class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.Q = queue.Queue()
        self.temp_Q = queue.Queue()

    def push(self, x):
        """
        Push element x onto stack.
        :type x: int
        :rtype: void
        """
        self.temp_Q.put(x)
        while self.Q.empty() is False:
            self.temp_Q.put(self.Q.get())
        while self.temp_Q.empty() is False:
            self.Q.put(self.temp_Q.get())

    def pop(self):
        """
        Removes the element on top of the stack and returns that element.
        :rtype: int
        """
        return self.Q.get()

    def top(self):
        """
        Get the top element.
        :rtype: int
        """
        # return self.Q.get()
        x = self.Q.get()
        self.push(x)
        return x

    def empty(self):
        """
        Returns whether the stack is empty.
        :rtype: bool
        """
        return self.Q.empty()


# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()