用兩個(gè)棧實(shí)現(xiàn)隊(duì)列

題目描述

用兩個(gè)棧來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列，完成隊(duì)列的Push和Pop操作。 隊(duì)列中的元素為int類型。

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

function Stack(){
    var item = [];
    this.push = function (node){
        item.push(node);
    };
    this.pop = function (){
        return item.pop();
    }
    this.isEmpty = function (){
        return item.length===0;
    }
}
 
var stack1 = new Stack();
var stack2 = new Stack();
 
function push(node)
{
    stack1.push(node);
}
function pop()
{
        if(stack1.isEmpty() && stack2.isEmpty()){
        throw new Error("Queue is empty");
    }
    if(stack2.isEmpty()){
       while(!stack1.isEmpty()){
           stack2.push(stack1.pop());
       }
    }

    return stack2.pop();
     
}

思路

入隊(duì)：將元素進(jìn)棧1;
　　出隊(duì)：判斷棧2是否為空，如果為空，則將棧1中所有元素pop，并push進(jìn)棧2，棧2出棧； 如果不為空，棧２直接出棧。

相關(guān)知識(shí)

棧（stack）又名堆棧，它是一種運(yùn)算受限的線性表。其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算。這一端被稱為棧頂，相對(duì)地，把另一端稱為棧底。向一個(gè)棧插入新元素又稱作進(jìn)棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個(gè)棧刪除元素又稱作出?；蛲藯＃前褩ｍ斣貏h除掉，使其相鄰的元素成為新的棧頂元素。
　　隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。