使用棧實(shí)現(xiàn)隊(duì)列的下列操作：
push(x) -- 將一個(gè)元素放入隊(duì)列的尾部。
pop() -- 從隊(duì)列首部移除元素。
peek() -- 返回隊(duì)列首部的元素。
empty() -- 返回隊(duì)列是否為空。
示例:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
說明:
你只能使用標(biāo)準(zhǔn)的棧操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的語言也許不支持棧。你可以使用 list 或者 deque（雙端隊(duì)列）來模擬一個(gè)棧，只要是標(biāo)準(zhǔn)的棧操作即可。
假設(shè)所有操作都是有效的 （例如，一個(gè)空的隊(duì)列不會(huì)調(diào)用 pop 或者 peek 操作）。

解法 1

利用兩個(gè)棧，分別為輸入棧和輸出棧，隊(duì)列的輸入元素全部壓入輸入棧，當(dāng)隊(duì)列彈出或查看元素時(shí)，若輸出棧為空，則將輸入棧全部壓入輸出棧，此時(shí)已完成所有元素的倒序排列，返回輸出棧的棧頂元素即可；若輸出棧不為空，則直接返回輸出棧的棧頂元素。

from collections import deque


class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.input_stack = deque()
        self.output_stack = deque()

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.input_stack.append(x)

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        if not self.output_stack:
            while not self.input_stack:
                self.output_stack.append(self.input_stack.pop())
        return self.output_stack.pop()

    def peek(self) -> int:
        """
        Get the front element.
        """
        if not self.output_stack:
            while not self.input_stack:
                self.output_stack.append(self.input_stack.pop())
        if not self.output_stack:
            return None
        return self.output_stack.__getitem__(-1)

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return not self.input_stack and not self.output_stack

執(zhí)行用時(shí) :40 ms
內(nèi)存消耗 :13.7 MB

時(shí)間復(fù)雜度：每個(gè)完成入隊(duì)、出隊(duì)的元素平均經(jīng)歷兩次壓入棧，兩次彈出棧，時(shí)間復(fù)雜度都為 O(1)，取隊(duì)首元素、判斷空則對應(yīng)棧的索引和判斷空操作，時(shí)間復(fù)雜度也都為 O(1)
空間復(fù)雜度：入隊(duì)、出隊(duì)操作需要分別使用輸入和輸出兩個(gè)棧，所以空間復(fù)雜度為 O(n)，取隊(duì)首元素、判斷空操作的空間復(fù)雜度為 O(1)

解法 2

利用兩個(gè)棧，分別為存儲(chǔ)棧和過渡棧，隊(duì)列輸入元素時(shí)，提前將存儲(chǔ)棧元素全部壓入過渡棧，然后輸入元素壓入存儲(chǔ)棧，再將過渡棧元素全部彈出并放回存儲(chǔ)棧，這樣就將新元素排列了到棧底，實(shí)現(xiàn)了隊(duì)列先入后出的效果。

from collections import deque


class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.store_stack = deque()
        self.tmp_stack = deque()

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        while self.store_stack:
            self.tmp_stack.append(self.store_stack.pop())
        self.store_stack.append(x)
        while self.tmp_stack:
            self.store_stack.append(self.tmp_stack.pop())

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

    def peek(self) -> int:
        """
        Get the front element.
        """
        if not self.store_stack:
            return None
        return self.store_stack.__getitem__(-1)

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return not self.store_stack

執(zhí)行用時(shí) :40 ms
內(nèi)存消耗 :13.7 MB

時(shí)間復(fù)雜度：每個(gè)完成入隊(duì)的元素平均經(jīng)歷三次壓入棧，兩次彈出棧，時(shí)間復(fù)雜度為 O(n)，出隊(duì)、取隊(duì)首元素、判斷空則對應(yīng)棧的彈出、索引和判斷空操作，時(shí)間復(fù)雜度都為 O(1)
空間復(fù)雜度：入隊(duì)操作需要使用過渡棧，所以空間復(fù)雜度為 O(n)，出隊(duì)、取隊(duì)首元素、判斷空操作的空間復(fù)雜度為 O(1)

注：解法 2 將主要工作放在了入隊(duì)步驟，而解法 1 則將工作分?jǐn)傇谌腙?duì)和出隊(duì)兩個(gè)步驟，平均性能更好。

參考

https://leetcode-cn.com/problems/implement-queue-using-stacks/