算法圖解：如何用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列？
本文轉(zhuǎn)載自微信公眾號(hào)「Java中文社群」，作者磊哥 。轉(zhuǎn)載本文請(qǐng)聯(lián)系Java中文社群公眾號(hào)。
本文已收錄至 https://github.com/vipstone/algorithm 《算法圖解》系列。
隊(duì)列和棧是計(jì)算機(jī)中兩個(gè)非常重要的數(shù)據(jù)結(jié)構(gòu)，經(jīng)過前面的學(xué)習(xí)(《隊(duì)列》、《棧》)我們知道了它們各自的特點(diǎn)，隊(duì)列是先進(jìn)先出(FIFO)的，而棧是先進(jìn)后出(FILO)的，那如何用棧來實(shí)現(xiàn)隊(duì)列呢?這可是一道經(jīng)典的面試題，所以本文我們就來實(shí)現(xiàn)一下。
在正式開始之前，我們先來回顧一下棧和隊(duì)列的常用方法。
棧(Stack)的常用方法包含以下這些：
- push()：入棧方法，向棧頂添加元素;
- pop()：出棧方法，將棧頂?shù)脑匾瞥⒎祷卦?
- peek()：查詢棧頂元素，并不會(huì)移除元素。
隊(duì)列(Queue)的常用方法包含以下這些：
- offer()：入隊(duì)方法，向隊(duì)尾添加元素;
- poll()：出隊(duì)方法，從隊(duì)頭移除并返回元素;
- peek()：查詢隊(duì)頭元素，并不會(huì)移除元素。
有了這些前置知識(shí)，接下來我們來看今天的題目。
題目描述
用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列。隊(duì)列的聲明如下，請(qǐng)實(shí)現(xiàn)它的兩個(gè)函數(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
- 最多會(huì)對(duì) appendTail、deleteHead 進(jìn)行 10000 次調(diào)用
- leetcode：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/
解題思路
這道題目的意思其實(shí)很好理解，就是要將先進(jìn)后出的棧改為先進(jìn)先出的隊(duì)列，其實(shí)問題中也給出了一些提示，“用兩個(gè)棧來實(shí)現(xiàn)一個(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è)棧中的元素都移動(dòng)到第二個(gè)棧中，如下圖所示：
步驟三
所有元素從第二個(gè)棧中出棧，如下圖所示：
小結(jié)
從上述圖片可以看出，元素添加順序是 1、2、3，最終經(jīng)過兩個(gè)棧之后的出棧順序也是 1、2、3，這樣我們就通過兩個(gè)棧實(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();
- }
- }
我們?cè)?LeetCode 中提交以上測(cè)試代碼，執(zhí)行結(jié)果如下：
注意事項(xiàng)
在整個(gè)實(shí)現(xiàn)過程中有兩個(gè)小細(xì)節(jié)需要特別注意一下：
第 1 個(gè)棧只負(fù)責(zé)入棧(暫存數(shù)據(jù))，第 2 個(gè)棧只負(fù)責(zé)出棧(最終的隊(duì)列執(zhí)行順序);
每次棧 2 出棧時(shí)都要把所有的元素都出完之后，才能從棧 1 中追加(添加)新數(shù)據(jù)，當(dāng)棧 2 的數(shù)據(jù)沒有全部出棧完成時(shí)，不能將棧 1 的元素入棧到棧 2，這樣會(huì)導(dǎo)致元素的執(zhí)行順序混亂。
總結(jié)
本文我們通過兩個(gè)先進(jìn)后出的棧，通過“負(fù)負(fù)得正”的思路實(shí)現(xiàn)了隊(duì)列先進(jìn)先出的特性，但需要特別注意的是當(dāng)?shù)?2 個(gè)棧也就是出棧容器，在非空(棧)時(shí)不能將第 1 個(gè)棧中的元素添加到第 2 個(gè)棧中，以免造成程序執(zhí)行順序混亂。
原文鏈接：https://mp.weixin.qq.com/s/18GdYCCaaltx4ZMVkPsptg
