栈的概念和基本操作

栈的定义

栈(Stack)：只允许在一端进行插入或删除操作的线性表。首先栈是一种线性表，但是限定这种线性表只能在某一端进行插入和删除操作，如图3-1所示。

栈顶(top)：线性表允许进行插入和删除的那一端。

栈底(bottom)：固定的，不允许进行插入和删除的另一端。

空栈：不含任何元素的空表。

假设某个栈S= (a1, a2, a3, a4, a5)，如图3-1所示，则a1为栈底元素，a5为栈顶元素。由于栈只能在栈顶进行插入和删除操作，故进栈次序依次为a1、a2、a3、a4、a5，而出栈次序为a5、a4、a3、a2、al。由此可见，栈的一个明显的操作特性可以概括为后进先出(Last In First Out, LIFO)，故又称为后进先出的线性表。 

图3-1  栈的示意图

注意：我们每接触到一种新的数据结构类型，都应该分别从其逻辑结构、存储结构和对数据的运算三个方面着手，以加深对定义的理解。

栈的基本操作

各种辅导书中给出的基本操作的名称不尽相同，但所表达的意思大致是一样的。这里我们以严蔚敏编写的教材为准给出栈的基本操作，希望读者能熟记下面的基本操作：

InitStack(&S)：初始化一个空栈S。

StackEmpty(S)：判断一个栈是否为空，若栈S为空返回true，否则返回false。

Push(&S, x)：进栈，若栈S未满，将x加入使之成为新顶。

Pop(&S, &x)：出栈，若栈S非空，弹出栈顶元素，并用x返回。

GetTop(S, &x)：读栈顶元素，若栈S非空，用x返回栈顶元素。

ClearStack(&S)：销毁栈，并释放栈S占用的存储空间。

注意：符号'&'是C++特有的，用来表示引用，有的书上用C语言中的指针类型‘*’，也可以达到传址的目的。

在解答算法题时，若题干没有做出限制，可以直接使用这些基本的操作函数。