[[384374]]

本文轉(zhuǎn)載自微信公眾號「神奇的程序員K」，作者神奇的程序員K。轉(zhuǎn)載本文請聯(lián)系神奇的程序員K公眾號。

前言

給你兩個(gè)棧你如何實(shí)現(xiàn)一個(gè)隊(duì)列，給你兩個(gè)隊(duì)列你如何實(shí)現(xiàn)一個(gè)棧。

本文就跟大家分享下這兩個(gè)問題的解決思路與實(shí)現(xiàn)過程，歡迎各位感興趣的開發(fā)者閱讀本文。

問題分析

我們先來看下棧與隊(duì)列的特性：

• 棧：最先加入的元素最后出
• 隊(duì)列：最先加入的元素最先出

有關(guān)棧與隊(duì)列的詳細(xì)講解請移步我的另一篇文章：數(shù)據(jù)結(jié)構(gòu):棧與隊(duì)列

有了棧與隊(duì)列的理論基礎(chǔ)后，我們就可以利用其特性來分析問題了，我們先來看下如何用棧來實(shí)現(xiàn)隊(duì)列：

• 我們的已知條件只有兩個(gè)棧，將這兩個(gè)棧進(jìn)行標(biāo)識：棧1、棧2
• 執(zhí)行入隊(duì)操作時(shí)，我們元素放進(jìn)棧1。
• 執(zhí)行出隊(duì)操作時(shí)：
  • 把棧1的元素壓入棧2
  • 棧2頂部元素出棧

上述思路中，我們用棧1來存儲元素，我們知道棧的規(guī)則是先進(jìn)后出，因此我們將棧1的元素壓入棧2后，將棧2元素出棧時(shí)，剛好符合隊(duì)列的特性。

接下來，我們來看下如何用隊(duì)列來實(shí)現(xiàn)棧：

• 同樣的，我們的已知條件有兩個(gè)隊(duì)列，將這兩個(gè)隊(duì)列進(jìn)行標(biāo)識：隊(duì)列1，隊(duì)列2
• 執(zhí)行入棧操作時(shí)，將元素放進(jìn)隊(duì)列1
• 執(zhí)行出棧操作時(shí)：
  • 如果隊(duì)列2為空，我們將隊(duì)列1中除隊(duì)首外的元素放進(jìn)隊(duì)列2
  • 如果隊(duì)列2不為空，我們將隊(duì)列2的元素放進(jìn)隊(duì)列1
  • 隊(duì)列1元素出隊(duì)

上述思路中，我們將元素都放入了隊(duì)列1，出棧時(shí)，我們只保留隊(duì)列1的隊(duì)首元素，其他元素全部放入了隊(duì)列2，隨后將隊(duì)列2的元素又放回了隊(duì)列1，最后將隊(duì)列1的元素出隊(duì)，經(jīng)過我們的這番倒騰后，剛好符合了棧的特性。

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

經(jīng)過上述分析，我們有了實(shí)現(xiàn)思路，接下來我們就將上述思路轉(zhuǎn)化為具體的代碼，下述代碼中將引入我們之前寫好的隊(duì)列與棧的實(shí)現(xiàn)代碼，對此不了解的開發(fā)者請移步我的另外兩篇文章：數(shù)組實(shí)現(xiàn)棧與對象實(shí)現(xiàn)棧、隊(duì)列與雙端隊(duì)列的實(shí)現(xiàn)

棧實(shí)現(xiàn)隊(duì)列

• 創(chuàng)建StacksAndQueues類文件，聲明解決本文問題所需要的變量

// 棧與隊(duì)列的相關(guān)操作 
import Stack from "../../StackTest/lib/Stack.ts"; 
import Queue from "../../QueueTest/lib/Queue.ts"; 
 
export default class StacksAndQueues { 
    private firstStacks: Stack; 
    private secondStacks: Stack; 
    private firstQueues: Queue; 
    private secondQueues: Queue; 
 
    constructor() { 
        this.firstStacks = new Stack(); 
        this.secondStacks = new Stack(); 
        this.firstQueues = new Queue(); 
        this.secondQueues = new Queue(); 
    } 
} 

• 實(shí)現(xiàn)入隊(duì)函數(shù)

// 入隊(duì) 
    enqueue(key: string | number): void { 
        // 入棧1 
        this.firstStacks.push(key); 
    } 

• 實(shí)現(xiàn)出隊(duì)函數(shù)

// 出隊(duì) 
   dequeue() { 
       while (!this.firstStacks.isEmpty()) { 
           this.secondStacks.push(this.firstStacks.pop()); 
       } 
       if (!this.secondStacks.isEmpty()) { 
           // 出棧2 
           return this.secondStacks.pop(); 
       } 
       return null; 
   } 

接下來，我們通過一個(gè)例子來驗(yàn)證下上述代碼能否正常執(zhí)行：

import StacksAndQueues from "./lib/StacksAndQueues.ts"; 
 
// 用棧實(shí)現(xiàn)隊(duì)列 
const stacksAndQueues = new StacksAndQueues(); 
stacksAndQueues.enqueue(3); 
stacksAndQueues.enqueue(9); 
stacksAndQueues.enqueue(12); 
console.log("出隊(duì)", stacksAndQueues.dequeue()); 
console.log("出隊(duì)", stacksAndQueues.dequeue()); 
console.log("出隊(duì)", stacksAndQueues.dequeue()); 

隊(duì)列實(shí)現(xiàn)棧

• 實(shí)現(xiàn)入棧函數(shù)

// 入棧 
   stackPush(key: string | number) { 
       // 入隊(duì)1 
       this.firstQueues.enqueue(key); 
   } 

• 實(shí)現(xiàn)出棧函數(shù)

// 出棧 
    stackPop() { 
        if (this.firstQueues.isEmpty()) { 
            return null; 
        } 
        // 隊(duì)列2為空 
        if (this.secondQueues.isEmpty()) { 
            while (this.firstQueues.size() != 1) { 
                // 將隊(duì)列1除隊(duì)首外的元素放進(jìn)隊(duì)列2 
                this.secondQueues.enqueue(this.firstQueues.dequeue()); 
            } 
        } 
 
        // 隊(duì)列2不為空 
        while (!this.secondQueues.isEmpty()) { 
            // 將隊(duì)列2的元素放進(jìn)隊(duì)列1 
            this.firstQueues.enqueue(this.secondQueues.dequeue()); 
        } 
        // 隊(duì)列1出隊(duì) 
        return this.firstQueues.dequeue(); 
    } 

• 接下來，我們通過一個(gè)例子來驗(yàn)證下上述代碼能否正常執(zhí)行：

// 隊(duì)列實(shí)現(xiàn)棧 
stacksAndQueues.stackPush(3); 
stacksAndQueues.stackPush(9); 
stacksAndQueues.stackPush(12); 
console.log("出棧", stacksAndQueues.stackPop()); 
console.log("出棧", stacksAndQueues.stackPop()); 
console.log("出棧", stacksAndQueues.stackPop()); 

代碼地址

本文實(shí)現(xiàn)代碼的完整地址如下：

• StacksAndQueues.ts