栈模型

栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈的顶(top)。对栈的基本操作有 Push（进栈）和 Pop（出栈），前者相当于插入，后者则是删除最后插入的元素。最后插入的元素可以通过使用 Top 例程在执行 Pop 之前进行检查。对空栈进行的 Pop 或 Top 一般被认为是栈 ADT 的错误。另一方面，当运行 Push 时空间用尽是一个实现错误，但不是 ADT 错误。

栈有时又叫做 LIFO（后进后出）表。普通的清空栈的操作和判断是否空栈的测试都是栈的操作指令系统的一部分，但是，对栈所能够做的基本上也就是 Push 和 Pop 操作。

栈的实现

由于栈是一个表，因此任何实现表的方法都能实现栈。

栈的单链表实现

栈的第一种实现方法是使用单链表。可以通过在表前端插入来实现 Push，通过删除表前端元素实现 Pop。Top 操作只是检查表前端元素并返回它的值。有时 Pop 操作和 Top 操作合二为一。

创建一个空栈也很简单，只要创建一个头节点，MakeEmpty 设置 Next 指针指向 NULL。Push 是通过向链表前端进行插入而实现的，其中，表的前端做为栈顶。Top 的实现是通过检查表在第一个位置上的元素而完成的。最后，Pop 是通过删除表的前端的元素而实现的。

很清楚，所有的操作均花费常数时间，因为这些例程没有任何地方涉及栈的大小（空栈除外），更不用说依赖于栈大小的循环了。这种实现方法的缺点在于对 malloc 和 free 的调用开销是昂贵的，特别是于指针操作的例程相比。有的缺点通过使用第二个栈可以避免，第二个栈初识时为空栈。当一个单元从第一个栈弹出时，它只是被放到了第二个栈中，此后，当地一个栈需要新的单元时，他首先去检查第二个栈。

栈的数组实现

栈的另一种实现方法避免了指针并且可能是更流行的解决方案。这种策略的唯一潜在危害是我们需要提前声明一个数组的大小。一般说来，这并不是问题，因为在典型的应用程序中，即使有相当多的栈操作，在任意时刻栈元素的实际个数从不会太大。声明一个数组足够大而不至于浪费太多的空间通常并没有什么困难。如果不能做到这一点，那么节省的做法是使用链表来实现。

用一个数组实现栈很简单的。每一个栈有一个 TopStack，对于空栈它是一个 -1（这就是空栈的初始化）。为了将某个元素 X 压入该栈，我们将 TopOfStack 加 1，然后置 Stack[TopOfStack] = X，其中 Stack 是代表具体栈的数组。未了弹出栈元素，我们置返回值为 Stack[TopOfStack] 然后 TopOfStack 减 1。当然，由于潜在地存在多少个栈，因此 Stack 数组和 TopOfStack 只代表一个栈结构的一部分。使用全局变量和固定名字来表示这种（或任意）数据结构非常不好，因为在大多数实际情况下总是存在多个栈。当编写实际程序的时候，你应该尽可能严格地遵循模型，这样，除一些栈例程外，你的程序的任何部分都没有存取被每个栈蕴含的数组或栈项顶（top-of-stack）变量的可能。这对所有的 ADT 操作都是成立的。像 Ada 和 C++ 这样的现代程序设计语言实际上都能够实施这个法则。

注意，这些操作不仅以常数时间运行，而且是以非常快的常数时间运行。在某些机器上，若在带有自增和自减寻址功能的寄存器上操作，则（整数的）Push 和 Pop 都可以写成一条机器指令。最现代化的计算机将栈操作作为它的指令系统的一部分，这个事实强化了这样一种观念，即栈很可能是计算机科学中仅次于数组的最基本的数据结构。

一个影响栈的执行效率的问题是错误检测。链表实现仔细地检查错误。对空栈的 Pop 或者对满栈的 Push 都将超出数组的界限并引起程序崩溃。显然，我们不愿出现这样的情况。但是，如果把这些条件的检测放到数组实现过程中，那就很可能要花费像实际栈操作那样多的时间。由于这个原因，除非在错误处理及其重要的场合（如在操作系统中），一般在栈例程中省去错误检测就成了惯用手法。虽然在多数情况下可能通过声明一个栈大到不至于使得操作溢出，并保证使用 Pop 操作的例程绝不对一个空栈执行 Pop 而侥幸避免对错误的检测，但是，这充其量只不过是使得程序得以正常运行而已，特别是当程序很大并且不止一个人编写或分若干次写成的时候。因为栈操作花费如此快的常数时间，所以一个程序的主要运行时间很少会花在这些例程上面。这就意味着，忽略错误检测一般是不妥的。你应该随时编写错误检测的代码；如果他们冗长，那么当它们确实耗费太多时间时你总可以将它们去掉。

应用

• 平衡符号（编译器检查）
• 后缀表达式
• 中缀到后缀的转换
• 函数调用