专栏首页技术进阶之路数据结构(二)

数据结构(二)

一、用栈实现队列

class MyQueue {

    private Stack<Integer> s1 = null;
    private Stack<Integer> s2 = null;
    
    /** Initialize your data structure here. */
    public MyQueue() {
        this.s1 = new Stack<>();
        this.s2 = new Stack<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        s1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        shift();
        if(!s2.isEmpty()) {
            return s2.pop();
        }
        throw new RuntimeException("队列中没有元素");
    }
    
    /** Get the front element. */
    public int peek() {
        shift();
        if(!s2.isEmpty()) {
            return s2.peek();
        }
        throw new RuntimeException("队列中没有元素");
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
    
    //将s1中的全部谈进s2,但是要保证s2为空
    public void shift() {
        if (s2.isEmpty()) {
            while(!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

二、用队列实现栈

栈是一种 后进先出(last in - first out, LIFO)的数据结构,栈内元素从顶端压入(push),从顶端弹出(pop)。一般我们用数组或者链表来实现栈,但是这里会介绍如何用队列来实现栈。队列是一种与栈相反的 先进先出(first in - first out, FIFO)的数据结构,队列中元素只能从 后端(rear)入队(push,然后从 前端(front)端出队(pop)。为了满足栈的特性,我们需要维护两个队列 q1 和 q2。同时,我们用一个额外的变量来保存栈顶元素。

思路:画图帮助分析。

方法:peek 和 pop 时,依次将队首出队到队尾

  • 1、push 的时候,直接在队列的尾部添加元素即可;
  • 2、只要涉及到 peek 或者 pop 操作,要满足栈“后进先出”的性质。需要当前是队尾的元素成为队首,而队列只支持队首出队,队尾入队。很容易想到需要依次把队尾之前的元素出队,放到哪里呢?直接放在队尾即可。因此,定义一个操作 shift ,将队首元素出队,出队以后放在队尾(真的是有毛病,爱的魔力转圈圈)。这个操作需要执行当前队列长度 - 1 次。
  • 3、peek 的时候,得到队尾元素以后,还得再队首元素移动到队尾一次。分析到这里,发现,其实如果我连着几次 peek 操作,得转好几圈。其实可以使用一个变量,记录上一次的操作是什么,这样会更合理一些。但是实际测试下来,因为每次多了一些判断,会消耗一些时间。
class MyStack {

    private Queue<Integer> q;
    
    /** Initialize your data structure here. */
    public MyStack() {
        q = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        q.offer(x);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        if (!q.isEmpty()) {
            shift();
            return q.poll();
        }
        throw new RuntimeException("队列中没有元素");
    }
    
    /** Get the top element. */
    public int top() {
        if (!q.isEmpty()) {
            shift();
            int elem = q.poll();
            q.offer(elem);
            return elem;
        }
        throw new RuntimeException("队列中没有元素");
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return q.isEmpty();
    }
    
    public void shift() {
        for (int i = 0; i < q.size() - 1; i++) {
            q.offer(q.poll());
        }
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 从零开始重新认识 SpringMVC

    默认情况下,你在方法的参数列表中写什么,前端表单中 input 标签的 name 属性值就要是什么,比如:

    wsuo
  • Spring 注解开发之 @Conditional

    在 SpringBoot 中经常看到该注解及其衍生注解,它的作用是根据条件注入组件。

    wsuo
  • 设计模式之 —— 状态模式 State

    在软件开发过程中,应用程序中的部分对象可能会根据不同的情况做出不同的行为,我们把这种对象称为 有状态的对象 ,而把影响对象行为的一个或多个动态变化的属性称为状态...

    wsuo
  • spark2的SparkSession思考与总结2:SparkSession有哪些函数及作用是什么

    问题导读 1.spark SparkSession包含哪些函数? 2.创建DataFrame有哪些函数? 3.创建DataSet有哪些函数? 上一篇spa...

    用户1410343
  • Spring Boot 整合 JPA

    目标:Spring Boot 整合 JPA 工具:IDEA--2020.1 学习目标:框架工具集成 本次学习的工程下载链接放到文本最后面

    背雷管的小青年
  • SpringBoot集成MyBatis

    各位应该都了解SSH和SSM工程搭建时候需要各种配置代码,还要Tomcat配置,非常麻烦

    用户3112896
  • 挑战程序竞赛系列(88):3.6平面扫描(2)

    挑战程序竞赛系列(88):3.6平面扫描(2) 传送门:POJ 3168: Barn Expansion 题意: 求不重叠的矩形个数。 当然,题意是说求能够被...

    用户1147447
  • 面试问到IOC我该如何回答呢?

    相信在面试中,只要问到Spring,基本都会抛出一个问题,说说你对Spring IOC理解吧?虽然在日常的开发经常会使用到,但是要回答起来,并不简单。大脑经过简...

    不一样的科技宅
  • nginx+uWsgi配置问题的解决

    uWSGI 是在像 nginx 、 lighttpd 以及 cherokee 服务器上的一个部署的选择。更多选择见 FastCGI 和 独立 WSGI 容器 。...

    习惯说一说
  • Greenrobot-EventBus源码学习(四)

    EventBus 深入学习四之实例&类说明 本篇开始,则转向greenrobot/EventBus, 之前基本上将Guava中设计的思路捋了一遍,逻辑比较简...

    一灰灰blog

扫码关注云+社区

领取腾讯云代金券