两栈法实现先进先出队列

在本题中，我们需要实现一个名为 `MyQueue` 的类，该类使用两个栈来模拟一个队列，遵循先入后出（FIFO）的原则。队列支持以下操作： 1. **push(int x)**: 将元素 `x` 添加到队列的末尾，即将元素压入后一个栈（称为后进栈）。 2. **pop()**: 从队列的开头移除并返回元素，即从第一个栈（称为先进栈）弹出元素。 3. **peek()**: 返回队列开头的元素，但不删除，相当于查看先进栈的栈顶元素。 4. **empty()**: 检查队列是否为空，如果为空则返回 `true`，否则返回 `false`。 为了实现这些功能，我们需要确保先进栈始终保存着队列的前部元素，而后进栈用于存储新加入的元素。当先进栈满时，我们将先进栈的元素转移到后进栈，保持先进栈的头部总是队列的第一个元素。 以下是关键的实现步骤： - 初始化两个栈 `stack1` 和 `stack2`，其中 `stack1` 作为先进栈，`stack2` 作为后进栈。 - **push(int x)**: - 如果 `stack1` 已满，将 `stack1` 的所有元素依次转移到 `stack2`。 - 然后将 `x` 压入 `stack1`。 - 保持 `stack1` 作为先进栈，因为新的元素总是入队到它的底部。 - **pop()**: - 如果 `stack1` 为空，说明队列已空，返回 `false` 或者抛出异常。 - 否则，从 `stack1` 弹出并返回栈顶元素。 - **peek()**: - 直接查看 `stack1` 的栈顶元素，无需移除，因为 `stack1` 保存了队列的头部。 - **empty()**: - 检查两个栈的大小，如果它们都为空，返回 `true`，否则返回 `false`。 为了达到进阶要求，即每个操作的平均时间复杂度为 O(1)，我们需要优化内存分配和检查栈容量的部分。在题目给出的代码片段中，`checkCapcity` 函数用于检测栈是否达到其当前容量。当 `stack1` 和 `stack2` 的大小之和接近或等于 `capacity` 时，将 `capacity` 扩大一倍。这样，当一个栈满时，另一个栈的空间利用率还很高，可以保证操作效率。 这个实现利用了栈的特性，通过动态调整容量和数据迁移策略，高效地实现了队列的操作。同时，通过维护先进栈和后进栈的平衡，确保了对先进先出规则的遵守。需要注意的是，由于使用了 C 语言的 `realloc` 功能进行内存扩展，实际操作时可能会带来额外的性能开销，但只要合理设计，总体上应该能够满足 O(1) 的平均时间复杂度要求。