计算机科学导论：跨学科方法

4.3　栈和队列

在本节，我们将介绍两个相互关联的数据类型：栈和队列，它们都可以来处理任意大小的对象集合。栈和队列都是集合的一些具体实现。我们将集合中的对象称为数据项（item）。一个集合具有四个基本操作：创建一个集合、插入一个项、删除一个项，以及测试集合是否为空。

当我们将一个项插入一个集合中时，目的是明确的。但是当删除一个项时，应该删除哪一个呢？每种类型的集合的删除规则决定了它的特征，并且每种集合也有针对不同性能要求的实现。在现实生活中，你已经遇到过很多种不同的集合和数据项的删除方式，只是你还没有意识到。

例如，队列的删除规则是总是删除集合中存在最长时间的项。这种策略称为“先进先出”（First In First Out，FIFO）。人们排队买票就是遵循这一原则：队列按到达顺序排列，因此离开队列的人比其他人排队的时间长。

栈的删除规则则是一个完全不同的策略：总是删除进入集合时间最短的项。这个策略被称为“后进先出”（Last In First Out，LIFO）。例如，当进入和离开飞机客舱时遵循的策略接近于后进先出：靠近船舱前部的人登机最晚但离开最早。

栈和队列的应用十分广泛，因此，熟悉其基本属性以及每种适用的场景十分重要。它们都是可以用来解决更高级别编程任务的基本数据结构。它们被广泛应用于系统和应用程序设计，在本节和4.5节的几个例子中会涉及。

下推栈　下推栈（或者简称为栈）是一种基于后进先出（LIFO）策略的集合。

下推栈操作示意图

LIFO策略是经常使用的几个计算机应用程序的基础。例如，许多人把电子邮件作为一个栈来组织，当接收到一个新邮件时，会把它放在最上面，位于最上面的邮件先被处理，即最近的日期优先（后进先出）。这个策略的优点是我们可以尽快看到新的邮件，缺点是如果不清空堆栈，一些旧的邮件可能永远不会被阅读。 ...