建站
咨詢
售后
建站咨詢
新聞中心
本文轉(zhuǎn)載自微信公眾號(hào)「神奇的程序員K」，作者神奇的程序員K。轉(zhuǎn)載本文請(qǐng)聯(lián)系神奇的程序員K公眾號(hào)。
創(chuàng)新互聯(lián)建站自2013年創(chuàng)立以來(lái)，先為鄲城等服務(wù)建站，鄲城等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為鄲城企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問(wèn)題。
前言
給你兩個(gè)棧你如何實(shí)現(xiàn)一個(gè)隊(duì)列，給你兩個(gè)隊(duì)列你如何實(shí)現(xiàn)一個(gè)棧。
本文就跟大家分享下這兩個(gè)問(wèn)題的解決思路與實(shí)現(xiàn)過(guò)程，歡迎各位感興趣的開(kāi)發(fā)者閱讀本文。
問(wèn)題分析
我們先來(lái)看下棧與隊(duì)列的特性：
- 棧：最先加入的元素最后出
- 隊(duì)列：最先加入的元素最先出
有關(guān)棧與隊(duì)列的詳細(xì)講解請(qǐng)移步我的另一篇文章：數(shù)據(jù)結(jié)構(gòu):棧與隊(duì)列
有了棧與隊(duì)列的理論基礎(chǔ)后，我們就可以利用其特性來(lái)分析問(wèn)題了，我們先來(lái)看下如何用棧來(lái)實(shí)現(xiàn)隊(duì)列：
- 我們的已知條件只有兩個(gè)棧，將這兩個(gè)棧進(jìn)行標(biāo)識(shí)：棧1、棧2
- 執(zhí)行入隊(duì)操作時(shí)，我們?cè)胤胚M(jìn)棧1。
- 執(zhí)行出隊(duì)操作時(shí)：
- 把棧1的元素壓入棧2
- 棧2頂部元素出棧
上述思路中，我們用棧1來(lái)存儲(chǔ)元素，我們知道棧的規(guī)則是先進(jìn)后出，因此我們將棧1的元素壓入棧2后，將棧2元素出棧時(shí)，剛好符合隊(duì)列的特性。
接下來(lái)，我們來(lái)看下如何用隊(duì)列來(lái)實(shí)現(xiàn)棧：
- 同樣的，我們的已知條件有兩個(gè)隊(duì)列，將這兩個(gè)隊(duì)列進(jìn)行標(biāo)識(shí)：隊(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)過(guò)我們的這番倒騰后，剛好符合了棧的特性。
實(shí)現(xiàn)代碼
經(jīng)過(guò)上述分析，我們有了實(shí)現(xiàn)思路，接下來(lái)我們就將上述思路轉(zhuǎn)化為具體的代碼，下述代碼中將引入我們之前寫(xiě)好的隊(duì)列與棧的實(shí)現(xiàn)代碼，對(duì)此不了解的開(kāi)發(fā)者請(qǐng)移步我的另外兩篇文章：數(shù)組實(shí)現(xiàn)棧與對(duì)象實(shí)現(xiàn)棧、隊(duì)列與雙端隊(duì)列的實(shí)現(xiàn)
棧實(shí)現(xiàn)隊(duì)列
- 創(chuàng)建StacksAndQueues類文件，聲明解決本文問(wèn)題所需要的變量
- // 棧與隊(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;
- }
接下來(lái)，我們通過(guò)一個(gè)例子來(lái)驗(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();
- }
- 接下來(lái)，我們通過(guò)一個(gè)例子來(lái)驗(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
當(dāng)前題目：隊(duì)列實(shí)現(xiàn)棧&棧實(shí)現(xiàn)隊(duì)列
新聞來(lái)源：http://www.dlmjj.cn/article/dpdcpho.html
