如果您熟悉数据结构的细节，那么有关堆栈和队列的问题将更容易处理。不过，这些问题可能相当棘手。有些问题可能仅仅是对原始数据结构的轻微修改，但是其他问题则将面临更复杂的挑战。
堆栈数据结构正如它听起来的样子：一堆数据。在某些类型的问题中，将数据存储在堆栈中可能比存储在数组中更好。
堆栈使用 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）。
例如，在广度优先搜索中，我们使用队列来存储我们需要处理的节点列表。每次处理节点时，都将其相邻节点添加到队列的后面。这允许我们按照查看顺序处理节点。
-
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 页开始。