java中用兩個棧實(shí)現(xiàn)一個隊(duì)列的案例

小編給大家分享一下java中用兩個棧實(shí)現(xiàn)一個隊(duì)列的案例，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

Java基礎(chǔ)教程欄目介紹如何用兩個棧實(shí)現(xiàn)一個隊(duì)列。

隊(duì)列和棧是計(jì)算機(jī)中兩個非常重要的數(shù)據(jù)結(jié)構(gòu)，經(jīng)過前面的學(xué)習(xí)（《隊(duì)列》、《?！罚┪覀冎懒怂鼈兏髯缘奶攸c(diǎn)，隊(duì)列是先進(jìn)先出（FIFO）的，而棧是先進(jìn)后出（FILO）的，那如何用棧來實(shí)現(xiàn)隊(duì)列呢？這可是一道經(jīng)典的面試題，所以本文我們就來實(shí)現(xiàn)一下。

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

棧（Stack）的常用方法包含以下這些：

• push()：入棧方法，向棧頂添加元素；
• pop()：出棧方法，將棧頂?shù)脑匾瞥⒎祷卦兀?/li>
• peek()：查詢棧頂元素，并不會移除元素。

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

• offer()：入隊(duì)方法，向隊(duì)尾添加元素；
• poll()：出隊(duì)方法，從隊(duì)頭移除并返回元素；
• peek()：查詢隊(duì)頭元素，并不會移除元素。

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

題目描述

用兩個棧實(shí)現(xiàn)一個隊(duì)列。隊(duì)列的聲明如下，請實(shí)現(xiàn)它的兩個函數(shù) appendTail 和 deleteHead，分別完成在隊(duì)列尾部插入整數(shù)和在隊(duì)列頭部刪除整數(shù)的功能，若隊(duì)列中沒有元素，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 進(jìn)行 10000 次調(diào)用

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

解題思路

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

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

步驟一

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

步驟二

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

步驟三

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

小結(jié)

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

實(shí)現(xiàn)代碼

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

class CQueue {
    Stack<Integer> inputStack; // 入棧的容器（添加時(shí)操作)
    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();
    }
}復(fù)制代碼

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

注意事項(xiàng)

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

1. 第 1 個棧只負(fù)責(zé)入棧（暫存數(shù)據(jù)），第 2 個棧只負(fù)責(zé)出棧（最終的隊(duì)列執(zhí)行順序）；
2. 每次棧 2 出棧時(shí)都要把所有的元素都出完之后，才能從棧 1 中追加（添加）新數(shù)據(jù)，當(dāng)棧 2 的數(shù)據(jù)沒有全部出棧完成時(shí)，不能將棧 1 的元素入棧到棧 2，這樣會導(dǎo)致元素的執(zhí)行順序混亂。

以上是java中用兩個棧實(shí)現(xiàn)一個隊(duì)列的案例的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習(xí)更多知識，歡迎關(guān)注億速云行業(yè)資訊頻道！