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

資訊專欄INFORMATION COLUMN

leetcode232 Implement Queue using Stacks

golden_hamster / 2437人閱讀

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

題目要求 
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).

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

思路與代碼

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

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

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

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

3.輸入[6]

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

這個方法其實增加許多不需要的倒出倒入操作，那么有沒有可能我們只在需要的時候?qū)@么大的數(shù)據(jù)量進行倒入倒出操作呢？

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

方法是每次添入元素時，仍然直接加入桶1。但是當(dāng)需要彈出元素時，則從桶2彈出。如果桶2是空的話，那么就把桶1中的內(nèi)容倒入桶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();
    }
}


想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~

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

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

相關(guān)文章

  • LeetCode 232：用棧實現(xiàn)隊列 Implement Queue using Stacks

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

    cloud 評論0 收藏0

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

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

    Martin91 評論0 收藏0

  • 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 攻略 - 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

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

    張漢慶 評論0 收藏0

發(fā)表評論

0條評論

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