代码随想录算法训练营第9天 | 232.用栈实现队列 , 225. 用队列实现栈

发布时间:2024年01月22日

栈与队列的内部实现机制:https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

344.反转字符串

题目链接:https://leetcode.cn/problems/reverse-string/description/

思路:


这是一道模拟题,不涉及到具体算法,考察的就是对栈和队列的掌握程度。 使用栈来模式队列的行为,如果仅仅用一个栈,是一定不行的,所以需要两个栈一个输入栈,一个输出栈,这里要注意输入栈和输出栈的关系。 在push数据的时候,只要数据放进输入栈就好,但在pop的时候,操作就复杂一些,输出栈如果为空,就把进栈数据全部导入进来(注意是全部导入),再从出栈弹出数据,如果输出栈不为空,则直接从出栈弹出数据就可以了。
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() {
        dumpStackIn();
        return stackOut.pop();
    }
    
    public int peek() {
        dumpStackIn();
        return stackOut.peek();
    }
    
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }

    // 如果stackOut为空,那么将stackIn中的元素全部放入stackOut中
    private void dumpStackIn(){
        if(!stackOut.isEmpty())    return;
        while(!stackIn.isEmpty()){
            int tmp = stackIn.pop();
            stackOut.push(tmp);
        }
    }
}

/**
 * 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();
 */

时间复杂度:push和empty为O(1), pop和peek为O(n)
空间复杂度:O(n)

225. 用队列实现栈

题目连接:https://leetcode.cn/problems/implement-stack-using-queues/description/

解法1:双队列

用两个队列que1和que2实现队列的功能,que2其实完全就是一个备份的作用,把que1最后面的元素以外的元素都备份到que2,然后弹出最后面的元素,再把其他元素从que2导回que1。

class MyStack {
    // q1 存放元素
    Queue<Integer>q1;
    // q2 临时中转队列
    Queue<Integer>q2;

    public MyStack() {
        q1 = new ArrayDeque<>();
        q2 = new ArrayDeque<>();
    }
    
    // poll() 用于移除并返回队列头部的元素
    public void push(int x) {
       while(q1.size() > 0){
           q2.add(q1.poll());
       }
       q1.add(x);
       while(q2.size() > 0){
           q1.add(q2.poll());
       }
    }
    
    public int pop() {
        return q1.poll();
    }
    
    public int top() {
        return q1.peek();
    }
    
    public boolean empty() {
        return q1.isEmpty();
    }
}

/**
 * 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();
 */

时间复杂度: pop为O(n),其他为O(1)
空间复杂度: O(n)

解法2:单队列

一个队列在模拟栈弹出元素的时候只要将队列头部的元素(除了最后一个元素外) 重新添加到队列尾部,此时再去弹出元素就是栈的顺序了。

class MyStack {

    Queue<Integer> queue;

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

    //每 offer 一个数(A)进来,都重新排列,把这个数(A)放到队列的队首
    public void push(int x) {
        queue.offer(x);
        int size = queue.size();
        //移动除了 A 的其它数
        while (size-- > 1)
            queue.offer(queue.poll());
    }

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

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

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

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