3.1.1　栈的基本知识

1. 栈的定义

栈是一种操作受限的线性表，栈的插入和删除操作只能在表的一端进行，这一端称作栈顶(top)；另一端称作栈底(bottom)。记作：

2. 栈的操作特征

栈的操作特征是“后进先出”(Last In First Out，LIFO)。故栈又称作后进先出线性表，简称LIFO表。

3. 栈的存储结构

栈是线性表的一种特例，所以线性表的顺序存储和链式存储都可以作为栈的存储结构。采用顺序存储结构的栈称为“顺序栈”；采用链式存储结构的栈称为“链栈”。图3-1示出了这两种栈的结构。

图3-1　栈结构示意图

4. 栈的5种基本操作

(1) 置栈空SetEmpty(S) 将栈S置成空栈。

(2) 判栈空IsEmpty(S) 若S为空栈，函数值为“真”；否则为“假”。

(3) 取栈顶元素GetTop(S) 读取栈S的顶部元素值。

(4) 入栈Push(S，x) 向栈S的顶部插入元素x。

(5) 出栈Pop(S) 删除栈S的顶部元素。

5. 栈的典型应用

(1) 表达式求值。

(2) 子程序的嵌套调用和递归调用。

(3) 列车进、出站台的调度。