《计算思维与算法入门》 —2.5 堆栈

2.5    堆栈

堆栈（Stack）是一组相同数据类型的组合，所有的操作均在堆栈顶端进行，具有“后进先出”的特性。所谓后进先出，其实就如同自助餐中餐盘在桌面上一个一个往上叠放，在取用时先拿最上面的餐盘，这是典型的堆栈概念的应用，如图2-37所示。

图2-37  自助餐中餐盘存取就是一种堆栈的应用

堆栈是一种抽象数据结构（Abstract Data Type，ADT），具有下列特性：

（1）只能从堆栈的顶端存取数据。

（2）数据的存取符合“后进先出”的原则。

堆栈压入和弹出的操作过程如图2-38所示。

图2-38  堆栈压入和弹出的操作过程

堆栈的基本运算有表2-1所示的5种。

表2-1  堆栈的基本运算

堆栈压入和弹出操作示意图如图2-39所示。

图2-39  堆栈push（压入）和pop（弹出）操作示意图

堆栈结构在计算机中应用得相当广泛，常用于计算机程序的运行，例如递归调用、子程序的调用。在日常生活中的应用也随处可见，例如大楼的电梯（见图     2-40）、货架上的商品等，其原理都类似于堆栈这样的数据结构。

图2-40  电梯搭乘方式就是一种堆栈的应用