3.1.1 栈的定义

栈（Stack），也称为堆栈，它是一种特殊的线性表，只允许在表的一端进行插入和删除操作。允许在表中地行插入删除操作的一端称为栈顶（Top），另一端称为栈底（Bottom）。栈顶是动态变化的，它由一个称为栈顶指针（top）的变量指示。当表中没有元素时，称为空栈。

栈的插入操作称为入栈或进栈，删除操作称为出栈或退栈。

在栈S=（a₁,a₂,…,a_n）中，a₁称为栈底元素，a_n称为栈顶元素。栈中的元素按照a₁，a₂，…，a_n的顺序依次进栈，当前的栈顶元素为a_n。最先进栈的元素一定在栈底，最后进栈的元素一定在栈顶。每次删除的元素是栈顶元素，也就是最后进栈的元素。因此，栈是一种后进先出的线性表。如图3.1所示。

在图3.1中，a₁是栈底元素，a_n是栈顶元素，由栈顶指针top指示。最先出栈的元素是a_n，最后出栈的元素是a₁。

可以把栈想象成一个木桶，先放进去的东西在下面，后放进去的东西在上面，最先取出来的是最后放进去的，最后取出来的是最先放进去的。

图3.2演示了元素A、B、C、D和E依次进栈和出栈的过程。

如果一个进栈的序列由A、B、C组成，它的出栈序列由ABC、ACB、BAC、BCA和CBA五种可能，只有CAB是不可能的输出序列。因为A、B、C进栈后，C出栈，接着就是B要出栈，A不可能在B之前出栈，所以CAB是不可能出现的序列。