首页 > 试题广场 >

用两个栈实现队列

[编程题]用两个栈实现队列
  • 热度指数：1009492 时间限制：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)
C++
Spectre_头像 Spectre_ 
class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int tmp = stack2.top();
        stack2.pop();
        return tmp;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

发表于 2022-08-10 20:27:02 回复(0)
C++
空中转体一周半头像 空中转体一周半

栈1用来入队，栈2用来出队。
进队：直接压入栈1
出队：有两种情况：栈2不空：栈2出栈顶元素。栈2为空，把栈1元素依次压入栈2，然后栈2出栈顶元素。

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }
    int pop() {
        if(!stack2.empty()){
            int res =stack2.top();
            stack2.pop();
            return res;
        }
        else {
            while(!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
             int res =stack2.top();
            stack2.pop();
            return res;
        }
    }
private:
    stack stack1;
    stack stack2;
};
发表于 2021-09-21 08:00:52 回复(0)
Python3
牛客338194879号头像 牛客338194879号

             
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        # write code here
        self.stack1.append(node)
    def pop(self):
        # return xx
        while len(self.stack1)!=0:
            item = int(self.stack1[0])
            self.stack2.append(item)
            self.stack1.pop(0)
        r = self.stack2[0]
        self.stack2.pop(0)
        return r
            


发表于 2021-08-31 21:02:13 回复(0)
任骞头像 任骞
class Solution
{
public:
    void push(int node) {
        stack1.push(node);
        
    }

    int pop() {
        if(stack2.empty()){
            while(!stack1.empty()){
            stack2.push(stack1.top());
             stack1.pop();
        }
        }
          int ret = stack2.top();
            stack2.pop();
            return ret;
         
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};
发表于 2016-06-23 22:04:15 回复(0)
侯夏冰头像 侯夏冰 
这是左程云的《程序员代码面试指南》的答案：
import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
    	if(stack1.empty()&&stack2.empty()){
            throw new RuntimeException("Queue is empty!");
        }
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

发表于 2016-06-04 16:11:14 回复(63)
你是我的小熊啊头像 你是我的小熊啊
/**
* 用两个栈来实现队列的push()和pop()操作
* 注意这里的队列的特性：先进先出，并且，其中的push()操作为添加元素到队列末尾，pop()操作为弹出队首元素，并且将其删除
* 其中栈的特性为：先进后出
* 
* 算法思想：这里利用了两个栈，来实现队列的操作，由队列和栈的特性可以知道，可以利用一个栈来作为过渡使用，即：
* 当向队列中插入数据时，实际上将其插入栈stack1中
* 当要从队列中弹出队首元素时，就可以将stack1中的元素依次写入到stack2中（由于在stack1中元素的顺序与队列中的正好相反，所以再次反即为正，反反得正）
* 所以这个时候，从栈stack2中弹出的栈顶元素即为队列中的队首元素
*/
Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
    //注意这里不必每次都将stack2清空，因为再后面的逆转回去时，会将栈中的元素pop()掉,这个操作就相当于清空了stack2，stack1也是一样的
    //注意这里是将stack1中的元素逆转（反反得正）
    while(!stack1.isEmpty()){
    stack2.push(stack1.pop());
    }
    //这里将要返回的队首的值取到了
    int getNumber = stack2.pop();
    //在取到对应的队首元素之后，就需要将剩下的元素在返回到原本的栈stack1中去
    while(!stack2.isEmpty()){
    stack1.push(stack2.pop());
    }
    return getNumber; 
    }

发表于 2017-03-05 16:30:50 回复(0)
小文同学在努力头像 小文同学在努力 
let stack1 = [] // 模拟队列头
let stack2 = [] // 模拟队列尾

function push(node)
{
    // 向队尾插入元素
    stack2.push(node)
}
function pop()
{
    // 从队列头删除元素
    if(stack1.length) {
        return stack1.pop()
    }
    while(stack2.length) {
        stack1.push(stack2.pop())
    }
    return stack1.pop()
}
module.exports = {
    push : push,
    pop : pop
};

发表于 2022-08-18 00:56:59 回复(0)
Java
FARO_Z头像 FARO_Z 
public class NC76_stackToQueue {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);
    }

    public int pop() {
        if (!stack2.isEmpty()) return stack2.pop();
        while (!stack1.isEmpty()) stack2.push(stack1.pop());
        return stack2.pop();
    }
}

