当前位置: 首页 > article >正文

数据结构:栈(Stack)和队列(Queue)—面试题(二)

1. 用队列实现栈。

习题链接icon-default.png?t=O83Ahttps://leetcode.cn/problems/implement-stack-using-queues/description/描述:

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(pushtoppop 和 empty)。

实现 MyStack 类:

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。

根据题意,他要我们用两个队列来实现一个栈,我们知道栈和队列的出数据的方式是不同的,栈是后进先出,队列是先进后出,那么我们该如何用两个队列实现后进先出呢?

 

我们知道当这两个队列都为空是,所代表我们要创建的栈也为空。

我们要进行入栈时,如果我们的栈为空。就将数据放到队列1中,如果栈不为空,代表两个队列都都不为空或者有一个队列不为空,此时是队列1不为空,将数据放入队列1中,如果是队列2不为空,将数据放入队列2中

我们要进行出栈时,如果栈为空不能出数据,如果栈不为空,我们知道队列是先进先出,而栈是先进后出,此时要出的数据应该是我们队列的最后一个数据才是,因此我们可以将我们队列不为空的数据除最后一个数据外全部弹出放入到此时为空的队列当中,并让剩最后一个数的队列将最后一个数弹出,此时弹出的数就是我们栈要出的数据。

我们要获得栈顶元素时,我们可以像出栈方式一样,最后我们让最后一位数据进行队列的查找即可,这样就没有删除最后一个元素,但是这种方式是有问题的,我们发现如果我们将除最后一个元素都放到另一个队列当中了,而最后一个元素依然在另一个队列,但是,栈的查找是不改变数据的形式的,如果我们还用这种方式就改变了他的形式,因此我们可以创建一个变量,将一个队列的所有元素都经过这个变量,然后在将这个变量的值放到另一个队列中,这时我们变量的最后一个值就是我们要查找的栈顶元素

完整代码 

class MyStack {

    Queue<Integer> que1;
    Queue<Integer> que2;

    public MyStack() {
        que1 = new LinkedList<>();
        que2 = new LinkedList<>();
    }
    
    public void push(int x) {
        if(empty()){
            que1.offer(x);
            return;
        }

        if(!que1.isEmpty()){
            que1.offer(x);
        }else{
            que2.offer(x);
        }
    }
    
    public int pop() {
        if(empty()){
            return -1;
        }
        if(!que1.isEmpty()){
            int count = que1.size();
            while(count-1 != 0){
                que2.offer(que1.poll());
                count--;
            }
            return que1.poll();
        }else{
            int count = que2.size();
            while(count-1 != 0){
                que1.offer(que2.poll());
                count--;
            }
             return que2.poll();
        }
        
    }
    
    public int top() {
        if(empty()){
            return -1;
        }
        if(!que1.isEmpty()){
            int count = que1.size();
            int tmp = -1;
            while(count != 0){
                tmp = que1.poll();
                que2.offer(tmp);
                count--;
            }
            return tmp;
        }else{
            int count = que2.size();
            int tmp = -1;
            while(count != 0){
                tmp = que2.poll();
                que1.offer(tmp);
                count--;
            }
            return tmp;
        }
        
    }
    
    public boolean empty() {
        return que1.isEmpty() && que2.isEmpty();
    }
}

2. 用栈实现队列。

描述:

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(pushpoppeekempty):

实现 MyQueue 类:

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空,返回 true ;否则,返回 false

根据题意,他要我们用两个栈实现一个队列,这会我们要用两个栈实现一个先进先出的队列

我们知道当这两个栈都为空是,所代表我们要创建的队列也为空。

我们要进行入队列时,我们让栈1专门作为入数据的栈.

我们要进行出队列时,如果队列为空,就不能删除,如何不为空,同时栈2为空我们就将栈1的所有数据都放到栈2中,由于栈是后进先出,这就让栈的数据都颠倒了过来,这时我们再让栈2出栈,此时出栈的次序就是我们队列的出数据顺序

我们要进行查找队头元素时,我们还是出队的方法,最后让栈进行栈顶元素的查找即可,因为我们上述的出队方式并没有改变数据的形式没有 

完整代码 

class MyQueue {

    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void push(int x) {
        stack1.push(x);
    }
    
    public int pop() {
        if(empty()){
            return -1;
        }

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

        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }
    
    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

好了今天的分享就到这里了,还请大家多多关注,我们下一篇见!


http://www.kler.cn/a/503060.html

相关文章:

  • 如何选择Ubuntu版本
  • 初识JVM HotSopt 的发展历程
  • 批量为视频生成字幕
  • 二级C语言 2025/1/14
  • 开发人员学习书籍推荐(C#、Python方向)
  • Rank-Analysis——LOL 排位战绩查询分析器
  • ssh2-sftp-client和ssh2配合使用js脚本快速部署项目到服务器
  • 力扣264. 丑数 II
  • 后端接口获取的对象包含图片,渲染后端图片,拼接地址渲染,循环列表,vue+uniapp
  • Visual Studio Code (VSCode)为当前项目设置保存时自动格式化
  • 禅道 ip 地址变换后的修改
  • 有限元分析学习——Anasys Workbanch第一阶段笔记(11)横梁中点挠度仿真结果与计算结果对比
  • 罗德与施瓦茨ZN-Z135,26.5G经济型网络分析仪校准套件
  • CSS语言的语法
  • iOS - runtime总结
  • Github 2025-01-13 开源项目周报 Top15
  • 【图像去噪】论文精读:High-Quality Self-Supervised Deep Image Denoising(HQ-SSL)
  • MyBatis 性能优化
  • c++自定义String
  • 【Pytorch实用教程】PyTorch 中如何输出模型参数:全面指南
  • 战略与规划方法——深入解析波士顿矩阵(BCG Matrix):分析产品组合的关键工具
  • Python----Python高级(函数基础,形参和实参,参数传递,全局变量和局部变量,匿名函数,递归函数,eval()函数,LEGB规则)
  • python中bug修复案例-----数据类型不匹配错误导致的bug修复
  • 如何在应用或系统中正确解析和渲染淘宝商品详情API接口返回的HTML内容?
  • Chromium 132 编译指南 Windows 篇 - 生成构建文件 (六)
  • Portainer.io安装并配置Docker远程访问及CA证书