高频刷题-232. Implement Queue using Stacks

高频刷题-232. Implement Queue using Stacks

https://leetcode.com/problems/implement-queue-using-stacks/

 

用两个stack(LIFO)去实现队列(FIFO), 这两种结构是完全相反的,所以需要一个辅助的stack将入栈的数据给倒置以下,最先想到的办法是实现push,首先导致当前栈stack的元素到back栈中,然后push当前的元素,再从back中导入回来:

高频刷题-232. Implement Queue using Stacks

这样使得pop(), peek都非常简单。

实现代码如下:

class MyQueue {

    private Stack<Integer> stack;
    private Stack<Integer> stackBack;

    /**
     * Initialize your data structure here.
     */
    public MyQueue() {
        stack = new Stack<>();
        stackBack = new Stack<>();
    }

    /**
     * Push element x to the back of queue.
     */
    public void push(int x) {
        while (!stack.isEmpty()) stackBack.push(stack.pop());
        stack.push(x);
        while (!stackBack.isEmpty()) stack.push(stackBack.pop());
    }

    /**
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {
        return stack.pop();
    }

    /**
     * Get the front element.
     */
    public int peek() {
        return stack.peek();
    }

    /**
     * Returns whether the queue is empty.
     */
    public boolean empty() {
        return stack.isEmpty();
    }
}

但是push()操作每次的时间复杂度都是O(n),再看题目的要求:

Follow-up: Can you implement the queue such that each operation is amortized O(1) time complexity?

需要实现摊还时间复杂度O(1)。 啥是摊还时间复杂度?

摊还分析给出了所有操作的平均性能。摊还分析的核心在于,最坏情况下的操作一旦发生了一次,那么在未来很长一段时间都不会再次发生,这样就会均摊每次操作的代价。

这样我们可以这样实现,push的时候,都push到stack中,而pop的时候,去判断stackBack中的元素是否为空,如果为空,需要翻转一次(从stack pop所有元素到stackBack中),如果stackBack不为空,说明可以从栈中直接pop元素(因为已经是之前翻转过的)。Peek的时候也做类似操作。这样N次操作均摊下来的时间复杂度为O(1)。

代码实现如下:

class MyQueue {

    private Stack<Integer> stack;
    private Stack<Integer> stackBack;

    /**
     * Initialize your data structure here.
     */
    public MyQueue() {
        stack = new Stack<>();
        stackBack = new Stack<>();
    }

    /**
     * Push element x to the back of queue.
     */
    public void push(int x) {
        stack.push(x);
    }

    /**
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {
        if (stackBack.isEmpty()) {
            while (!stack.isEmpty()) stackBack.push(stack.pop());
        }
        return stackBack.pop();
    }

    /**
     * Get the front element.
     */
    public int peek() {
        if (stackBack.isEmpty()) {
            while (!stack.isEmpty()) stackBack.push(stack.pop());
        }
        return stackBack.peek();
    }

    /**
     * Returns whether the queue is empty.
     */
    public boolean empty() {
        return stack.isEmpty() && stackBack.isEmpty();
    }
}

 

上一篇:Gatewey


下一篇:AiApe问答机器人项目Alpha阶段后端Bug汇总