首页 > 试题广场 >

用两个栈实现队列

[编程题]用两个栈实现队列
  • 热度指数:1007674 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
用两个栈来实现一个队列,使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法,即保证pop操作时队列内已有元素。

数据范围:
要求:存储n个元素的空间复杂度为  ,插入与删除的时间复杂度都是 
示例1

输入

["PSH1","PSH2","POP","POP"]

输出

1,2

说明

"PSH1":代表将1插入队列尾部
"PSH2":代表将2插入队列尾部
"POP“:代表删除一个元素,先进先出=>返回1
"POP“:代表删除一个元素,先进先出=>返回2   
示例2

输入

["PSH2","POP","PSH1","POP"]

输出

2,1
推荐
class Solution
{
public:
    void push(int node) {
       stack1.push(node); 
    }
    int pop() {
        int a;
        if(stack2.empty()){
            while(!stack1.empty()){
                a=stack1.top();
                stack2.push(a);
                stack1.pop();
            }
        }
        a=stack2.top();
        stack2.pop();
        return a;
        
    }
private:
    stack<int> stack1;
    stack<int> stack2;
};

用两个栈实现一个队列的功能?要求给出算法和思路!

<分析>:

入队:将元素进栈A

出队:判断栈B是否为空,如果为空,则将栈A中所有元素pop,并push进栈B,栈B出栈;

 如果不为空,栈B直接出栈。

用两个队列实现一个栈的功能?要求给出算法和思路!

<分析>:

入栈:将元素进队列A

出栈:判断队列A中元素的个数是否为1,如果等于1,则出队列,否则将队列A中的元素   以此出队列并放入队列B,直到队列A中的元素留下一个,然后队列A出队列,再把   队列B中的元素出队列以此放入队列A中。


编辑于 2015-08-18 23:15:03 回复(73)
function push(node)
{
    while(stack2.length > 0) {
        let oldNode = stack2.pop()
        stack1.push(oldNode)
    }
    stack1.push(node)
}
function pop()
{
    while(stack1.length > 0) {
        let node = stack1.pop()
        stack2.push(node)
    }
    return stack2.pop()
}
let stack1 = [], stack2 = []
module.exports = {
    push : push,
    pop : pop
};

发表于 2022-06-15 17:02:27 回复(0)

用栈的先进后出 --实现队列的先进先出

var stack1 = []   // 入栈stack1----负责存元素
var stack2 = []   // 出栈stack2----负责取元素
function push(node)
{
    // write code here
    // 入栈时直接stack1存入元素
    stack1.push(node)
}
function pop()
{
    // write code here
//   如果stack2中没有元素,则从stack1中将元素pop出,再push存入stack2中
    if(stack2.length == 0) {
        while(stack1.length) {
            stack2.push(stack1.pop())   
        }
    }
    return stack2.pop()   // 将stack2元素弹出

}
module.exports = {
    push : push,
    pop : pop
};
发表于 2022-05-14 14:24:25 回复(0)
const stackIn = []
const stackOut = []
function push(node) {
    // write code here
    stackIn.push(node)
}
function pop() {
    // write code here
    // 有的话证明上次队列没有完全出队
    if(stackOut.length) return stackOut.pop()

    // 到这里说明已经完全出队了, 需要进入下批次的队伍
    while (stackIn.length) {
        stackOut.push(stackIn.pop())
    }
    return stackOut.pop()
}
module.exports = {
    push: push,
    pop: pop
};
发表于 2022-03-08 21:19:17 回复(0)
let stack = [];
function push(node)
{
    // write code here
    stack.unshift(node);
}
function pop()
{
    // write code here
    return stack.pop();
}
module.exports = {
    push : push,
    pop : pop
};
发表于 2021-10-20 14:12:09 回复(0)
function push(node)
{
    // write code here
    return Array.prototype.push.call(this,node)
}
function pop()
{
    // write code here
    return Array.prototype.shift.call(this)
}
module.exports = {
    push : push,
    pop : pop
};
发表于 2021-09-27 16:37:00 回复(0)
var stack1 = [];
var stack2 = [];
function push(node)
{
    // write code here
    stack1.push(node);
}
function pop()
{
    // write code here
    if(stack2.length == 0){
        while(stack1.length != 0){
            stack2.push(stack1.pop());
        }
    }
    return stack2.pop();
}
module.exports = {
    push : push,
    pop : pop
};

发表于 2021-06-08 14:35:05 回复(0)
let stack1 = [],stack2 = [];
function push(node)
{
    // write code here
    stack1.push(node);
}
function pop()
{
    let tmp;
    while(tmp = stack1.pop()){
        stack2.push(tmp);
    }
    let res = stack2.pop();
    while(tmp = stack2.pop()){
        stack1.push(tmp);
    }
    return res;
}

