3.1.1　栈的定义及基本运算

图3－1 栈示意图

栈是限制在表的一端进行插入和删除的线性表。允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。当表中没有元素时称为空栈。如图3－1所示栈中，进栈的顺序是a1，a2，a3，…，an，当需要出栈时其顺序为an，…，a3，a2，a1，所以栈又称为后进先出的线性表（Last In First Out），简称LIFO表。

在日常生活中，有很多后进先出的例子，读者可以列举。在程序设计中，常常需要栈这样的数据结构，使得与保存数据时相反的顺序来使用这些数据，这时就需要用一个栈来实现。

栈的插入操作，叫作进栈，也叫入栈。栈的删除操作，叫作出栈，也叫弹栈。

下面讨论一下进栈出栈的变化形式，是不是最先进栈的元素一定最后一个出栈呢？不一定，因为进栈和出栈的先后虽然受到限制，但是时间没有受到限制。举例来说，若有三个元素1、2、3依次进栈，出栈顺序有几种呢？

第一种，1、2、3依次进栈，出栈顺序一定是3、2、1；

第二种，1进，2进，2出，1出，3进，3出，出栈顺序是2、1、3；

第三种，1进，1出，2进，3进，3出，2出，出栈顺序1、3、2；

第四种，1进，2进，2出，3进，3出，1出，出栈顺序2、3、1；

第五种，1进，1出，2进，2出，3进，3出，出栈顺序1、2、3。

由此可知，3个元素有5种可能的出栈顺序，多个元素数量更多，可见元素的出栈形式是多变的。

对于栈，常作的基本运算有以下几种。

（1）栈初始化：Init＿Stack（s）

初始条件：栈s不存在。

操作结果：构造了一个空栈。

（2）判栈空：Empty＿Stack（s）

初始条件：栈s已存在。

操作结果：若s为空栈返回为1，否则返回为0。

（3）入栈：Push＿Stack（s，x）

初始条件：栈s已存在。

操作结果：在栈s的顶部插入一个新元素x，x成为新的栈顶元素。栈发生变化。

（4）出栈：Pop＿Stack（s）

初始条件：栈s存在且非空。

操作结果：栈s的顶部元素从栈中删除，栈中少了一个元素。栈发生变化。

（5）读栈顶元素：Top＿Stack（s）

初始条件：栈s存在且非空。

操作结果：栈顶元素作为结果返回，栈不变化。