leetcode232 Implement Queue using Stacks

golden_hamster 發布于2019-08-15 13:32 / 2429人閱讀

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

題目要求

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

通過隊列實現一個棧的功能。棧的api為push（壓入棧頂），pop（出棧），peek（棧頂元素），empty（棧是否為空）。這道題和之前的使用棧實現隊列功能是類似的，可以參考我的這篇博客。

思路與代碼

因為棧本質上是將輸入的元素逆序輸出，因此如果我們通過兩個棧對輸入的元素進行兩次逆序操作就可以保證按照最初的順序輸出。那么什么時候進行逆序的操作呢？

思路一：倒入再倒回。
將棧想象為兩個桶，每次我都想獲得第一個桶中最底下的東西，因此我將第一個桶倒入第二個桶，這時原來在第一個桶底的元素就在第二個桶的最上面。取完第二個桶中的內容后，我再把東西倒回。這樣每次都只需要往第一個桶里面添加新元素，如果想要獲得第一個桶桶底的元素，就把它倒到第二個桶里面去。重復上述的操作。圖示如下：

1.輸入[1,2,3,4,5]

2.獲得捅底的元素1，則將1號桶導入2號桶，獲取元素后再倒回

3.輸入[6]

4.獲得當前捅底的元素2，那么操作同第二步

這個方法其實增加許多不需要的倒出倒入操作，那么有沒有可能我們只在需要的時候對這么大的數據量進行倒入倒出操作呢？

思路二：多次加入，一次倒出
從上一個例子我們可以看見，桶1中的內容一定是輸入順序的逆序，而桶2中的內容則一定和輸入順序相同。那么我們能不能保證無時無刻，桶1中的元素全部位于桶2之后，從而確保每次從桶2中獲得的元素是正確的順序。而當桶2中沒有元素時，只要導入桶1的元素就可以了。

方法是每次添入元素時，仍然直接加入桶1。但是當需要彈出元素時，則從桶2彈出。如果桶2是空的話，那么就把桶1中的內容倒入桶2。這樣，下次加入的元素必然全部位于桶2后的所有元素，而桶2中的元素也能保證位輸入順序。圖例如下：

1.輸入[1,2,3,4,5]

2.彈出1

3.彈出2

4.輸入[6,7]

這樣我們確保了每個元素只會入棧出棧再入棧出棧兩次，即進入桶1，彈出桶1，進入桶2，彈出桶2。極大的減少了不必要的入棧出棧。代碼如下：

public class ImplementQueueusingStacks_232 {
    Stack s1 = new Stack();
    Stack s2 = new Stack();
    /** Push element x to the back of queue. */
    public void push(int x) {
        s1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(s2.isEmpty()){
            while(!s1.isEmpty()){
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        if(s2.isEmpty()){
            while(!s1.isEmpty()){
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return s1.empty() && s2.empty();
    }
}

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

云服務器 GPU云服務器 Implement Stacks Leetcod LeetCode

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

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

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

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

cloud 2019-08-19 10:26 評論0 收藏0
[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
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
前端 | 每天一個 LeetCode

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

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