leetcode225 implement stack using queues

binta 發布于2019-08-15 13:30 / 2123人閱讀

摘要：題目要求使用隊列來模擬實現一個棧。棧是指先進后出的數據結構，而隊列則是先進先出的數據結構。隊列的包括在隊列尾插入數據，輸出隊列頭的數據，查看隊列的長度，隊列是否為空。

題目要求

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

使用隊列來模擬實現一個棧。
棧是指先進后出的數據結構，而隊列則是先進先出的數據結構。
假設我們分別往棧和隊列中順序輸入[1,2,3]，那么棧的輸出是[3,2,1]，而隊列的輸出的[1,2,3]。

隊列的API包括在隊列尾插入數據，輸出隊列頭的數據，查看隊列的長度，隊列是否為空。

那么我們現在看一下如何通過隊列來實現棧的操作。

方法一：兩個隊列

當插入數據中時，固定往非空的那個隊列插入數據。（如果兩個隊列的值都為空，那么就任選一個隊列插入即可）。當想要獲得棧頂數據或者執行棧的pop操作時，那么就將隊列中的值逐個輸出到另一個隊列中，并輸出原隊列中最后一個元素的值。

下面用圖形展示一下：
1.向數據結構中插入1，因為此時兩個隊列總都為空，因此任選一個隊列插入

2.向數據結構中插入2和3，因為此時隊列一非空，因此插入隊列一

3.模擬pop操作，這是需要將隊列一的內容輸出再輸入到隊列二中并丟棄隊列1中最后一個元素，即為3

4.模擬top操作，類似于pop，將非空隊列的內容逐個轉移至空隊列，并記錄最后的一個元素返回，即為2

代碼如下：

public class Stack {

    LinkedList queue1 = new LinkedList();
    LinkedList queue2 = new LinkedList();
    
    /** Push element x onto stack. */
    public void push(int x) {
        if(queue1.isEmpty()){
            queue2.offer(x);
        }else{
            queue1.offer(x);
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        int top = 0;
        if(queue1.isEmpty()){
            while(queue2.size() > 1){
                top = queue2.poll();
                queue1.offer(top);
            }
            top = queue2.poll();
        }else{
            while(queue1.size() > 1){
                top = queue1.poll();
                queue2.offer(top);
            }
            top = queue1.poll();
        }
        return top;
    }
    
    /** Get the top element. */
    public int top() {
        int top = 0;
        if(queue1.isEmpty()){
            while(!queue2.isEmpty()){
                top = queue2.poll();
                queue1.offer(top);
            }
        }else{
            while(!queue1.isEmpty()){
                top = queue1.poll();
                queue2.offer(top);
            }
        }
        return top;
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }
    
}

思路二：單個隊列模擬棧

思路一使用兩個隊列從而確保值從隊列中丟出的過程不會丟失。但是其實一個隊列已經足以來模擬棧。我們只需要在每一次往隊列中輸入數據時，確保當前隊列中的輸出順序和棧相同即可。同樣我們使用圖片來模擬一下過程。
1.輸入1，這時隊列為空，將1正常輸入

2.輸入2，這時為了確保隊列的輸出順序和棧相同，我需要將1輸出并重新輸入，這時可以把1看成一個新輸入的值，所以將在2之后輸出

3.輸入3，同上一步，在輸入新加入的值后，將余下的值輸出后重新輸入一遍

其實隊列的最大特點就是可以維護原來的輸入順序，因此每次輸出再重新輸入的數據之間的順序不會受到影響。

4.pop和push只需要輸出或者讀取隊首的值即可

class MyStack {

    /** Initialize your data structure here. */
    Queue queue;
    public MyStack() {
        queue = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        int size = queue.size();
        queue.offer(x);
        while (size-- > 0) {
            queue.offer(queue.poll());
        }
        
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return queue.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}

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

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

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

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

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

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

AlanKeene 2019-08-19 10:28 評論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
LeetCode 232：用棧實現隊列 Implement Queue using Stacks

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

cloud 2019-08-19 10:26 評論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
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