09 | 面试题：用队列实现栈&用栈实现队列-算法面试通关 50 讲

当前位置:　首页>> 技术小册>> 算法面试通关 50 讲

09 | 面试题：用队列实现栈 & 用栈实现队列

在算法面试中，数据结构的灵活运用是考察重点之一。特别是当面试官要求你使用一种数据结构去模拟另一种数据结构的行为时，这不仅考验了你对数据结构内部原理的理解，还检验了你的逻辑思维能力和编程实现能力。本章节将深入探讨两个经典问题：一是如何使用队列（Queue）实现栈（Stack）的功能，二是如何使用栈（Stack）实现队列（Queue）的功能。通过这两个问题的解析，你将深刻理解到不同数据结构之间的转换与互操作。

一、使用队列实现栈

栈（Stack）是一种后进先出（LIFO, Last In First Out）的数据结构，它只允许在栈顶进行添加（push）或删除（pop）元素的操作。而队列（Queue）则是一种先进先出（FIFO, First In First Out）的数据结构，元素从一端加入（队尾），从另一端移除（队首）。要用队列实现栈，关键在于如何逆转元素的顺序，使得最后进入的元素能够最先被移除。

1. 思路分析

单队列实现：最直接的方法是利用两个队列，但在面试中，为了展示你的创造力，可以尝试仅用一个队列来实现。核心思想是，每次进行push操作时，将新元素直接加入到队列的末尾；而在进行pop操作时，除了队列末尾的元素外，将队列中其他所有元素依次出队并入队到队列尾部，这样原本在队列前端的元素（即最后入队的元素）就被移动到了队列的末尾，实现了栈的pop操作。
双队列实现：使用两个队列，一个作为主队列用于存储元素，另一个作为辅助队列。push操作时将元素加入主队列末尾；pop操作时将主队列中除了最后一个元素外的所有元素依次出队并入队到辅助队列，然后将主队列和辅助队列的角色互换，此时原主队列的最后一个元素即成为新主队列（原辅助队列）的队首元素，可以直接出队，模拟栈的pop操作。

2. 代码实现（单队列版）

class MyStack:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.queue = []
    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        self.queue.append(x)
    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        if not self.queue:
            return None
        n = len(self.queue)
        for _ in range(n - 1):
            self.queue.append(self.queue.pop(0))  # 移动元素至队尾
        return self.queue.pop(0)  # 返回原队尾元素，即栈顶元素
    def top(self) -> int:
        """
        Get the top element.
        """
        if not self.queue:
            return None
        return self.queue[-1]
    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return not self.queue

注意：上述单队列实现在pop操作时的时间复杂度为O(n)，因为需要移动n-1个元素。在实际应用中，如果追求效率，建议使用双队列实现。

二、使用栈实现队列

与用队列实现栈相反，使用栈实现队列的目标是利用栈的后进先出特性来模拟队列的先进先出行为。

1. 思路分析

两个栈实现：为了模拟队列的先进先出，我们可以使用两个栈。一个作为输入栈（inputStack），用于接收新元素；另一个作为输出栈（outputStack），用于移除元素。当需要从队列中移除元素时，如果输出栈为空，则将输入栈中的所有元素依次弹出并压入输出栈，这样输出栈的栈顶元素即为队列的队首元素，可以直接弹出。如果输出栈不为空，则直接从输出栈弹出栈顶元素即可。

2. 代码实现

class MyQueue:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.inputStack = []
        self.outputStack = []
    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.inputStack.append(x)
    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        self._move_to_output()
        return self.outputStack.pop()
    def peek(self) -> int:
        """
        Get the front element.
        """
        self._move_to_output()
        return self.outputStack[-1]
    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return not self.inputStack and not self.outputStack
    def _move_to_output(self):
        """
        将输入栈中的所有元素移动到输出栈，如果输出栈为空。
        """
        if not self.outputStack:
            while self.inputStack:
                self.outputStack.append(self.inputStack.pop())

在上述实现中，_move_to_output方法负责在需要时（即输出栈为空时）将输入栈的所有元素转移到输出栈。这样，输出栈的栈顶元素就始终对应于队列的队首元素，实现了队列的先进先出特性。push操作的时间复杂度为O(1)，而pop和peek操作在最坏情况下（即输出栈为空时）的时间复杂度为O(n)，因为需要移动n个元素。但在均摊分析下，这些操作的时间复杂度可以视为O(1)，因为每个元素从输入栈移动到输出栈只发生一次。

总结

通过本章的学习，我们不仅掌握了如何使用队列实现栈以及如何使用栈实现队列的具体方法，还深刻理解了数据结构之间的内在联系和转换机制。这些技巧在算法面试中尤为重要，它们能够展示你的编程功底和问题解决能力。希望读者能够灵活运用这些技巧，在面试中脱颖而出。