队列的pop是pop第一个元素,栈的pop是pop最后一个元素,数组的pop与栈一样
发表于 2021-04-19 11:11:16 回复(0)
JS玩家不要上当,JS里面的Array同时是栈和队列,所以不需要****两个栈,直接一个数组搞定。
这题的难点是理解 ”队列pop“,其实所谓 ”队列的pop“在JS中的实现就是Array.prototype.shift
const stack = [];

function push(node)
{
    // write code here
    stack.push(node);
}
function pop()
{
    // write code here
    return stack.shift();
}
module.exports = {
    push : push,
    pop : pop
};


编辑于 2021-04-08 14:12:45 回复(0)
const stack1 = [];
const stack2 = [];
function push(node)
{
    stack1.push(node);
}
function pop()
{
    if (stack2.length) return stack2.pop();
    else if (stack1.length === 0) return null;
    else {
        while (stack1.length) stack2.push(stack1.pop());
        return stack2.pop();
    }
}

发表于 2021-03-29 14:34:54 回复(0)
使用JavaScript语言:
【注意】我们使用数组模拟栈,虽然数组有shift()方法可以直接去除头部元素,但是我们既然把它当做栈,就要遵守栈的规则:只能在一端进行插入和删除。
let inStack = []; // 入队列
let outStack = []; // 出队列
function push(node)
{
    inStack.push(node);
}
function pop()
{
    // 如果outStack为空,就将inStack中的数据转移到outStack中
    // 如果outStack不为空,就直接pop()
    if(!outStack.length) {
        while(inStack.length) {
            outStack.push(inStack.pop());
        }
    }
    return outStack.pop();
}
module.exports = {
    push : push,
    pop : pop
};
PS:不明白的同学,建议在纸上画一下,就懂了~

发表于 2021-03-20 21:56:42 回复(0)
let stack1 = [],stack2 = [];
function push(node)
{
    // write code here
    stack1.push(node);
    
}
function pop()
{
    // write code here
    if(stack2.length <= 0){
        while(stack1.length > 0){
            stack2.push(stack1.pop());
        }
    }
    return stack2.pop();
}
用JavaScript写的

发表于 2021-03-15 16:31:20 回复(0)
栈:先进后出;队列:后进先出
let stack1 = [],stack2 = []
function push(node)
{
    // write code here
   stack1.push(node)//  当时进队列,直接进入 stack1

}
function pop() 

{
    // write code here
    if(stack2.length) return stack2.pop() //当出列时,如果 stack2 不为空,弹出 stack2 栈顶元素

    else{            

        while(stack1.length){ 

            stack2.push(stack1.pop()) // stack1 中的全部数逐个出栈入栈 stack2

        }
    }
   return stack2.pop() //弹出 stack2 栈顶元素 

}

编辑于 2020-12-24 15:19:49 回复(0)
function push(node)
{
    // write code here
    return Array.prototype.unshift.call(this,node)
    
}
function pop()
{
    // write code here
     return Array.prototype.pop.call(this)
}
module.exports = {
    push : push,
    pop : pop
};

发表于 2020-09-04 18:05:28 回复(0)
var a=[]
function push(node)
{
    a.push(node)
}
function pop()
{
    return a.shift()
}
感觉javascript有点赖皮。。
发表于 2020-04-19 17:37:03 回复(0)
/**
 * 我的解题思路:
 * 先入后出的话,直接调用shift方法就好了
 *
 * @param {*} node 
 */
const stack = [];
function push(node)
{
    // write code here
    stack.push(node);
}
function pop()
{
    // write code here
    return stack.shift();
}

/**
 * 不用其他的方法的解题思路:
 * 1.主要是pop方法的实现
 * 2.先生成一个倒序的栈,用于获取需要返回的结果
 * 3.然后再将之前栈填充完整
 *
 * @param {*} node 
 */
let stack1 = [];
let stack2 = [];
function topPush(node)
{
    // write code here
    stack1.push(node);
}
function topPop()
{
    // write code here
    while(stack1.length) {
        stack2.push(stack1.pop());
    }
    const result = stack2.pop();
    while(stack2.length) {
        stack1.push(stack2.pop());
    }
    return result;
}

发表于 2020-02-15 22:14:16 回复(0)
var inStack = [],
    outStack = [];
function push(node)
{
    // write code here
    inStack.push(node);
}
function pop()
{
    // write code here
    if (!outStack.length) {
        while (inStack.length) {
            outStack.push(inStack.pop());
        }
    }
    return outStack.pop();
}

发表于 2019-09-16 15:26:05 回复(0)
var inStack = []
function push(node)
{
    inStack.push(node);
}
function pop()
{
    if (inStack) {
      return inStack.shift();
    }
}
这样难道不可以吗?为什么大家好像没人用这样的
发表于 2019-09-06 19:14:19 回复(0)
哭了,没有在for循环里加var,内存溢出调了好久
发表于 2019-08-21 16:39:31 回复(0)
用js比较清楚理解
通过代码:
var push1=[];
function push(node)
{
    return push1.push(node);
}
function pop()
{
    return push1.shift();
}
发表于 2019-04-29 20:09:39 回复(0)