LeetCode 225：用隊列實現棧 Implement Stack using Queues

AlanKeene 發布于2019-08-19 10:28 / 1433人閱讀

摘要：下面是入棧時代碼獲得隊列長度反轉次數為隊列長度減一反轉語言沒有棧和隊列數據結構，只能用數組或雙端隊列實現。這類編程語言就壓根不需要用隊列實現棧或用棧實現隊列這種問題，因為棧和隊列本身就必須借助實現。

題目：

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

push(x) -- 元素 x 入棧

pop() -- 移除棧頂元素

top() -- 獲取棧頂元素

empty() -- 返回棧是否為空

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.

示例:

MyStack stack = new MyStack();

stack.push(1);
stack.push(2);  
stack.top();   // 返回 2
stack.pop();   // 返回 2
stack.empty(); // 返回 false

注意:

你只能使用隊列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 這些操作是合法的。

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

你可以假設所有操作都是有效的（例如, 對一個空的棧不會調用 pop 或者 top 操作）

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

解題思路：

方法一（兩個隊列）：

? 隊列先進后出，棧后進先出。用隊列實現棧，可以用兩個隊列完成題解：

? 出入棧：

? 入棧時用 queue1 來存入節點；出棧時queue1 內節點順序出隊列并入隊列到 queue2，直到queue1剩最后一個元素時即為棧頂元素，彈出即可；

? 取棧頂元素：

? 用一個 top 指針一直指向棧頂元素，top() 方法查詢棧頂元素時直接返回 top 指針即可。

方法二（一個隊列）：

? 只用一個隊列，只需要在入棧時反轉隊列即可：

入棧存入到隊列queue

節點1入棧：queue：1
反轉隊列0次：queue：1

節點2入棧queue：1->2
反轉隊列1次：
queue：1->2 --> queue：2->1

節點2入棧queue：2->1->3
反轉隊列2次：
queue：2->1->3 ---> queue：1->3->2 ---> queue：3->2->1

......

這樣不管什么時候出隊順序都是按照出棧的順序。

Java：

方法一

class MyStack {
    Queue queue1;
    Queue queue2;
    private int top;//指向棧頂元素

    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        queue1.offer(x);
        top = x;//新加入元素為棧頂元素
    }

    public int pop() {
        while (queue1.size() > 1) {//條件為隊列1的元素個數大于一
            top = queue1.poll();//用top暫存元素，當循環結束時，top剛好是棧頂元素
            queue2.add(top);
        }
        //隊列1與隊列2交換
        Queue tmp = queue2;
        queue2 = queue1;
        queue1 = tmp;
        return queue2.poll();//返回隊列2的隊列頭元素，隊列2也只有一個元素
    }

    public int top() {
        return top;
    }

    public boolean empty() {
        return queue1.isEmpty();//隊列1決定了棧是否為空
    }
}

方法二：

每次入隊時反轉隊列即可，只有入棧需要特殊操作，出棧、取棧頂元素、是否空都按照隊列正常出隊列、取隊列頭元素、是否空方法操作。下面是入棧時代碼：

Queue queue = new LinkedList<>();

public void push(int x) {
    queue.add(x);
    int sz = queue.size();//獲得隊列長度
    while (sz > 1) {//反轉次數為隊列長度減一
        queue.add(queue.remove());//反轉
        sz--;
    }
}

Python：

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

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

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

class MyStack:

    def __init__(self):
        self.stack = []

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

    def pop(self) -> int:
        return self.stack.pop(-1)

    def top(self) -> int:
        return self.stack[-1]

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

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

GPU云服務器云服務器 java 棧隊列 java 棧隊列面試 python實現棧隊列實現原理

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

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

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] Implement Stack using Queues 用隊列實現棧

摘要：雙隊列法復雜度時間空間思路和類似，我們也可以用兩個隊列來模擬棧的操作。當時，我們將數字進非空的隊列就行了。操作和一樣，區別在于我們拿到最后一個數后，還要再把它進另一個隊列中。雙隊列法復雜度時間 O(N) 空間 O(N) 思路和Implement Queue using Stack類似，我們也可以用兩個隊列來模擬棧的操作。當push時，我們將數字offer進非空的隊列就行了。當p...

ivan_qhz 2019-08-14 12:39 評論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 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評論0 收藏0
前端 | 每天一個 LeetCode

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

張漢慶 2019-08-23 13:42 評論0 收藏0