首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构(二)

数据结构(二)

作者头像
wsuo
发布2020-07-31 15:13:34
2350
发布2020-07-31 15:13:34
举报
文章被收录于专栏:技术进阶之路技术进阶之路

一、用栈实现队列

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。同时,我们用一个额外的变量来保存栈顶元素。

思路:画图帮助分析。

“用队列实现栈”题解配图.gif
“用队列实现栈”题解配图.gif

方法: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();
 */
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-02-08 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、用栈实现队列
  • 二、用队列实现栈
    • 方法:peek 和 pop 时,依次将队首出队到队尾
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档