leetcode刷题（99）——225. 用队列实现栈

老马的编程之旅

发布于 2022-06-22 14:05:24

1530

发布于 2022-06-22 14:05:24

使用队列实现栈的下列操作：

push(x) – 元素 x 入栈 pop() – 移除栈顶元素 top() – 获取栈顶元素 empty() – 返回栈是否为空注意:

你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。你所使用的语言也许不支持队列。你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

思路：用队列实现栈只需要一个队列作为底层数据结构一个栈需要的api如下：

class MyStack {

    /** 添加元素到栈顶 */
    public void push(int x);

    /** 删除栈顶的元素并返回 */
    public int pop();

    /** 返回栈顶元素 */
    public int top();

    /** 判断栈是否为空 */
    public boolean empty();
}

先说pushAPI，直接将元素加入队列，同时记录队尾元素，因为队尾元素相当于栈顶元素，如果要top查看栈顶元素的话可以直接返回：

class MyStack {
    Queue<Integer> q = new LinkedList<>();
    int top_elem = 0;

    /** 添加元素到栈顶 */
    public void push(int x) {
        // x 是队列的队尾，是栈的栈顶
        q.offer(x);
        top_elem = x;
    }

    /** 返回栈顶元素 */
    public int top() {
        return top_elem;
    }
}

底层数据结构是先进先出的队列，每次pop只能从队头取元素；但是栈是后进先出，也就是说popAPI 要从队尾取元素。

把队列前面的都取出来再加入队尾，让之前的队尾元素排到队头，这样就可以取出了：

/** 删除栈顶的元素并返回 */
public int pop() {
    int size = q.size();
    while (size > 1) {
        q.offer(q.poll());
        size--;
    }
    // 之前的队尾元素已经到了队头
    return q.poll();
}

这样实现还有一点小问题就是，原来的队尾元素被提到队头并删除了，但是top_elem变量没有更新，我们还需要一点小修改：

/** 删除栈顶的元素并返回 */
public int pop() {
    int size = q.size();
    // 留下队尾 2 个元素
    while (size > 2) {
        q.offer(q.poll());
        size--;
    }
    // 记录新的队尾元素
    top_elem = q.peek();
    q.offer(q.poll());
    // 删除之前的队尾元素
    return q.poll();
}

完整代码：

class MyStack {
    Queue<Integer> queue = new LinkedList<Integer>();
    int topElement = 0;
    /** Initialize your data structure here. */
    public MyStack() {
        
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue.offer(x);
        topElement = x;
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        int size = queue.size();
        while(size>2){
            queue.offer(queue.poll());
            size--;
        }
        topElement = queue.peek();
        queue.offer(queue.poll());
        return queue.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return topElement;
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.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)。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021-01-20，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法