1.表（TODO）

2.栈

方法调用

• 检测平衡符号的算法提出一种在编译的过程语言和面向对象语言中实现方法调用的方式。这里的问题是，当调用一个新方法时，主调例程的所有局部变量需要由系统存储起来，否则被调用的新方法将会重写由主调例程的变量所使用的内存。不仅如此，该主调例程的当前位置也必须要存储，以便在新方法运行完后知道向哪里转移。这些变量一般由编译器指派给机器的寄存器，但存在某些冲突（通常所有的方法都是获取指定给1号寄存器的某些变量），特别是涉及递归的时候。该问题类似于平衡符号的原因在于，方法调用和方法返回基本上类似于开括号和闭括号，二者相同的想法应该是行得通的。
• 当存在方法调用的时候，需要存储的所有重要信息，诸如寄存器的值（对应变量的名字）和返回地址（它可在程序计数器得到，一般情况是在一个寄存器止中）等，都要以抽象的方式存在“一张纸上”并被置于一个堆（pile）的顶部。然后控制转移到新方法，该方法自由地用它的一些值代替这些寄存器。如果它又进行其他的方法调用，那么它也遵循相同的过程。当该方法要返回时，它查看堆顶部的那张“纸”并复原所有的寄存器，然后进行返回转移。
• 显然，所有全部工作均可由一个栈来完成，而这正是在实现递归的每一种程序设计语言中实际发生的事实。所存储的信息或称为活动记录，或叫做栈帧。在典型的情况下，需要做些微调整：当前环境是由栈顶描述的。因此，一条返回语句就可给出前面的环境（不用复制）。在实际计算机中的栈常常是从内存分区的高端向下增长，而在许多非java系统中是不检查溢出的。由于有太多的同时在运行的方法，因此栈空间用尽的情况总是可能发生的。显而易见，栈空间用尽常是致命的错误。
• 在不进行栈溢出检测的语言和系统中，程序将会崩溃而没有明显的说明；而在java中会抛出一个异常
  *在正常情况下我们不应该越出栈空间，发生这种情况通常是由失控递归的指向引起。
  递归总能够与被彻底去除（编译器是在转变成汇编语言时完成递归去除的），但是这么做是相当冗长乏味的。一般方法是要求使用一个栈，而且当且仅当你能够把最低限度的最小值放到栈上时这个方法才值得一用。非递归程序一般说来确实比等价的递归程序要快，但是速度优势的代价却是由于去除递归而使用程序清晰性受到了影响

3.队列

队列的数组实现

  对于每一个队列数据结构，我们保留一个数组theArray以及位置front和back，它们代表队列的两端。我们还要记录实际存在于队列中的元素的个数currentSize。下图表示某个中间状态的一个队列

array.png
 操作应该是清楚的。为使一个元素x入队（即执行enqueue），我们让currentSize和back增1，然后置theArray[back]=x。 若使元素dequeue(出列)，我们置返回值为theArray[front],且currentSize减1,然后使front增1。也可以有其他的方法（将在后面讨论）。现在论述错误检测。
 上述实现存在一个潜在的问题。经过10次enqueue后队列似乎是满了，因为back现在是数组的最后一个下标，而下一次再enqueue就会是一个不存在的位置。然而，队列中也许只存在几个元素，因为若干元素可能已经出队了。像栈一样，即使在有许多操作的情况下队列也常常不是很大。
 简单的解决方法是，只要front或back到达数组的尾端,它就又绕回道开头。下面诸图显示在某些操作期间的队列情况。这叫做循环数组的实现。
 实现回绕所需要的附加代码是极小的（不过它可能使得运行时间加倍）。如果front或back增1导致超越了数组，那么其值就要重置到数组的第一个位置。
queue.png
队列为空时（back=fromt-1）,队列的大小可以通过比较back跟front隐式地算出。