算法---兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列

asoren 發(fā)布于2019-08-20 15:58 / 2833人閱讀

摘要：但是數(shù)據(jù)結(jié)構(gòu)知識(shí)的需要，數(shù)據(jù)結(jié)構(gòu)中對(duì)隊(duì)列棧的定義很明確棧，先進(jìn)后出隊(duì)列，先進(jìn)先出現(xiàn)在要用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列，那么首先定義一個(gè)棧構(gòu)造函數(shù)吧。

其實(shí)JS很“流氓的”，JS的數(shù)組完全既可以是隊(duì)列也可以是棧。
因?yàn)閿?shù)組的push,pop就是棧的一組方法嘛。
數(shù)據(jù)的push,shift就是隊(duì)列的一組方法嘛。
但是數(shù)據(jù)結(jié)構(gòu)知識(shí)的需要，數(shù)據(jù)結(jié)構(gòu)中對(duì)隊(duì)列、棧的定義很明確：

棧，先進(jìn)后出

隊(duì)列，先進(jìn)先出

現(xiàn)在要用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列，那么首先定義一個(gè)棧構(gòu)造函數(shù)吧。

定義一個(gè)棧Stack構(gòu)造函數(shù)

new兩個(gè)Stack，stack1,stack2

stack1實(shí)現(xiàn)隊(duì)列的進(jìn)就好了

stack2實(shí)現(xiàn)隊(duì)列的出就好了
重點(diǎn)來了，進(jìn)的時(shí)候去的是stack1，怎么從stack2出數(shù)據(jù)呢

當(dāng)棧2為空，棧1不為空時(shí)，把棧1的數(shù)據(jù)依次pop出去到棧2中，這樣再棧2pop時(shí)就是隊(duì)列應(yīng)該pop的數(shù)據(jù)了

上代碼：

function Queue(){
    var items = [];
    function Stack() {
        var item = [];
        this.push = function (elem) {
            item.push(elem);
            return item;
        };
        this.pop = function () {
            return item.pop();
        };
        this.isEmpty = function () {
            return item.length === 0;
        };
        this.get = function () {
            return item;
        };
    }
    var stack1 = new Stack();
    var stack2 = new Stack();
    this.push = function (elem) {
        stack1.push(elem);
        return items.push(elem);
    }
    this.pop = function () {
        if(stack1.isEmpty() && stack2.isEmpty()){
            throw new Error("空隊(duì)列");
        }
        if(stack2.isEmpty() && !stack1.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }
    };
    this.get = function () {
        if(!stack2.isEmpty()){
            return stack2.get().reverse();
        }else{
            return items;
        }
    }
}
var queue = new Queue();
queue.push(0);
queue.push(1);
queue.push(2);
queue.get();
queue.pop();
queue.get();

云服務(wù)器 GPU云服務(wù)器兩個(gè)棧 java 棧隊(duì)列 java 棧隊(duì)列面試 java 手寫一個(gè)棧

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/82624.html

相關(guān)文章

算法面試：隊(duì)列實(shí)現(xiàn)棧的方案

摘要：基本解決方案按照上述的大體思路，我們給出解決方案入棧和出棧都在中完成，只作為臨時(shí)中轉(zhuǎn)空間。入棧入隊(duì)出棧除隊(duì)尾的元素外將其他所有元素出隊(duì)，再入隊(duì)中轉(zhuǎn)暫存，然后將中的元素出隊(duì)出棧。聲明：碼字不易，轉(zhuǎn)載請(qǐng)注明出處，歡迎文章下方討論交流。前言：Java數(shù)據(jù)結(jié)構(gòu)與算法專題會(huì)不定時(shí)更新，歡迎各位讀者監(jiān)督。本篇介紹的是如何用兩個(gè)隊(duì)列實(shí)現(xiàn)棧的問題。這道題作為上一篇文章算法面試：棧實(shí)現(xiàn)隊(duì)列的方案的姊...

dabai 2019-08-16 11:06 評(píng)論0 收藏0
算法面試：棧實(shí)現(xiàn)隊(duì)列的方案

摘要：解決方案二入隊(duì)都在中進(jìn)行，用于隊(duì)列，同時(shí)保證所有元素都在一個(gè)棧里，且遵循以下約束入隊(duì)不管空與否，都將中的所有元素壓入中出隊(duì)若中不為空，則直接從中彈出元素若為空，則說明隊(duì)列為空，不能出隊(duì)。聲明：碼字不易，轉(zhuǎn)載請(qǐng)注明出處，歡迎文章下方討論交流。前言：Java數(shù)據(jù)結(jié)構(gòu)與算法專題會(huì)不定時(shí)更新，歡迎各位讀者監(jiān)督。本篇文章介紹一個(gè)有趣的問題：用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列。這道題來自互聯(lián)網(wǎng)公司的算法面試...

韓冰 2019-08-19 10:43 評(píng)論0 收藏0
算法學(xué)習(xí)之?dāng)?shù)據(jù)結(jié)構(gòu)線性表、堆、棧

摘要：棧底是固定的，而棧頂浮動(dòng)的如果棧中元素個(gè)數(shù)為零則被稱為空棧。入棧將數(shù)據(jù)保存到棧頂。鏈棧鏈棧是指棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，是沒有附加頭節(jié)點(diǎn)的運(yùn)算受限的單鏈表，棧頂指針是鏈表的頭指針。一、喜歡單挑線性表 1.線性表的特性線性表是一個(gè)線性結(jié)構(gòu)，它是一個(gè)含有n≥0個(gè)節(jié)點(diǎn)的有限序列。在節(jié)點(diǎn)中，有且僅有一個(gè)開始節(jié)點(diǎn)沒有前驅(qū)并有一個(gè)后繼節(jié)點(diǎn)，有且僅有一個(gè)終端節(jié)點(diǎn)沒有后繼并有一個(gè)前驅(qū)節(jié)點(diǎn)。其他的節(jié)點(diǎn)都有且...

huaixiaoz 2019-06-27 14:11 評(píng)論0 收藏0
【面試算法】由兩個(gè)棧組成的隊(duì)列

摘要：題目編寫一個(gè)類，用兩個(gè)棧實(shí)現(xiàn)隊(duì)列，支持隊(duì)列的基本操作，，代碼實(shí)現(xiàn) 【題目】編寫一個(gè)類，用兩個(gè)棧實(shí)現(xiàn)隊(duì)列，支持隊(duì)列的基本操作（add，poll，peek）代碼實(shí)現(xiàn) public class TwoStacksQueue { private Stack stackPush; private Stack stackPop; public TwoStacksQue...

wenshi11019 2019-08-14 15:17 評(píng)論0 收藏0
學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊(duì)列

摘要：于是翻出了機(jī)房里的這本學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法開始學(xué)習(xí)程序員的基礎(chǔ)知識(shí)。這本書用了我最熟悉的來實(shí)現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)和算法，而且書很薄，可以說是一本不錯(cuò)的入門教程。隊(duì)列在頭部刪除元素，尾部添加元素。本系列所有文章：第一篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊(duì)列第二篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之鏈表第三篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之集合第四篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之字典和散列表第五篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算...

pingan8787 2019-08-20 18:37 評(píng)論0 收藏0