发表于 2021-11-11 10:46:53 回复(1)
Python 3
阿司匹林Yo头像 阿司匹林Yo 
class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, node):
        self.stack1.append(node)

    def pop(self):
        if not self.stack2:
            self.stack2 = self.stack1[::-1]
            self.stack1 = []
        return self.stack2.pop()

发表于 2021-07-30 15:40:01 回复(0)
阿mini默头像 阿mini默 
import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.peek());
                stack1.pop();
            }
        }
        int result = stack2.peek();
        stack2.pop();
        
        return result;
    }
}

发表于 2021-06-30 17:35:04 回复(0)
Java
不走阿拉头像 不走阿拉
思路：
push()实现 默认在stack1中添加元素；
 pop()实现，队列的出队，相当于将栈底元素弹出，需要这借助stack2,先把栈底后面的元素弹栈到stack2然后弹出stack1的栈底元素，并赋值给i,最后把stack2中的元素弹栈到stack1,完成一次模拟出队操作；
public void push(int node) {
        if(stack1.isEmpty()&&stack2.isEmpty()){
                stack1.push(node);
            }else if(!stack1.isEmpty()){
                stack1.push(node);
            }else {
                stack2.push(node);
            }
    }
    
    public int pop() {
    int i;
            while (stack1.size() != 1) {
                stack2.push(stack1.pop());
            }
            i = stack1.pop();
            while (!stack2.isEmpty()){
                stack1.push(stack2.pop());
            }
            return i;
    }

编辑于 2021-06-07 21:41:13 回复(0)
Java
Mono_Chrome头像 Mono_Chrome 
import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);
    }

    public int pop() {
        if (!stack2.isEmpty()) {
            return stack2.pop();
        }
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        return stack2.isEmpty() ? -1 : stack2.pop();
    }
}
发表于 2021-05-07 22:56:53 回复(0)
wengJJ头像 wengJJ
Python
使用pop()方法,将python的list当作stack使用 
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack1=[]
        self.stack2=[]
    def push(self, node):
        # write code here
        self.stack1.append(node)
    def pop(self):
        if len(self.stack2) !=0:
            return self.stack2.pop()
        while len(self.stack1) != 0:
            self.stack2.append(self.stack1.pop())
            
        return self.stack2.pop()



发表于 2021-04-17 16:46:14 回复(0)
Python
牛客313692148号头像 牛客313692148号
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack_in = []
        self.stack_out = []
    
    def push(self, node):
        # write code here
        self.stack_in.append(node)
    def pop(self):
        # return xx
        if self.stack_out:
            return self.stack_out.pop()
        while self.stack_in:
            temp = self.stack_in.pop()
            self.stack_out.append(temp)
        return self.stack_out.pop()
发表于 2021-03-29 15:30:27 回复(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)
肥猿头像 肥猿
思路：入队时，在第一个栈入栈，出队，从第二个栈出栈。
如果第二个栈为空，则第一个栈中元素依次出栈压入第二个栈中，最后再第二个栈出栈
public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}
发表于 2021-03-13 11:12:45 回复(0)
牛客208065635号头像 牛客208065635号 
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []
    def push(self, node):
        # write code here
        self.stack.append(node)
    def pop(self):
        # return xx
        return self.stack.pop(0)

发表于 2021-03-12 14:03:34 回复(0)
天天向上_呀头像 天天向上_呀
// 队列  先进先出  后进后出
// 栈    先进后出    后进先出
栈实现队列，push  pop  
// push方法向栈中添加元素,返回结果是当前添加的元素
// pop方法移除并返回栈顶元素，如果是空栈，会抛出异常：EmptyStackException
对队列 的push与对栈一样，向栈中添加元素
对队列 的pop应是移除并返回栈底元素，解决方法可将栈倒序，再对栈进行pop，再将栈倒序，则为队列正常顺序
双栈可实现上列倒序

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        int a = stack1.push(node);
        //return a;
    }
    
    public int pop() {
        while (stack1.size() != 0){
            int b = stack1.pop();
            stack2.push(b);
        } 
        int c = stack2.pop();
        while(stack2.size() != 0){
            int d = stack2.pop();
            stack1.push(d);
        }
        return c ;
        
    }
}

发表于 2021-01-17 19:43:48 回复(0)
提交观点

问题信息

栈
难度：
2385条回答 319045浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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