使用两个栈实现队列 - 剑指Offer Day01

"Day01_剑指Offer.md" 在编程面试中，《剑指Offer》是一本非常受欢迎的书籍，它包含了一系列经典的算法和数据结构问题。这篇内容涉及到的问题是使用两个栈来实现一个队列，这是一道典型的利用数据结构特性进行转换的问题。 在Java中，`Stack` 是 `java.util` 包下的一个类，它继承自 `Vector`，提供了后进先出（LIFO）的操作。而队列则是先进先出（FIFO）的数据结构，通常由 `LinkedList` 或 `ArrayDeque` 实现。在这个问题中，由于 `Stack` 的操作速度较慢（因为它是线程安全的），而 `Deque` 提供了更高效的操作，特别是对于队列操作。然而，为了保持线程安全并遵循题目要求，我们将使用两个 `Stack` 对象来模拟队列的行为。 首先，我们需要定义一个名为 `CQueue` 的类，它包含两个 `Stack<Integer>` 实例，`stack1` 和 `stack2`。`stack1` 用于存放插入的元素，而 `stack2` 用于删除操作。 `appendTail(int value)` 方法用于在队列尾部添加元素。由于 `stack1` 是后进先出的，所以直接调用 `push` 方法将元素添加到 `stack1` 底部即可。 `deleteHead()` 方法用于在队列头部删除元素。如果两个栈都为空，说明队列中没有元素，因此返回 -1。如果 `stack2` 为空，我们需要将 `stack1` 中的所有元素转移到 `stack2`，这样 `stack2` 的顶部元素就是队列的头部元素，可以被删除。这个过程通过一个 `while` 循环完成，直到 `stack1` 变空。转移完成后，从 `stack2` 中弹出顶部元素，即完成了删除操作。 这种解决方案巧妙地利用了栈的特性，即使得在没有额外数据结构的情况下，也能实现队列的基本操作。在实际编程面试中，这样的问题能够考察候选人的思维灵活性和对数据结构的理解深度。通过不断地练习此类问题，可以提升解决问题的能力，并为面试做好准备。