双栈队列如何实现多线程安全？

核心回答

给整个双栈队列使用同一把互斥锁，保护入队、查看和出队，并把“判断输出栈为空、搬运输入栈、弹出结果”放在一次持锁操作里。这样其他线程看不到搬运了一半的状态，队列操作可以按各次持锁的先后理解为顺序发生。

仅把两个栈换成线程安全容器，或者给两个栈分别加锁，都不足以保护跨栈的不变式。empty() 的返回值也只是调用时的快照，不能保证下一次 pop() 一定成功。

Python 实现

以下接口在空队列时立即抛错，不是阻塞队列。即使运行在带 GIL 的解释器中，也明确使用锁，不依赖多条操作碰巧不会被切换。

from threading import Lock

class SafeTwoStackQueue:
    def __init__(self):
        self.inbox, self.outbox = [], []
        self.lock = Lock()

    def push(self, value):
        with self.lock:
            self.inbox.append(value)

    def pop(self):
        with self.lock:
            if not self.outbox:
                while self.inbox:
                    self.outbox.append(self.inbox.pop())
            if not self.outbox:
                raise IndexError("empty queue")
            return self.outbox.pop()

    def peek(self):
        with self.lock:
            if not self.outbox:
                while self.inbox:
                    self.outbox.append(self.inbox.pop())
            if not self.outbox:
                raise IndexError("empty queue")
            return self.outbox[-1]

    def empty(self):
        with self.lock:
            return not self.inbox and not self.outbox

锁究竟保护什么

假设输出栈为空，线程甲开始从输入栈搬运；若线程乙此时直接弹输出栈，可能拿到最新元素而不是最早元素。因此搬运不是可以任意穿插的若干独立栈操作，而是队列出队的一部分。

peek() 与 pop() 一样，在输出栈为空时先把输入栈整体搬到输出栈，再查看输出栈顶；整个过程都在同一把锁内，不通过输入栈的底部索引绕过栈抽象。用户提供的耗时业务处理放在队列取值以后执行，不能占着队列锁运行。

pop() 或 peek() 触发的单次搬运可能持锁 O(n)，所以其他线程可能等待较久。若题目继续要求空队列等待，可在相同锁上增加条件变量，使用 while 检查非空条件；若没有双栈这个实现约束，通常直接选成熟并发队列。

参考资料