Osheep

时光不回头,当下最重要。

用两个栈实现队列

题目描述:
用两个栈来实现一个队列,完成队列的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中。

文章同步:levinhax’s Github Blog

点赞