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).

題解：

使用隊(duì)列實(shí)現(xiàn)棧：
首先，我們給出棧和隊(duì)列的特點(diǎn)：
棧（stack）中的數(shù)據(jù)是先進(jìn)后出的（First In Last Out: FILO）:
std::stack<int> S;
STL的棧頭文件：
#include <stack>
包括五種基本操作：
S.top(); // 取棧頂元素；
S.push(x); // 將x添加進(jìn)棧；
S.pop(); // 彈出棧頂元素；
S.empty(); // 判斷棧是否為空；
S.size(); // 棧中元素的個(gè)數(shù)；
隊(duì)列（queue）中的數(shù)據(jù)是先進(jìn)先出的（First In First Out: FIFO）:
std::queue<int> Q;
STL的隊(duì)列頭文件：
#include <queue>
包括六種基本操作：
Q.front(); // 取隊(duì)列頭部元素；
Q.back(); // 取隊(duì)列尾部元素；
S.push(x); // 將x添加進(jìn)隊(duì)列；
S.pop(); // 彈出隊(duì)列頭部元素；
S.empty(); // 判斷隊(duì)列是否為空；
S.size(); // 隊(duì)列中元素的個(gè)數(shù)；
下面我們來(lái)分析如何用列表來(lái)實(shí)現(xiàn)棧：

image.png

image.png

1. 將（元素3）push 到空的臨時(shí)隊(duì)列中；
2. 將q中已逆序的元素依次取出存入temp_q中，直到取出q中所有元素(q為空)；注：剛開(kāi)始push第一個(gè)元素時(shí)，q本來(lái)就是空的，所以直接跳到三步；
3. 將tem_q中逆序的元素依次取出存入q中，直到取出所有元素為止（tem_q為空）；
   自此，后進(jìn)入的（元素3）也成功變?yōu)殛?duì)列q的頭部元素，實(shí)現(xiàn)了后入先出（棧）；

My Solution（C/C++完整實(shí)現(xiàn)）：

#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;
}

結(jié)果：

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