队列实现栈以及栈实现队列 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：队列实现栈以及栈实现队列

评论礼仪 见这里，违者直接拉黑。

[cabbagehao]

用栈实现队列的方法，最开始没有看懂，一直用的复杂度比较高的那种来回倒腾的方式，题主这里的解法是一步到位了。
这篇文章里总结了几种不同的方法优缺点https://www.cnblogs.com/wanghui9072229/archive/2011/11/22/2259391.html

[deepbreath373]

打卡

打卡

[zhangshuiyong]

"225. 用队列实现栈（简单）"，题目好像规定用双队列的方式实现栈。如果不按作者的单队列实现栈，需要想得多一些。就是设计一个队列(push_pop_queue)只能存储最多一个元素，一个存储多个元素的队列(store_queue)。

1. 遇到push，如果push_pop_queue为空可以直接push_back。如果push_pop_queue不为空，需要把已有元素pop_front到store_queue
2. 遇到pop，如果push_pop_queue不为空(只有1个元素)，直接pop_front。然后如果store_queue不为空，O(n)拿到队尾元素，放回到push_pop_queue
3. 遇到top，push_pop_queue不为空(只有一个元素)，先pop_front，拿到top元素，在push_back,最后返回top元素

[zxcvbnmleizhe]

光用api好像复杂度除了pop为o(n),其余的也是o(1)

class MyStack {
        LinkedList<Integer> list;

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

        public void push(int x) {
            list.add(x);

        }

        public int pop() {
            return list.removeLast();
        }

        public int top() {
            return list.getLast();
        }

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

[labuladong]

@zhangshuiyong 这样实现功能没问题，但题目说要用队列的 API 实现栈，所以用 LinkedList 的 API 不合要求

[ichengzi]

栈是反向， 队列是正向。 负负得正， 两个栈可以模拟队列。 正正无法得负， 两个对立无法模拟栈， 队列一直会保持正向读取的顺序。

[yfeng21]

我觉得用队列实现栈这题东哥理解错题意了。Implement a last-in-first-out (LIFO) stack using only two queues, 说的是只能用两个队列，不能有其他变量，所以不能存 int top_elem = 0; 这个值 我的python实现

class MyStack:

    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()

    def push(self, x: int) -> None:
        # Clears q2 before pushing new value
        if len(self.q2) > 0:
            self.q1.append(self.q2.popleft())
        self.q1.append(x)

    def pop(self) -> int:
        ans = self.top()
        self.q2.popleft()
        return ans

    def top(self) -> int:
        # Makes sure q2 only contains 1 element: top of stack 
        if len(self.q2) != 1:
            while len(self.q1) > 1:
                self.q2.append(self.q1.popleft())
            self.q1, self.q2 = self.q2, self.q1
        ans = self.q2[0]
        return ans

    def empty(self) -> bool:
        return len(self.q1) + len(self.q2) == 0

[deepbreath373]

力扣第 25 题「 用队列实现栈」让我们实现如下 API： 这句对应的链接题目跑到 k 个一组反转链表去了。

[carterwu]

每次push的时候，按顺序将队头的元素重新加入队尾就可以。这样不必要维护一个top_elem MyStack.prototype.push = function(x) { this.queue.push(x) let count = this.queue.length while (count > 1) { this.queue.push(this.queue.shift()) count-- } };

[labuladong]

@deepbreath373 感谢指出，已修复

[restart365]

个人感觉这种写法更好理解，下面用queue to stack做例子，用q2存储最终结果。push的时候先在q1添加新element，再把q2里所有的元素加进q1。这时q1里已经是一个倒叙的queue了。把q1再dump回q2，保持q1为空

class MyStack {
    ArrayDeque<Integer> q1, q2;

    public MyStack() {
        q1 = new ArrayDeque<>();
        q2 = new ArrayDeque<>();
    }
    
    public void push(int x) {
        q1.push(x);
        while(!q2.isEmpty()) {
            q1.push(q2.pop());
        }
        
        while(!q1.isEmpty()) {
            q2.push(q1.pop());
        }
    }
    
    public int pop() {
        return q2.pop();
    }
    
    public int top() {
        return q2.peek();
    }
    
    public boolean empty() {
        return q2.isEmpty();
    }
}

这样做的好处是把一个push method的逻辑盘明白了，剩下pop, peek, empty都能无脑一行解决。 stack to queue的做法就是把push的顺序换一下，先把s2放进s1，再添加新element，然后再把s1放回s2。

public void push(int x) {
    while (!s2.empty()) {
        s1.push(s2.pop());
    }

    s1.push(x);

    while (!s1.empty()) {
        s2.push(s1.pop());
    }
}

[coconilu]

对比LeetCode官方解法和东哥解法，我发现不一样的地方。 官方是在push的时候整理队列，东哥是在pop的时候整理队列，时间复杂度都是n。 但是我觉得官方的比较好理解一些。