首页 > 试题广场 >

用两个栈实现队列

[编程题]用两个栈实现队列
  • 热度指数：1009869 时间限制：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)
Java
牛客961255415号头像 牛客961255415号
public void push(int node) {
stack1.push(node);
}

public int pop() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
发表于 2024-04-25 17:05:11 回复(0)
Java
你好，侦探先生头像 你好，侦探先生 
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() {
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        };
        return stack2.pop();
    }
}
// 当向队列中插入数据时，实际上将其插入栈stack1中
// 当要从队列中弹出队首元素时，就可以将stack1中的元素依次写入到stack2中（由于在stack1中元素的顺序与队列中的正好相反，所以再次反即为正，反反得正）
// 所以这个时候，从栈stack2中弹出的栈顶元素即为队列中的队首元素

编辑于 2024-03-26 10:47:41 回复(0)
Java
不存在的神秘人头像 不存在的神秘人
public void push(int node) {
        stack1.push(node);
    }
   
    public int pop() {
    if(stack2.empty())
    while(!stack1.empty()){
        Integer a=stack1.pop();
        stack2.push(a);
    }
    return stack2.pop();
    }
编辑于 2024-03-11 16:53:07 回复(0)
Java
牛客276339250号头像 牛客276339250号
全部先压栈到stack2，再出栈stack
import java.util.*;
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() {
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
int res=stack2.pop();
while(!stack2.isEmpty()){
stack1.push(stack2.pop());
}
return res;
}
}

发表于 2023-09-20 15:37:30 回复(0)
Java
whywhy8535头像 whywhy8535 
import java.util.*;
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();
        }
        //栈1的数据全部进入栈2
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        //进栈之后在立即出一个栈
        return stack2.pop();
    }

    public static void main(String[] args) {
        Solution stackDemo = new Solution();
        for (int i = 0; i < 10; i++) {
            stackDemo.push(i);
            //栈 先进后出 stack1是 9 8 7 。。。。 1
        }
        System.out.println("1111111");
        if (stackDemo.stack2.isEmpty()) {
            int pop = stackDemo.pop();
            System.out.println(pop);
        }
        while (!stackDemo.stack2.isEmpty()) {
            int pop = stackDemo.pop();
            System.out.println(pop);
        }


    }
}

发表于 2023-09-02 22:30:13 回复(1)
Java
I-头像 I-
import java.util.*;
import java.util.Stack;

public class Solution {
    // 使用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() {
    // 需要判断反方向放置元素的栈是否为空
    if(stack1.isEmpty()){
        // 抛出异常
       throw new  RuntimeException("This stack is empty!");
    }
    while(!stack1.empty()){
        // 把stack1的元素全部倒入stack2中
        stack2.push(stack1.pop()) ;
    }
    int value=stack2.pop();
    // 把值再一次倒回stack1
    while(!stack2.isEmpty()){
        stack1.push(stack2.pop()) ;

    }
    return value;
    }
}

发表于 2023-08-21 10:34:05 回复(0)
Java
做则必成的勇气和信心头像 做则必成的勇气和信心 
public void push(int node) {//从栈1入
        stack1.push(node);
    }
    
    public int pop() {
        if(stack2.size()<=0){//从栈2出
            while(stack1.size()!=0){//当栈1不为0
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

发表于 2023-07-19 10:14:51 回复(0)
Java
抓住努力的尾巴头像 抓住努力的尾巴 
import java.util.*;
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() {
        while(stack1.size() > 1) {
            stack2.push(stack1.pop());
        }
        int val = stack1.pop();
        while(!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }
        return val;
    }
}
发表于 2023-07-15 16:12:29 回复(0)
Java
牛客355865901号头像 牛客355865901号
我用一个行不行
import java.util.*;
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.add(node);
    }
    
    public int pop() {
        int item = stack1.firstElement();
        stack1.removeElementAt(0);
        return item;
    }
}


发表于 2023-07-14 15:45:17 回复(0)
Java
反对画饼的潜伏者很想去广西嗦粉头像 反对画饼的潜伏者很想去广西嗦粉
要求：存储n个元素的空间复杂度为 �(�)O(n) ，插入与删除的时间复杂度都是 �(1)O(1)
但是我看大家的时间复杂度都是O(n), 貌似不可能O(1)...
发表于 2023-06-09 13:26:37 回复(0)
Java
许七头像 许七 
import java.util.Stack;

public class Solution {
    //用于入队
    Stack<Integer> stack1 = new Stack<Integer>();
    //用于出队
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        while(!stack2.isEmpty()){
            stack1.add(stack2.pop());
        }
        stack1.add(node);
    }
    
    public int pop() {
        while(!stack1.isEmpty()){
            stack2.add(stack1.pop());
        }
        return stack2.pop();
    }
}

