首页 > 试题广场 >

用两个栈实现队列

[编程题]用两个栈实现队列
  • 热度指数：1036809 时间限制：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)
Javascript
petrichor11头像 petrichor11 
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)
Javascript
载梦覆星河头像 载梦覆星河

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

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)
Javascript
AAATest头像 AAATest 
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)
Javascript
牛客257156640号头像 牛客257156640号
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)
Javascript
gai溜子头像 gai溜子
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)
JavaScript
王志晗头像 王志晗 
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)
JavaScript
可以教我摸鱼嘛头像 可以教我摸鱼嘛 
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)
JavaScript
白下布衣头像 白下布衣
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)
JavaScript
splwany头像 splwany 
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
webchang头像 webchang
使用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)
JavaScript
IPzzzi头像 IPzzzi 
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)
JavaScript
别卷啦！头像 别卷啦！
栈：先进后出；队列：后进先出 
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)
JavaScript
菲鸽爱编程头像 菲鸽爱编程 
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)
JavaScript
奕※時＾毀￠头像 奕※時＾毀￠
var a=[]
function push(node)
{
    a.push(node)
}
function pop()
{
    return a.shift()
}
感觉javascript有点赖皮。。
发表于 2020-04-19 17:37:03 回复(0)
JavaScript
Helianthuswhite头像 Helianthuswhite 
/**
 * 我的解题思路：
 * 先入后出的话，直接调用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)
JavaScript
Bytedancer2021头像 Bytedancer2021 
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)
JavaScript
内推看我主页头像 内推看我主页 
var inStack = []
function push(node)
{
    inStack.push(node);
}
function pop()
{
    if (inStack) {
      return inStack.shift();
    }
}
这样难道不可以吗？为什么大家好像没人用这样的
发表于 2019-09-06 19:14:19 回复(0)
JavaScript
三年二班喵小萌头像 三年二班喵小萌
哭了，没有在for循环里加var，内存溢出调了好久
发表于 2019-08-21 16:39:31 回复(0)
JavaScript
仙人掌的刺猬头像 仙人掌的刺猬
用js比较清楚理解
通过代码：
var push1=[];
function push(node)
{
    return push1.push(node);
}
function pop()
{
    return push1.shift();
}
发表于 2019-04-29 20:09:39 回复(0)
提交观点

问题信息

栈
难度：
39条回答 327598浏览

热门推荐

通过挑战的用户

查看代码

相关试题

用两个栈实现队列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号