Page 87 - 高中 信息技术 选择性必修1 数据与数据结构

 3.4 用栈组织后进先出数据

3.4 用栈组织后进先出数据

队列对应了生活中的排队现象，但还有另一种现象，如对一叠碗的取放：每次把洗净
的碗放好时总是放在这叠碗的最上面，而每次取用的时候也总是取最上面的。在这种现象
中，事物的进出顺序都有共同的特征，那就是后进先出。

广东教育出版社
3.4.1 栈

栈（Stack）是限制只能在一端进行插入和删除的特殊线性表。栈中能进行插入和删
除的一端称为栈顶（Top），而另一固定端称为栈底（Bottom）。把一个数据元素放入
栈中的操作叫作进栈或压栈（Push），从栈中取出一个数据元素的操作称为出栈或弹出

（Pop）。栈中没有元素时，称为空栈。
栈的形式在日常生活中经常出现，例如一叠书、一叠盘子，如果规定取书、取盘子或
放入书、放入盘子都只能在顶部进行，则它就是一个栈。
生活中有很多类似的例子，如购物车的取放（如图3-16所示）、仓库、码头物品的堆

放等。在计算机程序中，我们可以用“栈”这种数据结构来组织和实现这种工作方式。
栈符合这个规律：后放入栈中的数据元素首先取出。故栈又被称为后进先出（LIFO：
Last In First Out）线性表。

图3-16 超市手推购物车停放

79 79

21X2204.indd 79 2019/9/26 13:53:18