成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

LeetCode 225：用隊列實現(xiàn)棧 Implement Stack using Queues

AlanKeene / 1461人閱讀

摘要：下面是入棧時代碼獲得隊列長度反轉(zhuǎn)次數(shù)為隊列長度減一反轉(zhuǎn)語言沒有棧和隊列數(shù)據(jù)結(jié)構(gòu)，只能用數(shù)組或雙端隊列實現(xiàn)。這類編程語言就壓根不需要用隊列實現(xiàn)?；蛴脳崿F(xiàn)隊列這種問題，因為棧和隊列本身就必須借助實現(xiàn)。

題目：

使用隊列實現(xiàn)棧的下列操作：

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（雙端隊列）來模擬一個隊列 , 只要是標準的隊列操作即可。

你可以假設所有操作都是有效的（例如, 對一個空的棧不會調(diào)用 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).

解題思路：

方法一（兩個隊列）：

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

? 出入棧：

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

? 取棧頂元素：

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

方法二（一個隊列）：

? 只用一個隊列，只需要在入棧時反轉(zhuǎn)隊列即可：

入棧存入到隊列queue

節(jié)點1入棧：queue：1
反轉(zhuǎn)隊列0次：queue：1

節(jié)點2入棧queue：1->2
反轉(zhuǎn)隊列1次：
queue：1->2 --> queue：2->1

節(jié)點2入棧queue：2->1->3
反轉(zhuǎn)隊列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的元素個數(shù)大于一
            top = queue1.poll();//用top暫存元素，當循環(huán)結(jié)束時，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決定了棧是否為空
    }
}

方法二：

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

Queue queue = new LinkedList<>();

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

Python語言沒有棧和隊列數(shù)據(jù)結(jié)構(gòu)，只能用數(shù)組 List 或雙端隊列 deque 實現(xiàn)。

這類編程語言就壓根不需要 用隊列實現(xiàn)?；蛴脳崿F(xiàn)隊列這種問題，因為棧和隊列本身就必須借助List、deque實現(xiàn)。

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

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

歡迎關(guān)注微.信公.眾號：愛寫B(tài)ug

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/76084.html

相關(guān)文章

  • leetcode225 implement stack using queues

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

    binta 評論0 收藏0

  • [Leetcode] Implement Stack using Queues 用隊列實現(xiàn)棧

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

    ivan_qhz 評論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

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

    tain335 評論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

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

    warmcheng 評論0 收藏0

  • 前端 | 每天一個 LeetCode

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

    張漢慶 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<