隊(duì)列實(shí)現(xiàn)棧的方法有哪些

本篇內(nèi)容介紹了“隊(duì)列實(shí)現(xiàn)棧的方法有哪些”的有關(guān)知識，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

先來回顧一下棧(Stack)和隊(duì)列(Queue)的特性和常見方法。

棧是后進(jìn)先出(LIFO)的數(shù)據(jù)結(jié)構(gòu)，常見方法如下：

• push()：入棧方法，向棧頂添加元素;

• pop()：出棧方法，將棧頂?shù)脑匾瞥⒎祷卦?

• peek()：查詢棧頂元素，并不會(huì)移除元素。

隊(duì)列是先進(jìn)先出(FIFO)的數(shù)據(jù)結(jié)構(gòu)，常見方法如下：

• offer()：入隊(duì)方法，向隊(duì)尾添加元素;

• poll()：出隊(duì)方法，從隊(duì)頭移除并返回元素;

• peek()：查詢隊(duì)頭元素，并不會(huì)移除元素。

知道了這些基礎(chǔ)內(nèi)容之后，就來看今天的問題吧。

題目描述使用隊(duì)列實(shí)現(xiàn)棧的下列操作：

• push(x) -- 元素 x 入棧

• pop() -- 移除棧頂元素

• top() -- 獲取棧頂元素

• empty() -- 返回棧是否為空

注意:

• 你只能使用隊(duì)列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty  這些操作是合法的;

• 你所使用的語言也許不支持隊(duì)列。你可以使用 list 或者 deque(雙端隊(duì)列)來模擬一個(gè)隊(duì)列 , 只要是標(biāo)準(zhǔn)的隊(duì)列操作即可;

• 你可以假設(shè)所有操作都是有效的(例如, 對一個(gè)空的棧不會(huì)調(diào)用 pop 或者 top 操作)。

LeetCode  225：https://leetcode-cn.com/problems/implement-stack-using-queues/

題目解析

這道題的題目很好理解：只需要將先進(jìn)先出的隊(duì)列，轉(zhuǎn)換為后進(jìn)先出的“?！本涂梢粤?，我們可以從多個(gè)方向入手來實(shí)現(xiàn)此功能，比如使用兩個(gè)隊(duì)列插入并交換的方式，或者是一個(gè)隊(duì)列插入再交換的方式，或雙端隊(duì)列的方式來實(shí)現(xiàn)此功能，具體實(shí)現(xiàn)方法和代碼如下。

實(shí)現(xiàn)方法 1：兩個(gè)隊(duì)列實(shí)現(xiàn)棧

之前我們用兩個(gè)棧實(shí)現(xiàn)了一個(gè)隊(duì)列的文章中，主要使用的是「負(fù)負(fù)得正」的思想，那么當(dāng)看到此道題時(shí)，首先應(yīng)該想到的是用兩個(gè)隊(duì)列來實(shí)現(xiàn)一個(gè)棧，但這里的實(shí)現(xiàn)思路和用棧實(shí)現(xiàn)隊(duì)列的思路又略有不同，因?yàn)殛?duì)列都是先進(jìn)先出的，我們可以把它理解為「正數(shù)」，那么也就不能用「負(fù)負(fù)得正」的思想了，我們這里使用兩個(gè)隊(duì)列來實(shí)現(xiàn)棧，主要的操作思路是先將元素插入一個(gè)臨時(shí)隊(duì)列中，然后再將另一個(gè)隊(duì)列的所有元素插入到臨時(shí)隊(duì)列的尾部，從而實(shí)現(xiàn)后進(jìn)先出功能的，具體的實(shí)現(xiàn)步驟如下。

步驟一

添加首個(gè)元素，入列到臨時(shí)隊(duì)列 queue2：

步驟二

因?yàn)檎疥?duì)列中無元素，因此無需將 queue1 中的元素移動(dòng)到臨時(shí)隊(duì)列 queue2 的尾部，直接將臨時(shí)隊(duì)列和正式隊(duì)列互換即可：

步驟三

添加第二個(gè)元素，先入列到臨時(shí)隊(duì)列 queue2：

步驟四

再將 queue1 中的元素移動(dòng)到 queue2 的尾部，如下所示：

步驟五

再將 queue1 和 queue2 進(jìn)行互換：

步驟六

執(zhí)行出隊(duì)操作：

最終效果

從最終的效果圖我們可以看出，通過兩個(gè)隊(duì)列已經(jīng)實(shí)現(xiàn)了后進(jìn)先出的特性，也就是完成了從隊(duì)列到棧的轉(zhuǎn)換，實(shí)現(xiàn)代碼如下：

