【代码随想录算法训练营-第十天】【栈与队列】232.用栈实现队列,225. 用队列实现栈

发布时间:2024年01月23日

写在最前面,目前Java已经推荐使用Deque来实现栈和队列了,原因:
https://www.cnblogs.com/jiading/articles/12452830.html

232.用栈实现队列

第一遍

  • 思路
    • pop:出栈;
    • push:入栈;
    • peek:获取栈顶元素;
    • empty:判断栈是否为空;
      https://blog.csdn.net/weixin_45428910/article/details/129701275
class MyQueue {
    Stack<Integer> stackIn;
    Stack<Integer> stackOut;

    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }

    public void push(int x) {
        stackIn.push(x);
    }

    public int pop() {
        judge();
        return stackOut.pop();
    }

    public int peek() {
        // 返回队头元素
        judge();
        return stackOut.peek();
    }

    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }

    public void judge() {
        if (!stackOut.isEmpty()) return;
        while (!stackIn.isEmpty()) {
            Integer x = stackIn.pop();
            stackOut.push(x);
        }
    }
}

225. 用队列实现栈

第一遍

  • 思路
    • 我实现的这个方法过于复杂了,其实不用写两个trans的函数;
    • 参考答案,可以将In中的转换到Out中,然后命名交换即可;
    • 同时,Deque提供了获取头尾元素和插入头尾位置的方法,可以使用Deque实现一个队列就完成这个操作;
      https://blog.csdn.net/swadian2008/article/details/126783574
class MyStack {
    Deque<Integer> queueIn;
    Deque<Integer> queueOut;

    public MyStack() {
        queueIn = new ArrayDeque<>();
        queueOut = new ArrayDeque<>();
    }

    public void push(int x) {
        queueIn.addLast(x);
    }

    public int pop() {
        transToOut();
        Integer x = queueIn.pollFirst();
        transToIn();
        return x;
    }

    public int top() {
        transToOut();
        Integer x = queueIn.pollFirst();
        queueOut.addLast(x);
        transToIn();
        return x;
    }

    public boolean empty() {
        return queueIn.isEmpty() && queueOut.isEmpty();
    }

    private void transToOut() {
        while (queueIn.size() > 1) {
            Integer x = queueIn.pollFirst();
            queueOut.addLast(x);
        }
    }

    private void transToIn() {
        while (queueOut.size() > 0) {
            Integer x = queueOut.pollFirst();
            queueIn.addLast(x);
        }
    }
}
文章来源:https://blog.csdn.net/qq_40691970/article/details/135686360
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。