怎么用兩個棧實現(xiàn)一個隊列

這篇文章主要講解了“怎么用兩個棧實現(xiàn)一個隊列”，文中的講解內(nèi)容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“怎么用兩個棧實現(xiàn)一個隊列”吧！

在正式開始之前，我們先來回顧一下棧和隊列的常用方法。

棧(Stack)的常用方法包含以下這些：

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

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

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

隊列(Queue)的常用方法包含以下這些：

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

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

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

有了這些前置知識，接下來我們來看今天的題目。

題目描述

用兩個棧實現(xiàn)一個隊列。隊列的聲明如下，請實現(xiàn)它的兩個函數(shù) appendTail 和  deleteHead，分別完成在隊列尾部插入整數(shù)和在隊列頭部刪除整數(shù)的功能，若隊列中沒有元素，deleteHead 操作返回 -1。

示例 1：

輸入： ["CQueue","appendTail","deleteHead","deleteHead"] [[],[3],[],[]] 輸出：[null,null,3,-1]

示例 2：

輸入： ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"] [[],[],[5],[2],[],[]] 輸出：[null,-1,null,null,5,2]

提示：

1 <= values <= 10000 最多會對 appendTail、deleteHead 進行 10000 次調(diào)用 leetcode：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/

解題思路

這道題目的意思其實很好理解，就是要將先進后出的棧改為先進先出的隊列，其實問題中也給出了一些提示，“用兩個棧來實現(xiàn)一個隊列”。這道題實現(xiàn)的核心思想就是「負負得正」，我們先用一個棧來存入元素(這時最先進入的元素在棧底)，然后再將第一個棧中的元素移動到新棧中，此時最先進入的元素就在棧頂了，然后在用第二個棧出棧時，整個執(zhí)行的順序就變成了先進先出。

接下來，我們用圖解的方式來實現(xiàn)一下整個流程。

步驟一

先將元素入棧到第一個棧中，如下圖所示：

步驟二

將第一個棧中的元素都移動到第二個棧中，如下圖所示：

步驟三

所有元素從第二個棧中出棧，如下圖所示：

小結(jié)

從上述圖片可以看出，元素添加順序是 1、2、3，最終經(jīng)過兩個棧之后的出棧順序也是 1、2、3，這樣我們就通過兩個棧實現(xiàn)了隊列(先進先出)。

實現(xiàn)代碼

接下來我們就用代碼來實現(xiàn)一下以上思路：

class CQueue {     Stack<Integer> inputStack; // 入棧的容器（添加時操作)     Stack<Integer> outputStack; // 出棧和查詢的棧容器      public CQueue() {         inputStack = new Stack();         outputStack = new Stack();     }      // 添加操作     public void appendTail(int value) {         inputStack.push(value);     }      // 刪除操作     public int deleteHead() {         if (!outputStack.isEmpty()) {             // 出棧容器不為空             return outputStack.pop();         } else if (!inputStack.isEmpty()) {             // 入棧 stack 全部轉(zhuǎn)移到出棧 stack             while (!inputStack.isEmpty()) {                 outputStack.push(inputStack.pop());             }         }         return outputStack.isEmpty() ? -1 : outputStack.pop();     } }

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

注意事項

在整個實現(xiàn)過程中有兩個小細節(jié)需要特別注意一下：

第 1 個棧只負責入棧(暫存數(shù)據(jù))，第 2 個棧只負責出棧(最終的隊列執(zhí)行順序);

每次棧 2 出棧時都要把所有的元素都出完之后，才能從棧 1 中追加(添加)新數(shù)據(jù)，當棧 2 的數(shù)據(jù)沒有全部出棧完成時，不能將棧 1 的元素入棧到棧  2，這樣會導致元素的執(zhí)行順序混亂。

感謝各位的閱讀，以上就是“怎么用兩個棧實現(xiàn)一個隊列”的內(nèi)容了，經(jīng)過本文的學習后，相信大家對怎么用兩個棧實現(xiàn)一個隊列這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！