Java基礎(chǔ)教學(xué)

• ##欄位介紹如何用兩個(gè)堆疊實(shí)作一個(gè)佇列。

# #佇列和堆疊是電腦中兩個(gè)非常重要的資料結(jié)構(gòu)，經(jīng)過前面的學(xué)習(xí)（《佇列》、《堆疊》）我們知道了它們各自的特點(diǎn)，佇列是先進(jìn)先出（FIFO）的，而堆疊是先進(jìn)後面出（FILO）的，那如何用堆疊來實(shí)作佇列呢？這不過是一個(gè)經(jīng)典的面試題，所以本文我們就來實(shí)作一下。

在正式開始之前，我們先來回顧一下堆疊和佇列的常用方法。
• 堆疊（Stack）的常用方法包含以下內(nèi)容：
• ##push()：入堆疊方法，在堆疊頂部新增元素；
• pop()：出棧方法，將棧頂?shù)脑匾瞥齺K傳回元素;

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

##佇列（Queue）的常用方法包含以下內(nèi)容：

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

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

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

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

問題描述

用兩個(gè)堆疊實(shí)作一個(gè)佇列。佇列的語(yǔ)句如下，請(qǐng)實(shí)作它的兩個(gè)函數(shù)appendTail和deleteHead，分別完成在佇列尾部插入整數(shù)和在佇列刪除整數(shù)的功能，若佇列中沒有元素，deleteHead操作返回-1。

範(fàn)例1：

# ##輸入：######["CQueue" ,"appendTail","deleteHead","deleteHead"]######[[],[3],[],[]]### ### 輸出：[null,null,3,-1 ]##########範(fàn)例2：###########輸入：###

["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]

[[],[],[5],[2],[ ],[]]

輸出：[null,-1,null,null,5,2]

提示：

##1 最多會(huì)對(duì)?appendTail、deleteHead 進(jìn)行?10000?次呼叫

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

解解題思路

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

這題實(shí)現(xiàn)的核心思想就是「負(fù)負(fù)得正」，我們先用一個(gè)棧來存入元素（這時(shí)最先進(jìn)入的元素在棧底），然後再將第一個(gè)棧中的元素移動(dòng)到新棧中，此時(shí)最先進(jìn)入的元素就在棧頂了，然後在用第二個(gè)棧出棧時(shí)，整個(gè)執(zhí)行的順序就變成了先進(jìn)先出。

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

步驟一

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

步驟二

##將第一個(gè)堆疊中的元素都會(huì)移動(dòng)到第二個(gè)堆疊中，如下圖所示：

步驟三

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

小結(jié)

從上述圖片可以看出，元素新增順序是1、2、3，最後經(jīng)過兩個(gè)堆疊之後的出棧順序也是1、2 、3，這樣我們就透過兩個(gè)棧實(shí)現(xiàn)了佇列（先進(jìn)先出）。

實(shí)作程式碼

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

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ù)制代碼</integer></integer>

我們?cè)贚eetCode 中提交以上測(cè)試程式碼，執(zhí)行結(jié)果如下：

注意事項(xiàng)

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

第1 個(gè)堆疊只負(fù)責(zé)入堆疊（暫存資料），第2 個(gè)堆疊只負(fù)責(zé)出棧（最終的佇列執(zhí)行順序）；

1. 每次堆疊2 出棧時(shí)都要把所有的元素都出完之後，才能從棧1 中追加（新增）新數(shù)據(jù)，當(dāng)棧2 的數(shù)據(jù)沒有全部出棧完成??時(shí)，不能將棧1 的元素入棧到棧2，這會(huì)導(dǎo)致元素的執(zhí)行順序混亂。
2. 總結(jié)

本文我們經(jīng)過兩個(gè)先進(jìn)後出的棧，透過「負(fù)負(fù)得正」的想法實(shí)現(xiàn)了隊(duì)列先進(jìn)先出的特性，但需要特別注意的是當(dāng)?shù)? 個(gè)棧也就是出棧容器，在非空（棧）時(shí)不能將第1 個(gè)棧中的元素加入到第2 個(gè)棧中，以免造成程式執(zhí)行順序混亂。

相關(guān)免費(fèi)學(xué)習(xí)推薦：

java基礎(chǔ)教學(xué)

以上是如何用兩個(gè)棧實(shí)作一個(gè)佇列？的詳細(xì)內(nèi)容。更多資訊請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！