题目描述:
用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。
分析:
一个队列包含了两个栈stack1和stack2,这道题要求我们操作这两个“先进后出”的栈实现一个“先进先出”的队列。
假设我们先把一个元素a插入到栈stack1中,这个时候栈stack1里有一个元素a,栈stack2为空。再插入两个元素b和c到栈stack1中,此时stack1中有三个元素,其中c在栈顶,a位于栈底,栈stack2仍为空。
这个时候若我们尝试着从队列中删除一个元素,根据队列先入先出的规则,a元素应该最先被删除。但栈的规则是先入后出,a元素位于栈底,并不能直接被删除。so,stack2就该登场了,如果我们把stack1中的元素逐个弹出并压入到栈stack2中,元素在stack2中的顺序就和原来在stack1中的元素颠倒了个,我们就能先把a元素给删除了。如果需要继续删除,直接弹出stack2的栈顶即可。
分析得到的结果就是:
先将元素进栈,出栈时先判断:
当stack2中不为空时,在stack2中的栈顶元素是最先进入队列的元素,直接出栈。如果stack2为空时,我们把stack1中的元素逐个弹出并压入stack2。由于先进入队列的元素被压到stack1的底端,经过弹出和压入之后就处于stack2的顶端了,又可以直接出栈
代码实现如下:
var stack1 = [];
var stack2 = [];
function push(node){
stack1.push(node);
}
function pop(){
if(stack2.length != 0){
return stack2.pop();
}else{
if(stack1.length == 0){
return;
}
while(stack1.length != 0){
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
用两个栈实现一个队列的功能
<分析>:
入队:将元素进栈stack1
出队:判断栈stack2是否为空,如果为空,则将栈stack1中所有元素pop,并push进栈stack2,栈stack2出栈;
如果不为空,栈stack2直接出栈。
用两个队列实现一个栈的功能
<分析>:
入栈:将元素进队列quenue1
出栈:判断队列quenue1中元素的个数是否为1,如果等于1,则出队列,否则将队列quenue1中的元素依次出队列并放入队列quenue2,直到队列quenue1中的元素留下一个,然后队列quenue1出队列,再把队列quenue2中的元素出队列依次放入队列quenue1中。