[Leetcode] Implement Stack using Queues 用隊列實現棧

ivan_qhz 發布于2019-08-14 12:39 / 2442人閱讀

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

雙隊列法 復雜度

時間 O(N) 空間 O(N)

思路

和Implement Queue using Stack類似，我們也可以用兩個隊列來模擬棧的操作。當push時，我們將數字offer進非空的隊列就行了。當pop時，因為要拿的是隊列最后一個數，我們先將它前面的數offer進另一個隊列，然后多帶帶拿出最后一個數，并且不再offer進另一個隊列，這樣，另一個隊列就少了最后一個數，而我們也拿到了最后一個數，而本來的隊列就變成空了，等待下次的pop操作來填滿。top操作和pop一樣，區別在于我們拿到最后一個數后，還要再把它offer進另一個隊列中。

代碼

class MyStack {
    
    Queue queue1;
    Queue queue2;
    int size;
    
    public MyStack(){
        this.queue1 = new LinkedList();
        this.queue2 = new LinkedList();
        this.size = 0;
    }
    
    // Push element x onto stack.
    public void push(int x) {
        if(queue1.isEmpty()){
            queue2.offer(x);
        } else {
            queue1.offer(x);
        }
        size++;
    }

    // Removes the element on top of the stack.
    public int pop() {
        if(size == 0){
            return -1;
        }
        int res = 0;
        // 將前面的數都offer進另一個隊列，然后拿出最后一個數
        if(queue1.isEmpty()){
            for(int i = 0; i < size - 1; i++){
                queue1.offer(queue2.poll());
            }
            res = queue2.poll();
        } else {
            for(int i = 0; i < size - 1; i++){
                queue2.offer(queue1.poll());
            }
            res = queue1.poll();
        }
        size--;
        return res;
    }

    // Get the top element.
    public int top() {
        if(size == 0){
            return -1;
        }
        // 先執行pop
        int top = pop();
        // 然后將pop出來的數再塞回隊列就行了
        if(queue1.isEmpty()){
            queue2.offer(top);
        } else {
            queue1.offer(top);
        }
        // 注意size也要加1
        size++;
        return top;
    }

    // Return whether the stack is empty.
    public boolean empty() {
        return size == 0;
    }
}

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

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

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

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

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

AlanKeene 2019-08-19 10:28 評論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 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
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