发表于 2023-05-10 08:58:32 回复(0)
Java
Hadoopdoop头像 Hadoopdoop 
public class Solution {
    // 用于入队列
    Stack<Integer> stack1 = new Stack<Integer>();
    // 专用于出队列
    Stack<Integer> stack2 = new Stack<Integer>();
    public void push(int node) {
        stack1.add(node);
    }
    public int pop() {
        if(!stack2.isEmpty()){
            return stack2.pop();
        } else {
            while (!stack1.isEmpty()){
                stack2.add(stack1.pop());
            }
            return this.pop();
        }
    }
}

发表于 2023-03-09 13:33:48 回复(0)
Java
贾天龙头像 贾天龙 
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() {
        // 只有当stack2为空的时候，才将stack1中的数据放到stack2中
        if(stack2.isEmpty()){
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }

        return stack2.pop();
    }
}

发表于 2023-03-06 14:40:52 回复(0)
Java
Matrixwayne头像 Matrixwayne 
import java.util.Stack;

public class Solution {

    // Stack: FIFO; Queue: FILO
    // [1,2,3,4]
    // stack1: 每次push的时候，直接放入到stack1中
    // stack2: 每次pop的时候，case 1: stack2不为空，那就直接pop stack2
    //                      case 2: stack2为空，则将stack1中全部倒入stack2中之后，再pop
    // queue的实现形式: queue.pop() <--[stack2 --->][<--- stack1]<-- queue.push()

    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()) {
            pushAllNodesFromStack1ToStack2();
        }
        return stack2.pop();
    }

    private void pushAllNodesFromStack1ToStack2() {
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
    }
}

发表于 2023-02-14 22:43:54 回复(0)
Java
清飞扬割草头像 清飞扬割草 
import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        if(stack1.isEmpty() && stack2.isEmpty()) {
          stack1.push(node); 
        } else{
            stack2.push(node);
        }
    }
    
    public int pop() {
       if(!stack1.isEmpty()) { 
         return stack1.pop();
       } else if(stack1.isEmpty() && !stack2.isEmpty()){
         int size = stack2.size();
         for(int i = 0; i < size; i++) {
            stack1.push(stack2.pop());
         }
       }
       return stack1.pop();
    }
}


发表于 2023-02-13 10:54:26 回复(0)
Java
加勒比海涛头像 加勒比海涛 
import java.util.Stack;

public class Solution {
    Stack<Integer> pushStack = new Stack<Integer>();
    Stack<Integer> popStack = new Stack<Integer>();

    // 我们单独写出来的方法
    // 他的作用是倒数据
    // 倒数据有两个条件
    // 1.必须一次性倒完
    // 2.如果pop栈数据没拿完,不能倒数据(只有pop栈空了,才可以倒数据)
    private void PushToPop() {
        // 1.pop栈为空才可以倒数据
        if(popStack.isEmpty()) {
            // 2.必须一次性倒完
            while (!pushStack.isEmpty()) {
                popStack.push(pushStack.pop());//从push栈中弹出数据压入到push栈中
            }
        }
    }

    // 压入栈
    // 可以随时随地倒数据
    // 只要满足那两个条件即可
    public void push(int node) {
        pushStack.push(node);
        // 其实压入元素的时候 , 可以不用倒数据
        // 因为pop中就导数据了,用户是一定会拿出数据的
        PushToPop();
    }

    // 弹出数据
    // 用户最后要的是pop栈数据,所以要弹出pop栈
    // 可以随时随地倒数据,只要满足那两个条件即可
    public int pop() {
        PushToPop();
        return popStack.pop();
    }
}

发表于 2023-01-17 16:49:34 回复(0)
Java
郝金辉头像 郝金辉 
// 为啥官方会给出 Stack 这种已明确被禁用的数据结构

import java.util.*;

public class Solution {
    Deque<Integer> stack1 = new ArrayDeque<Integer>();
    Deque<Integer> stack2 = new ArrayDeque<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();
    }
}

发表于 2022-12-25 21:14:07 回复(0)
Java
dynamo1头像 dynamo1 
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.isEmpty() && stack2.isEmpty()) {
            return -1;
        }
        if (!stack2.isEmpty()) {
            return stack2.pop();
        }
        while(!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        return stack2.pop();
    
    }
}

发表于 2022-12-04 16:18:00 回复(0)
Java
键盘都敲坏了.头像 键盘都敲坏了. 
public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        while (! stack2.isEmpty())  stack1.push(stack2.pop());
        stack1.push(node);
    }

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

发表于 2022-11-10 15:29:29 回复(0)
提交观点

问题信息

栈
难度：
391条回答 319083浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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