用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
題目描述
用兩個(gè)棧來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列困食，完成隊(duì)列的Push和Pop操作县昂。 隊(duì)列中的元素為int類(lèi)型。
代碼如下：
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);
// write code here
}
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();
// write code here
}
module.exports = {
push : push,
pop : pop
};
解題思路
棧是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)陷舅，而隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)倒彰，那么本題中，
1莱睁、實(shí)現(xiàn)入隊(duì)：將元素直接壓入棧1待讳。
2、實(shí)現(xiàn)出隊(duì)：先判斷兩個(gè)棧是否都為空仰剿，如果不是创淡，在判斷棧2，如果為空南吮，棧1不為空琳彩，先將棧1的元素全部出棧，按順序壓入棧2部凑，然后再?gòu)臈?中出棧露乏，就取得了原來(lái)在棧1棧底的元素了。
