代码随想录算法训练营Day7 | 233.用栈实现队列、225.用队列实现栈

发布时间:2023年12月22日

LeeCode 233 用栈实现队列

在这里插入图片描述

本题思路:使用两个栈来实现队列,应该怎么做呢?我们通过画图来分析下

  • 入队列的时候,直接在 stackin 入在这里插入图片描述
  • 出队列的时候,肯定是先出 1 ,此时把,stackin 中全部 弹出到 入到 stackout 中,如果要出队列,直接弹出 stackout 顶部元素就行。(此处,因为 stackout 为空,所以需要将 stackin 所有元素弹入到 stackout 中在这里插入图片描述
  • 此时如果继续入队列 3 就继续往 stackin 中添加在这里插入图片描述
  • 此时再要出队列的时候,就是出的2,此时 stackout 中不为空,直接返回 stackout.pop 即可在这里插入图片描述
  • 此时再进入队列 4 ,直接进入 stackin在这里插入图片描述
  • 后续的逻辑就和前面一样
public 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() {
        // 首先判断 stackout 是否为空
        if (stackout.isEmpty()) {
            // 把 stackin 元素全部放入 stackout中
            while (!stackin.isEmpty()) {
                stackout.push(stackin.pop());
            }
        } 
        return stackout.pop();
    }

    // 查看队首元素
    public int peek() {
        // 首先判断 stackout 是否为空
        if (stackout.isEmpty()) {
            // 把 stackin 元素全部放入 stackout中
            while (!stackin.isEmpty()) {
                stackout.push(stackin.pop());
            }
        } 
        return stackout.peek();
    }

    // 判空操作
    public boolean empty() {
        return (stackin.isEmpty() && stackout.isEmpty()) == true ? true : false;
    }
}

LeetCode 225 用队列实现栈

在这里插入图片描述
本题思路:使用 一个队列来模拟实现栈更简单。下面画个图来分析一下

  • 进栈操作在这里插入图片描述
  • 出栈操作,此时应该出的是 3 ,我们可以将 3 之前的元素 从队头弹出,然后重新加入到队列中,此时队头元素就是 3,直接弹出返回这个元素即可在这里插入图片描述
public class MyStack {

    Queue<Integer> queue;
    int size = 0;

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

    // 添加操作,直接入栈即可(入队列)
    public void push(int x) {
        queue.add(x);
        size++;
    }

    // 出栈操作
    public int pop() {
        // 先弹出 size-1 个元素,重新加到队列末尾。
        for (int i = 0; i < size - 1; i++) {
            queue.add(queue.poll());
        }
        size--;
        return queue.poll();
    }

    // 查看栈顶元素
    public int top() {
        // 先弹出 size-1 个元素,重新加入到队列末尾。
        for (int i = 0; i < size - 1; i++) {
            queue.add(queue.poll());
        }
        // 保存下来栈顶元素
        int res = queue.poll();
        queue.add(res);
        return res;
    }

    public boolean empty() {
        return size == 0 ? true : false;
    }
}
文章来源:https://blog.csdn.net/hero_jy/article/details/135140736
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。