队列实现栈以及栈实现队列

队列是一种先进先出的数据结构，栈是一种先进后出的数据结构，形象一点就是这样：

这两种数据结构底层其实都是数组或者链表实现的，只是 API 限定了它们的特性

今天来看看如何使用「栈」的特性来实现一个「队列」，如何用「队列」实现一个「栈」。

一、用栈实现队列

力扣第 232 题「用栈实现队列」让我们实现的 API 如下：

lass MyQueue:

    # 添加元素到队尾
    def push(self, x: int) -> None:
        pass

    # 删除队头的元素并返回
    def pop(self) -> int:
        pass

    # 返回队头元素
    def peek(self) -> int:
        pass

    # 判断队列是否为空
    def empty(self) -> bool:
        pass

我们使用两个栈 s1, s2 就能实现一个队列的功能（这样放置栈可能更容易理解）：

当调用 push 让元素入队时，只要把元素压入 s1 即可，比如说 push 进 3 个元素分别是 1,2,3，那么底层结构就是这样：

那么如果这时候使用 peek 查看队头的元素怎么办呢？按道理队头元素应该是 1，但是在 s1 中 1 被压在栈底，现在就要轮到 s2 起到一个中转的作用了：当 s2 为空时，可以把 s1 的所有元素取出再添加进 s2，这时候 s2 中元素就是先进先出顺序了：

当 s2 中存在元素时，直接调用操作 s2 的 pop 方法，弹出的就是最先插入的元素，即实现了队列的 pop 操作。

完整代码如下：

class MyQueue:
    def __init__(self):
        # 使用两个栈s1和s2
        self.s1 = []
        self.s2 = []

    # 添加元素到队尾
    def push(self, x: int) -> None:
        self.s1.append(x)

    # 返回队头元素
    def peek(self) -> int:
        if not self.s2:
            # 把 s1 元素压入 s2
            while self.s1:
                self.s2.append(self.s1.pop())
        return self.s2[-1]

    # 删除队头元素并返回
    def pop(self) -> int:
        # 先调用 peek 保证 s2 非空
        self.peek()
        return self.s2.pop()

    # 判断队列是否为空
    # 两个栈都为空才说明队列为空
    def empty(self) -> bool:
        return not self.s1 and not self.s2

至此，就用栈结构实现了一个队列，核心思想是利用两个栈互相配合。

值得一提的是，这几个操作的时间复杂度是多少呢？

有点意思的是 peek 操作，调用它时可能触发 while 循环，这样的话时间复杂度是 O(N)，但是大部分情况下 while 循环不会被触发，时间复杂度是 O(1)。由于 pop 操作调用了 peek，它的时间复杂度和 peek 相同。

像这种情况，可以说它们的最坏时间复杂度是 O(N)，因为包含 while 循环，可能需要从 s1 往 s2 搬移元素。

但是它们的均摊时间复杂度是 O(1)，这个要这么理解：对于一个元素，最多只可能被搬运一次，也就是说 peek 操作平均到每个元素的时间复杂度是 O(1)。

二、用队列实现栈

如果说双栈实现队列比较巧妙，那么用队列实现栈就比较简单粗暴了，只需要一个队列作为底层数据结构就能实现了。

力扣第 225 题「用队列实现栈」让我们实现如下 API：

class MyStack:

    # 添加元素到栈顶
    def push(self, x: int) -> None:
        pass
    
    # 删除栈顶的元素并返回
    def pop(self) -> int:
        pass
    
    # 返回栈顶元素
    def top(self) -> int:
        pass
    
    # 判断栈是否为空
    def empty(self) -> bool:
        pass

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

class MyStack:
    def __init__(self):
        # 使用一个队列 q 来实现一个栈
        self.q = []
        # 栈顶元素
        self.top_elem = 0
    
    # 添加元素到栈顶
    def push(self, x: int) -> None:
        # x 是队列的队尾，是栈的栈顶
        self.q.append(x)
        self.top_elem = x
    
    # 返回栈顶元素
    def top(self) -> int:
        return self.top_elem

    # 检查栈是否为空
    def empty(self) -> bool:
        return len(self.q) == 0

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

解决方法简单粗暴，把队列前面的都取出来再加入队尾，让之前的队尾元素排到队头，这样就可以取出了：

class MyStack:
    # 为了节约篇幅，省略上文给出的代码部分...

    # 删除栈顶的元素并返回
    def pop(self):
        size = len(self.q)
        while size > 1:
            self.q.append(self.q.pop(0))
            size -= 1
        # 之前的队尾元素已经到了队头
        return self.q.pop(0)

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

class MyStack:
    # 为了节约篇幅，省略上文给出的代码部分...

    # 删除栈顶的元素并返回
    def pop(self):
        size = len(self.q)
        # 留下队尾 2 个元素
        while size > 2:
            self.q.append(self.q.pop(0))
            size -= 1
        # 记录新的队尾元素
        self.top_elem = self.q[0]
        self.q.append(self.q.pop(0))
        # 删除之前的队尾元素
        return self.q.pop(0)

这样就实现完了，完整的代码如下：

from queue import Queue

class MyStack:
    def __init__(self):
        self.q = Queue()
        self.top_elem = 0

    # 添加元素到栈顶
    def push(self, x: int) -> None:
        self.q.put(x)
        self.top_elem = x

    # 删除栈顶的元素并返回
    def pop(self) -> int:
        size = self.q.qsize()
        while size > 2:
            self.q.put(self.q.get())
            size -= 1
        self.top_elem = self.q.queue[0]
        self.q.put(self.q.get())
        return self.q.get()

    # 返回栈顶元素
    def top(self) -> int:
        return self.top_elem

    # 判断栈是否为空
    def empty(self) -> bool:
        return self.q.empty()