Chapter 3 | 栈和队列

如果您熟悉数据结构的细节，那么有关堆栈和队列的问题将更容易处理。不过，这些问题可能相当棘手。有些问题可能仅仅是对原始数据结构的轻微修改，但是其他问题则将面临更复杂的挑战。

实现一个栈

堆栈数据结构正如它听起来的样子：一堆数据。在某些类型的问题中，将数据存储在堆栈中可能比存储在数组中更好。

堆栈使用 LIFO（后进先出）的顺序。也就是说，就像在一堆餐盘中一样，添加到堆栈中的最新项是要删除的第一个项。 它使用以下操作：

  • pop () : Remove the top item from the stack.
  • push (item) : Add an item to the top of the stack.
  • peek () : Return the top of the stack.
  • isEmpty () : Return true if and only if the stack is empty.

与数组不同，堆栈不提供对第 i 项的固定时间（constant-time）访问。但是，它允许固定时间的添加和删除，因为它不需要移动元素。

我们提供了实现堆栈的简单示例代码。注意，如果数据项是从同一侧添加和删除的，也可以使用链表实现堆栈。

  1. 1     public class MyStack<T> {
  2. 2         private static class StackNode<T> {
  3. 3             private T data;
  4. 4             private StackNode<T> next;
  5. 5
  6. 6             public StackNode(T data) {
  7. 7                 this.data = data;
  8. 8             }
  9. 9         }
  10. 10
  11. 11         private StackNode<T> top;
  12. 12
  13. 13         public T pop() {
  14. 14             if (top == null) throw new EmptystackException();
  15. 15             T item = top.data;
  16. 16             top = top.next;
  17. 17             return item;
  18. 18         }
  19. 19
  20. 20         public void push(T item) {
  21. 21             StackNode<T> t = new StackNode<T>(item);
  22. 22             t.next = top;
  23. 23             top= t;
  24. 24         }
  25. 25
  26. 26         public T peek() {
  27. 27             if (top == null) throw new EmptyStackException();
  28. 28             return top.data;
  29. 29         }
  30. 30
  31. 31         public boolean isEmpty() {
  32. 32             return top == null;
  33. 33         }
  34. 34     }

经常有用到堆栈一种情况是在某些递归算法中。有时候，你需要在递归时将临时数据 push 到堆栈中，然后在回溯（backtrack）时删除它们（例如，因为递归检查失败）。堆栈提供了一种直观的方法来实现。

堆栈还可以用于迭代地实现递归算法。（这是一个很好的练习！采用简单的递归算法并迭代实现。）

实现一个队列

A queue implements FIFO (first-in first-out) ordering. As in a line or queue at a ticket stand, items are removed from the data structure in the same order that they are added. It uses the operations:

队列使用 FIFO（先进先出）的顺序。就像在售票亭排队一样，数据项将按照添加它们的顺序从数据结构中删除。

它使用以下操作：

  • add (item) : Add an item to the end of the list.
  • remove () : Remove the first item in the list.
  • peek () : Return the top of the queue.
  • isEmpty () : Return true if and only if the queue is empty.

队列也可以用链表实现。事实上，它们本质上是一样的，它们本质上是一样的。

  1. 1     public class MyQueue<T> {
  2. 2         private static class QueueNode<T> {
  3. 3             private T data;
  4. 4             private QueueNode<T> next;
  5. 5
  6. 6             public QueueNode(T data) {
  7. 7                 this.data = data;
  8. 8             }
  9. 9         }
  10. 10
  11. 11         private QueueNode<T> first;
  12. 12         private QueueNode<T> last;
  13. 13
  14. 14         public void add(T item) {
  15. 15             QueueNode<T> t = new QueueNode<T>(item);
  16. 16             if (last != null) {
  17. 17                 last.next= t;
  18. 18             }
  19. 19             last = t;
  20. 20             if (first== null) {
  21. 21                 first= last;
  22. 22             }
  23. 23         }
  24. 24
  25. 25         public T remove() {
  26. 26             if (first== null) throw new NoSuchElementException();
  27. 27             T data= first.data;
  28. 28             first= first.next;
  29. 29             if (first == null) {
  30. 30                 last = null;
  31. 31             }
  32. 32             return data;
  33. 33         }
  34. 34
  35. 35         public T peek() {
  36. 36             if (first== null) throw new NoSuchElementException();
  37. 37             return first.data;
  38. 38         }
  39. 39
  40. 40         public boolean isEmpty() {
  41. 41             return first== null;
  42. 42         }
  43. 43     }

更新队列中的第一个和最后一个节点尤其容易出错。一定要仔细检查一下。

经常使用队列的地方是广度优先搜索（breadth-first search）或实现一个缓存（cache）。

例如，在广度优先搜索中，我们使用队列来存储我们需要处理的节点列表。每次处理节点时，都将其相邻节点添加到队列的后面。这允许我们按照查看顺序处理节点。

Interview Questions

  • 3.1 三合一（Three in One）：描述如何使用单个数组实现三个栈。

    提示：#2, #72, #38, #58

  • 3.2 Min函数（Stack Min）：设计一个栈，除了 push 和 pop，还有一个返回最小元素的函数 min。push、pop 和 min 的运行时间都应为 0(1)。

    提示：#27, #59, #78

  • 3.3 一摞盘子（Stack of Plates）：想象有一摞盘子。如果这摞盘子堆得太高，它可能会倒塌。因此，在现实生活中，当前一摞盘子的高度超过某个阈值时，我们可能需要重新放一摞。实现一个类似于此的数据结构 SetOfStacks 。SetOfStacks 应该由几个栈组成，并且应该在前一个栈超过容量时创建一个新的栈。SetOfStacks.push() 和SetOfStacks.pop() 的作用应该与单个堆栈相同（即，pop() 返回的值应该与仅有单个堆栈时的返回值相同）。

    FOLLOW UP

    实现一个函数 popAt(int index)，它在特定的子堆栈上执行 pop 操作。

    提示：#64, #87

  • 3.4 通过堆栈实现队列（Queue via Stacks）：实现一个 MyQueue 类，它使用两个堆栈实现一个队列。

    提示：#98, #774

  • 3.5 排序堆栈（Sort Stack）：编写一个程序对栈进行排序，使最小的项在栈顶。可以使用额外的临时堆栈，但不能将元素复制到任何其他数据结构（如数组）中。堆栈支持以下操作：push、pop、peek 和 Empty。

    提示：# 15, #32, #43

  • 3.6 动物收容所（Animal Shelter）：动物收容所只收容猫狗，实行“先进先出”的原则。人们必须在动物收容所里收养“最老的”动物（根据到达时间），或者他们可以选择他们更喜欢狗还是猫（并且将收养这种类型中最老的动物）。他们不能选择他们想要的特定动物。创建数据结构以维护该系统，并实现诸如 enqueue，dequeueAny，dequeueDog 和 dequeueCat 之类的操作。你可以使用内置的链表数据结构。

    提示：#22, #56, #63

附加问题：链表(#2.6)，中等问题(#16.26)，困难问题(#17.9)。

提示从第 653 页开始。