如何用兩個棧實作一個佇列？

Java基礎教學

• ##欄位介紹如何用兩個堆疊實作一個佇列。

# #佇列和堆疊是電腦中兩個非常重要的資料結構，經過前面的學習（《佇列》、《堆疊》）我們知道了它們各自的特點，佇列是先進先出（FIFO）的，而堆疊是先進後面出（FILO）的，那如何用堆疊來實作佇列呢？這不過是一個經典的面試題，所以本文我們就來實作一下。

在正式開始之前，我們先來回顧一下堆疊和佇列的常用方法。
• 堆疊（Stack）的常用方法包含以下內容：
• ##push()：入堆疊方法，在堆疊頂部新增元素；
• pop()：出棧方法，將棧頂的元素移除並傳回元素;

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

##佇列（Queue）的常用方法包含以下內容：

##offer()：入隊方法，將元素加入隊尾；

poll()：出隊方法，從隊頭移除並返回元素；

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

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

問題描述

用兩個堆疊實作一個佇列。佇列的語句如下，請實作它的兩個函數appendTail和deleteHead，分別完成在佇列尾部插入整數和在佇列刪除整數的功能，若佇列中沒有元素，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 最多會對 appendTail、deleteHead 進行 10000 次呼叫

leetcode：leetcode-cn.com/problems/yo…

解解題思路

這題目的意思其實很好理解，就是要將先進後出的棧改為先進先出的隊列，其實問題中也給了一些提示，「用兩個棧來實作一個隊列」。

這題實現的核心思想就是「負負得正」，我們先用一個棧來存入元素（這時最先進入的元素在棧底），然後再將第一個棧中的元素移動到新棧中，此時最先進入的元素就在棧頂了，然後在用第二個棧出棧時，整個執行的順序就變成了先進先出。

接下來，我們用圖解的方式來實現整個流程。

步驟一

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

步驟二

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

步驟三

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

小結

從上述圖片可以看出，元素新增順序是1、2、3，最後經過兩個堆疊之後的出棧順序也是1、2 、3，這樣我們就透過兩個棧實現了佇列（先進先出）。

實作程式碼

接下來我們就用程式碼來實作以上思路：

class CQueue {
    Stack inputStack; // 入栈的容器（添加时操作)
    Stack 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 全部转移到出栈 stack
            while (!inputStack.isEmpty()) {
                outputStack.push(inputStack.pop());
            }
        }        return outputStack.isEmpty() ? -1 : outputStack.pop();
    }
}复制代码

我們在LeetCode 中提交以上測試程式碼，執行結果如下：

注意事項

在整個實作過程中有兩個小細節需要特別注意一下：

第1 個堆疊只負責入堆疊（暫存資料），第2 個堆疊只負責出棧（最終的佇列執行順序）；

1. 每次堆疊2 出棧時都要把所有的元素都出完之後，才能從棧1 中追加（新增）新數據，當棧2 的數據沒有全部出棧完成​​時，不能將棧1 的元素入棧到棧2，這會導致元素的執行順序混亂。
2. 總結

本文我們經過兩個先進後出的棧，透過「負負得正」的想法實現了隊列先進先出的特性，但需要特別注意的是當第2 個棧也就是出棧容器，在非空（棧）時不能將第1 個棧中的元素加入到第2 個棧中，以免造成程式執行順序混亂。

相關免費學習推薦：

java基礎教學

以上是如何用兩個棧實作一個佇列？的詳細內容。更多資訊請關注PHP中文網其他相關文章！