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

Martin91 發布于2019-08-14 12:29 / 2155人閱讀

摘要：注意的方法是和，實際上我們應該實現的是和或者和，的實現和是一樣的，但將改為時，我們要先把到的元素保存，然后再彈出輸出棧，然后返回這個保存的元素。

Implement Queue using Stacks

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.

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

雙棧法 復雜度

時間入隊O(1) 出隊O(N) 空間 O(N)

思路

隊列和棧都是順序插入的，區別在于隊列的出口方向和棧的出口方向是相反的，利用這個性質，如果我們將元素按照順序插入棧后，再一個個彈出并反向插入另一個棧，那么這第二個棧的出口順序就和隊列是一樣的了。所以我們構造兩個棧，所有新加的元素都加入輸入棧，一旦要出隊列時，我們便將輸入棧的元素都反向加入輸出棧，再輸出。需要注意的是，如果輸出棧不為空時，說明當前要輸出的元素還在輸出棧中，所以我們就暫時不用將輸入棧的元素加入輸出棧（而且加入后也會導致順序錯誤）。

注意

Leetcode的方法是pop和push，實際上我們應該實現的是poll和offer（或者enqueue和dequeue），offer的實現和push是一樣的，但將pop改為poll時，我們要先把peek到的元素保存，然后再彈出輸出棧，然后返回這個保存的元素。

代碼

class MyQueue {
    
    Stack input = new Stack();
    Stack output = new Stack();
    
    // Push element x to the back of queue.
    public void push(int x) {
        input.push(x);
    }

    // Removes the element from in front of queue.
    public void pop() {
        int x = peek();
        output.pop();
    }

    // Get the front element.
    public int peek() {
        if(output.isEmpty()){
            while(!input.isEmpty()){
                output.push(input.pop());
            } 
        }
        return output.peek();
    }

    // Return whether the queue is empty.
    public boolean empty() {
        return input.isEmpty() && output.isEmpty();
    }
}

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

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

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

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

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

cloud 2019-08-19 10:26 評論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 225：用隊列實現棧 Implement Stack using Queues

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

AlanKeene 2019-08-19 10:28 評論0 收藏0
leetcode225 implement stack using queues

摘要：題目要求使用隊列來模擬實現一個棧。棧是指先進后出的數據結構，而隊列則是先進先出的數據結構。隊列的包括在隊列尾插入數據，輸出隊列頭的數據，查看隊列的長度，隊列是否為空。題目要求 Implement the following operations of a queue using stacks. push(x) -- Push element x to the back of que...

binta 2019-08-15 13:30 評論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