如何使用Java堆棧實現隊列

這篇文章主要講解了“如何使用Java堆棧實現隊列”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“如何使用Java堆棧實現隊列”吧！

Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

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

解題思路

讀完題之后，第一步必然要想清楚棧和隊列的區別，如下圖所示，棧和隊列的基本實現其實都可以看作一個list：

1）那如果是棧的話，[1, 2, 3]入棧之后，指針會指向3，出棧的時候就會pop這個list里的3；

2）如果是隊列的話，[1, 2, 3]入隊之后，指針會指向1，出隊的時候就會pop這個list里的1。

也就是說如果是棧，這個list里從上到下會是[3, 2, 1]，而如果是隊列，則是[1, 2, 3]。因此，問題就轉化為：怎么將一個插入之后會變成[3, 2, 1]的list變成插入之后是[1, 2, 3]。

這個問題一下子很難找到答案，我們退一步思考另外一個問題：假如現在已經是[1, 2, 3]，現在要將4這個元素插入到這個list里面，怎么才能保持[1, 2, 3, 4]？（正如下圖所示）

為了解決這個問題，就需要將4插入到這個list的底部（而不能直接插入到頂部），那什么情況下4才能插入到底部？注意到這個list是一個棧，只有這個棧是空棧的情況下，4才有可能插入到底部。所以，我們要構造出空棧的情況，那如果要將一個非空的棧變成空棧，勢必要pop元素，而且這些元素還必須保存起來，不能丟棄，所以必然要有一個地方，必然要有另外一個數據結構來存儲這些pop出來的元素。

基于上面的思考過程，我們自然會想到額外再使用一個棧

來存儲這些pop出來的元素，如下圖所示。將主棧stack2的元素逐一pop出來并且push到輔助棧stack1中，就可以清空主棧，讓它變成一個空棧。

這樣一來，主棧就可以將新的元素4放入到底部。與此同時，因為元素進入輔助棧stack1之后，順序變成了逆序[3, 2, 1]，所以當這些元素再pop出來導到主棧stack2時，又會跟原來的順序[1, 2, 3]一樣。

至此，整個算法的邏輯就清晰了，我們來重新過一遍。首先，當主棧stack2沒有元素的時候，那就直接放入主棧stack2即可。

接下來會進來第二個元素2，那就按照如下的步驟走：

當新元素3要插入的時候，繼續這個操作即可：

可以看到，通過這種方法，可以始終保持主棧是以隊列的順序存儲元素（參考本文的第一幅圖）。至于pop和peek方法，都只要直接對主棧stack2進行判斷和處理就可以了。

時間復雜度

按照上面的解法，隊列的各種基本操作的時間復雜度分別為：

push操作：整個過程需要將元素從主棧stack2挪到輔助棧stack1（這一步的時間復雜度是O(n)），然后插入新元素（時間復雜度O(1)），最后再挪回主棧stack2（時間復雜度O(n)），所以時間復雜度是O(2n+1)，等于O(n)

pop操作：因為只需要對主棧stack2做判斷，所以只需要O(1)

peek操作：因為只需要對主棧stack2做判斷，所以只需要O(1)

最終實現

Java實現

class MyQueue {

        private LinkedList<Integer> stack1 = new LinkedList<>(); // the aux one
        private LinkedList<Integer> stack2 = new LinkedList<>(); // the true one

        /**
         * Initialize your data structure here.
         */
        public MyQueue() {
        }

        /**
         * Push element x to the back of queue.
         */
        public void push(int x) {
            if (stack2.isEmpty()) {
                stack2.push(x);
            } else {
                while (!stack2.isEmpty()) {
                    stack1.push(stack2.pop());
                }
                stack2.push(x);
                while (!stack1.isEmpty()) {
                    stack2.push(stack1.pop());
                }
            }
        }

        /**
         * Removes the element from in front of queue and returns that element.
         */
        public int pop() {
            if (!stack2.isEmpty()) {
                return stack2.pop();
            }
            return -1;
        }

        /**
         * Get the front element.
         */
        public int peek() {
            if (!stack2.isEmpty()) {
                return stack2.peek();
            }
            return -1;
        }

        /**
         * Returns whether the queue is empty.
         */
        public boolean empty() {
            return stack2.isEmpty();
        }
    }

感謝各位的閱讀，以上就是“如何使用Java堆棧實現隊列”的內容了，經過本文的學習后，相信大家對如何使用Java堆棧實現隊列這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！