import java.util.Queue;  class MyStack {      Queue<Integer> queue1;     Queue<Integer> queue2;      public MyStack() {         queue1 = new LinkedBlockingQueue();         queue2 = new LinkedBlockingQueue();     }      /**      * 入棧      */     public void push(int x) {         // 1.入列臨時(shí)隊(duì)列二         queue2.offer(x);         // 2.將隊(duì)列一的所有元素移動(dòng)到隊(duì)列二         while (!queue1.isEmpty()) {             queue2.offer(queue1.poll());         }         // 3.隊(duì)列一和隊(duì)列二互換         Queue<Integer> temp = queue1;         queue1 = queue2;         queue2 = temp;     }      /**      * 出棧并返回此元素      */     public int pop() {         return queue1.poll();     }      /**      * 查詢棧頂元素      */     public int top() {         return queue1.peek();     }      /**      * 判斷是否為空      */     public boolean empty() {         return queue1.isEmpty();     } }

我們在 LeetCode 中提交以上測試代碼，執(zhí)行結(jié)果如下：

此方法很穩(wěn)，竟然擊敗了 100% 的用戶。

實(shí)現(xiàn)方法 2：一個(gè)隊(duì)列實(shí)現(xiàn)棧

那我們可以不可以用一個(gè)隊(duì)列來實(shí)現(xiàn)棧呢?答案是肯定的。

我們只需要執(zhí)行以下兩個(gè)步驟就可以實(shí)現(xiàn)將隊(duì)列轉(zhuǎn)換為棧了，具體實(shí)現(xiàn)步驟如下：

將元素入列到隊(duì)尾;

再將除隊(duì)尾之外的所有元素移除并重寫入列。

這樣操作之后，最后進(jìn)入的隊(duì)尾元素反而變成了隊(duì)頭元素，也就實(shí)現(xiàn)了后進(jìn)先出的功能了，如下圖所示。

步驟一

元素 1 入列：

步驟二

元素 2 入列：

步驟三

將最后一個(gè)元素之前的所有元素，也就是元素 1，出列重新入列：

步驟四

執(zhí)行出隊(duì)操作：

最終效果

以上思路的實(shí)現(xiàn)代碼如下：

import java.util.Queue;  class MyStack {     Queue<Integer> queue1;      public MyStack() {         queue1 = new LinkedBlockingQueue();     }      /**      * 入棧      */     public void push(int x) {         // 獲取原隊(duì)列長度（要移動(dòng)的次數(shù)）         int count = queue1.size();         // 將元素放入隊(duì)尾         queue1.offer(x);         // 將除最后一個(gè)元素外，其他的元素重新入隊(duì)         for (int i = 0; i < count; i++) {             System.out.println("for");             queue1.offer(queue1.poll());         }     }      /**      * 出棧并返回此元素      */     public int pop() {         return queue1.poll();     }      /**      * 查詢棧頂元素      */     public int top() {         return queue1.peek();     }      /**      * 判斷是否為空      */     public boolean empty() {         return queue1.isEmpty();     } } 我們把以上代碼在 LeetCode

我們把以上代碼在 LeetCode 中提交，執(zhí)行結(jié)果如下：

此方法依舊很穩(wěn)，也是同樣的擊敗了 100% 的用戶，只不過此方法在內(nèi)存方面有更好的表現(xiàn)。

實(shí)現(xiàn)方法 3：雙端隊(duì)列實(shí)現(xiàn)棧

如果覺得以上方法比較難的話，最后我們還有一個(gè)更簡單的實(shí)現(xiàn)方法，我們可以使用 Java 中的雙端隊(duì)列 ArrayDeque  來實(shí)現(xiàn)將元素可以插入隊(duì)頭或隊(duì)尾，同樣移除也是，那么這樣我們就可以從隊(duì)尾入再從隊(duì)尾出，從而就實(shí)現(xiàn)了棧的功能了。

雙端隊(duì)列結(jié)構(gòu)如下：

我們來演示一下用雙端隊(duì)列實(shí)現(xiàn)棧的具體步驟。

步驟一

元素 1 入隊(duì)：

步驟二

元素 2 入隊(duì)(隊(duì)尾)：

步驟三

再從隊(duì)尾出隊(duì)：

最終效果

以上思路的實(shí)現(xiàn)代碼如下：

import java.util.ArrayDeque;  class MyStack {     ArrayDeque<Integer> deque;      public MyStack() {         deque = new ArrayDeque<>();     }      /**      * 入棧      */     public void push(int x) {         deque.offer(x);     }      /**      * 出棧并返回此元素      */     public int pop() {         return deque.pollLast();     }      /**      * 查詢棧頂元素      */     public int top() {         return empty() ? -1 : deque.peekLast();     }      /**      * 判斷是否為空      */     public boolean empty() {         return deque.isEmpty();     } }

我們把以上代碼在 LeetCode 中提交，執(zhí)行結(jié)果如下：

“隊(duì)列實(shí)現(xiàn)棧的方法有哪些”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！