栈及其基本运算

2.4.1　栈及其基本运算

1．什么是栈

栈实际上也是线性表，只不过是一种特殊的线性表。在这种特殊的线性表中，其插入与删除运算都只在线性表的一端进行。即在这种线性表的结构中，一端是封闭的，不允许进行插入与删除元素；另一端是开口的，允许插入与删除元素。在顺序存储结构下，对这种类型线性表的插入与删除运算是不需要移动表中其他数据元素的。这种线性表称为栈。

栈（stack）是限定在一端进行插入与删除的线性表。

在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。即栈是按照“先进后出”（FILO，First In Last Out）或“后进先出”（LIFO，Last In First Out）的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。由此可以看出，栈具有记忆作用。

通常用指针top来指示栈顶的位置，用指针bottom指示栈底。

往栈中插入一个元素称为入栈运算，从栈中删除一个元素（即删除栈顶元素）称为退栈运算。栈顶指针top动态反映了栈中元素的变化情况。

如图2-8所示是栈的示意图。

栈这种数据结构在日常生活中也是常见的。例如，子弹夹是一种栈的结构，最后压入的子弹总是最先被弹出，而最先压入的子弹最后才能被弹出。又如，在用一端为封闭另一端为开口的容器装物品时，也是遵循“先进后出”或“后进先出”的原则。

图2-8　栈的示意图

2．栈的顺序存储及其运算

与一般的线性表一样，在程序设计语言中，用一维数组S（1：m）作为栈的顺序存储空间，其中m为栈的最大容量。通常，栈底指针指向栈空间的低地址一端（即数组的起始地址这一端）。如图2-9(a)所示是容量为10的栈顺序存储空间，栈中已有6个元素；如图2-9(b)所示与如图2-9(c)所示分别为入栈与退栈后的状态。

在栈的顺序存储空间S（1：m）中，S（bottom）通常为栈底元素（在栈非空的情况下），S（top）为栈顶元素。top=0表示栈空；top=m表示栈满。

图2-9　栈在顺序存储结构下的运算

栈的基本运算有三种：入栈、退栈与读栈顶元素。

下面分别介绍在顺序存储结构下栈的这三种运算。

（1）入栈运算

入栈运算是指在栈顶位置插入一个新元素。这个运算有两个基本操作：首先将栈顶指针进一（即top加1），然后将新元素插入到栈顶指针指向的位置。

当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不可能再进行入栈操作。这种情况称为栈“上溢”错误。

（2）退栈运算

退栈运算是指取出栈顶元素并赋给一个指定的变量。这个运算有两个基本操作：首先将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量，然后将栈顶指针退一（即top减1）。

当栈顶指针为0时，说明栈空，不可能进行退栈操作。这种情况称为栈“下溢”错误。

（3）读栈顶元素

读栈顶元素是指将栈项元素赋给一个指定的变量。必须注意，这个运算不删除栈顶元素，只是将它的值赋给一个变量，因此，在这个运算中，栈顶指针不会改变。

当栈顶指针为0时，说明栈空，读不到栈顶元素。