LeetCode 232：用棧實現隊列 Implement Queue using Stacks

cloud 發布于2019-08-19 10:26 / 2498人閱讀

摘要：題目使用棧實現隊列的下列操作將一個元素放入隊列的尾部。用棧實現隊列，可以用兩個棧完成題解。入隊列時用存入節點，出隊列時內節點順序出棧壓入中。這類編程語言就壓根不需要用隊列實現棧或用棧實現隊列這種問題，因為棧和隊列本身就必須借助實現。

題目：

使用棧實現隊列的下列操作：

push(x) -- 將一個元素放入隊列的尾部。

pop() -- 從隊列首部移除元素。

peek() -- 返回隊列首部的元素。

empty() -- 返回隊列是否為空。

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.

示例:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

說明:

你只能使用標準的棧操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。

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

假設所有操作都是有效的（例如，一個空的隊列不會調用 pop 或者 peek 操作）。

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

解題思路：

隊列先進后出，棧后進先出。用棧實現隊列，可以用兩個棧完成題解。入隊列時用 stack1 存入節點，出隊列時 stack1 內節點順序出棧壓入 stack2 中。

例如 1, 2, 3 元素順序入隊列 
即存入棧stack1：[1, 2, 3]

出隊列時順序應為：1->2->3
但是棧先進先出，出棧順序為：3->2->1
與出隊列順序不相符

借助另一個棧stack2
stack1內的元素順序出棧并壓入stack2
stack1：[1, 2, 3] ---> stack2：[3, 2, 1]
此時stack2出棧順序：1->2->3
與出隊列順序相符

注意：在出隊列時無需著急將 stack1 中的節點順序壓入 stack2。因為要實現的隊列是先進后出，可以將 stack2 中的節點全部彈出之后再將 stack1 內節點順序壓入stack2，這樣可以將出棧的時間復雜度攤還到 O(1)。

Java：

class MyQueue {
    private Stack stack1;
    private Stack stack2;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    public int peek() {
        //stack1節點順序彈出并壓入stack2
        if (stack2.isEmpty()) {//條件是: stack2為空,而不是stack1非空, 這樣攤還復雜度O(1)
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());//stack1彈出節點并壓入stack2
            }
        }
        return stack2.peek();
    }

    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

Python：

Python語言沒有棧和隊列數據結構，只能用數組 List 或雙端隊列 deque 實現。

這類編程語言就壓根不需要用隊列實現棧或用棧實現隊列這種問題，因為棧和隊列本身就必須借助List、deque實現。

所以這道題在這種語言中這就非常簡單了，可以說是作弊。

class MyQueue:
    def __init__(self):
        self.queue = []

    def push(self, x: int) -> None:
        self.queue.append(x)

    def pop(self) -> int:
        #彈出第一個元素
        return self.queue.pop(0)

    def peek(self) -> int:
        #返回第一個元素
        return self.queue[0]

    def empty(self) -> bool:
        return not self.queue

歡迎關注微.信公.眾號：愛寫Bug

云服務器 GPU云服務器隊列queue 隊列實現原理消息隊列實現 python隊列實現

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/76013.html

[Leetcode] Implement Queue using Stacks 用棧實現隊列

摘要：注意的方法是和，實際上我們應該實現的是和或者和，的實現和是一樣的，但將改為時，我們要先把到的元素保存，然后再彈出輸出棧，然后返回這個保存的元素。 Implement Queue using Stacks Implement the following operations of a queue using stacks. push(x) -- Push element x to th...

Martin91 2019-08-14 12:29 評論0 收藏0
leetcode232 Implement Queue using Stacks

摘要：題目要求通過隊列實現一個棧的功能。棧的為壓入棧頂，出棧，棧頂元素，棧是否為空。重復上述的操作。但是當需要彈出元素時，則從桶彈出。這樣，下次加入的元素必然全部位于桶后的所有元素，而桶中的元素也能保證位輸入順序。極大的減少了不必要的入棧出棧。題目要求 Implement the following operations of a queue using stacks. push(x) ...

golden_hamster 2019-08-15 13:32 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0
LeetCode 225：用隊列實現棧 Implement Stack using Queues

摘要：下面是入棧時代碼獲得隊列長度反轉次數為隊列長度減一反轉語言沒有棧和隊列數據結構，只能用數組或雙端隊列實現。這類編程語言就壓根不需要用隊列實現棧或用棧實現隊列這種問題，因為棧和隊列本身就必須借助實現。題目：使用隊列實現棧的下列操作： push(x) -- 元素 x 入棧 pop() -- 移除棧頂元素 top() -- 獲取棧頂元素 empty() -- 返回棧是否為空 Impl...

AlanKeene 2019-08-19 10:28 評論0 收藏0