如何使用Java堆棧實(shí)現(xiàn)隊(duì)列

這篇文章主要講解了“如何使用Java堆棧實(shí)現(xiàn)隊(duì)列”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“如何使用Java堆棧實(shí)現(xiàn)隊(duì)列”吧！

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

解題思路

讀完題之后，第一步必然要想清楚棧和隊(duì)列的區(qū)別，如下圖所示，棧和隊(duì)列的基本實(shí)現(xiàn)其實(shí)都可以看作一個(gè)list：

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

2）如果是隊(duì)列的話，[1, 2, 3]入隊(duì)之后，指針會(huì)指向1，出隊(duì)的時(shí)候就會(huì)pop這個(gè)list里的1。

也就是說(shuō)如果是棧，這個(gè)list里從上到下會(huì)是[3, 2, 1]，而如果是隊(duì)列，則是[1, 2, 3]。因此，問(wèn)題就轉(zhuǎn)化為：怎么將一個(gè)插入之后會(huì)變成[3, 2, 1]的list變成插入之后是[1, 2, 3]。

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

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

基于上面的思考過(guò)程，我們自然會(huì)想到額外再使用一個(gè)棧

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

這樣一來(lái)，主棧就可以將新的元素4放入到底部。與此同時(shí)，因?yàn)樵剡M(jìn)入輔助棧stack1之后，順序變成了逆序[3, 2, 1]，所以當(dāng)這些元素再pop出來(lái)導(dǎo)到主棧stack2時(shí)，又會(huì)跟原來(lái)的順序[1, 2, 3]一樣。

至此，整個(gè)算法的邏輯就清晰了，我們來(lái)重新過(guò)一遍。首先，當(dāng)主棧stack2沒(méi)有元素的時(shí)候，那就直接放入主棧stack2即可。

接下來(lái)會(huì)進(jìn)來(lái)第二個(gè)元素2，那就按照如下的步驟走：

當(dāng)新元素3要插入的時(shí)候，繼續(xù)這個(gè)操作即可：

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

時(shí)間復(fù)雜度

按照上面的解法，隊(duì)列的各種基本操作的時(shí)間復(fù)雜度分別為：

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

pop操作：因?yàn)橹恍枰獙?duì)主棧stack2做判斷，所以只需要O(1)

peek操作：因?yàn)橹恍枰獙?duì)主棧stack2做判斷，所以只需要O(1)

最終實(shí)現(xiàn)

Java實(shí)現(xiàn)

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堆棧實(shí)現(xiàn)隊(duì)列”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)如何使用Java堆棧實(shí)現(xiàn)隊(duì)列這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！