力扣labuladong一刷day57天队列实现栈以及栈实现队列

2024-01-10 12:31:31

力扣labuladong一刷day57天队列实现栈以及栈实现队列

一、232. 用栈实现队列

题目链接:https://leetcode.cn/problems/implement-queue-using-stacks/description/
思路:题目要求使用两个栈实现队列,栈是先进后出,队列是先进先出,那么只需要添加元素只往s1中加,删除元素从s2中加,如果s2为空就把s1中的所有元素都出栈并压入s2,这样就变成了先进先出了,如果s2不为空,就直接出栈就行了,不为空说明都已经是排好队的先进先出了,等s2消耗空了再从s1出栈往s2压入元素。

class MyQueue {
    Deque<Integer> s1;
    Deque<Integer> s2;
    public MyQueue() {
        s1 = new LinkedList<>();
        s2 = new LinkedList<>();
    }

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

    public int pop() {
        if (!s2.isEmpty()) return s2.pop();
        while (!s1.isEmpty()) {
            s2.push(s1.pop());
        }
        return s2.pop();
    }

    public int peek() {
        if (!s2.isEmpty()) return s2.peek();
        while (!s1.isEmpty()) {
            s2.push(s1.pop());
        }
        return s2.peek();
    }

    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}
/**
 * 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();
 */

二、225. 用队列实现栈

题目链接:https://leetcode.cn/problems/implement-stack-using-queues/description/
思路:用队列实现栈,只用一个队列就可以实现,只需要把每次添加元素之后,把该元素前面所有的元素出队再入队,前面的元素就都排到后面去了,就实现了后进先出。
如下:
添加元素 1, 2, 3, 4,实际上是:
1
2, 1
3, 2, 1
4, 3, 2, 1

class MyStack {
    LinkedList<Integer> queue;
    public MyStack() {
        queue = new LinkedList<>();
    }

    public void push(int x) {
        int num = queue.size();
        queue.add(x);
        while (num > 0) {
            queue.add(queue.poll());
            num--;
        }
    }

    public int pop() {
        return queue.poll();
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}

文章来源:https://blog.csdn.net/qq_43511039/article/details/135497646
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。