leetcode怎么用棧實現(xiàn)隊列

這篇文章給大家分享的是有關(guān)leetcode怎么用棧實現(xiàn)隊列的內(nèi)容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

一、題目內(nèi)容

請你僅使用兩個棧實現(xiàn)先入先出隊列。隊列應(yīng)當(dāng)支持一般隊列的支持的所有操作（push、pop、peek、empty）：

實現(xiàn) MyQueue 類：

• void push(int x) 將元素 x 推到隊列的末尾

• int pop() 從隊列的開頭移除并返回元素

• int peek() 返回隊列開頭的元素

• boolean empty() 如果隊列為空，返回 true ；否則，返回 false

說明：

• 你只能使用標(biāo)準(zhǔn)的棧操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。

• 你所使用的語言也許不支持棧。你可以使用 list 或者 deque（雙端隊列）來模擬一個棧，只要是標(biāo)準(zhǔn)的棧操作即可。

進(jìn)階：

• 你能否實現(xiàn)每個操作均攤時間復(fù)雜度為 O(1) 的隊列？換句話說，執(zhí)行 n 個操作的總時間復(fù)雜度為 O(n) ，即使其中一個操作可能花費較長時間。

示例：

輸入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
輸出：
[null, null, null, 1, 1, false]

解釋：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
 

提示：

1 <= x <= 9
最多調(diào)用 100 次 push、pop、peek 和 empty
假設(shè)所有操作都是有效的 （例如，一個空的隊列不會調(diào)用 pop 或者 peek 操作）

二、解題思路

由于棧只能后進(jìn)先出，所以可以用一個棧先按照順序存，然后再從后往前彈出給新的棧，這樣新的棧再彈出就是先進(jìn)先出的順序了。

三、代碼

class MyQueue:

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

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

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        if len(self.sb) == 0:
            while len(self.sa) != 0:
                self.sb.append(self.sa.pop())
        return self.sb.pop()

    def peek(self) -> int:
        """
        Get the front element.
        """
        if len(self.sb) == 0:
            while len(self.sa) != 0:
                self.sb.append(self.sa.pop())
        return self.sb[-1]

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return len(self.sa) == 0 and len(self.sb) == 0


# 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()
if __name__ == '__main__':
    myQueue = MyQueue()
    myQueue.push(1)
    myQueue.push(2)
    ans1 = myQueue.peek()
    ans2 = myQueue.pop()
    ans3 = myQueue.empty()
    print(ans1, ans2, ans3)

感謝各位的閱讀！關(guān)于“l(fā)eetcode怎么用棧實現(xiàn)隊列”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學(xué)到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！