Skip to content

Latest commit

 

History

History
179 lines (127 loc) · 6.37 KB

Chapter_3_Stacks_and_Queues.md

File metadata and controls

179 lines (127 loc) · 6.37 KB
Raw

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