简述用两个栈实现队列 ？

使用两个栈实现队列是一个经典的数据结构问题。队列是一种先进先出（FIFO）的数据结构，而栈是一种后进先出（LIFO）的数据结构。为了用栈实现队列，我们需要两个栈，我们称它们为栈A和栈B。

以下是用两个栈实现队列的基本思路：

1. 入队（Enqueue）操作：当有新元素进入队列时，我们直接将其压入栈A。
2. 出队（Dequeue）操作：当需要从队列中取出元素时，我们首先将栈B中的所有元素弹出（如果栈B不为空），然后将栈A的顶部元素弹出并压入栈B。此时，栈B的顶部元素就是队列中的第一个元素（即最早进入队列的元素），我们将其弹出并返回。如果栈A为空，则队列为空，无法执行出队操作。

以下是使用Python实现的代码示例：

class QueueWithTwoStacks:
    def __init__(self):
        self.stackA = []
        self.stackB = []

    def enqueue(self, x):
        self.stackA.append(x)

    def dequeue(self):
        if not self.stackB:
            while self.stackA:
                self.stackB.append(self.stackA.pop())
        return self.stackB.pop()

# 使用示例
queue = QueueWithTwoStacks()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue())  # 输出：1
print(queue.dequeue())  # 输出：2

这种实现方式的时间复杂度如下：

• 入队操作的时间复杂度是O(1)，因为直接将元素压入栈A的顶部。
• 出队操作的时间复杂度在最坏情况下是O(n)，其中n是队列中元素的数量。当栈B为空时，需要将栈A中的所有元素弹出并压入栈B，这是一个线性时间操作。但在平均情况下，出队操作的时间复杂度是O(1)，因为每个元素只会被从栈A移动到栈B一次。