《数据结构 》第4章 栈与队列.pdfVIP

第四章 栈和队列 第四章 栈和队列 《数据结构》20 12. 5 《数据结构》20 12. 5 内容提要 4.1 栈 4.2 算术表达式的计算 4.3 栈与递归 4.4 队列 《数据结构》20 12. 5 《数据结构》20 12. 5 4.1 栈 4.1.1 栈的定义 栈 （stack）又称堆栈，是限定只 在表尾进行插入或删除操作的线性表。 栈 S = ( a , a , …，a ) 1 2 n 是按a , a , …，a 次序进栈的，a 为 1 2 n 1 栈底元素，a 为栈顶元素。 n 《数据结构》20 12. 5 《数据结构》20 12. 5 《数据结构》20 12. 5 《数据结构》20 12. 5 表尾（可以操作的一端）称作栈顶，表头（不能 操作的一端）称作栈底。向栈插入新元素称为进栈， 从栈删除元素称为出栈。 栈的修改是按后进先出原则进行的，所以栈又称 后进先出 （Last In First Out）的线性表。简称LIFO 结构。 S=(a,b,c) d S : S=(a,b,c,d) S d,c : S=(a,b) 《数据结构》20 12. 5 《数据结构》20 12. 5 4.1.2 栈的抽象数据类型定义 ADT STACK is Data： 采用顺序或链接方式存储的栈，其存储类型 为StackType。 Operation： Void InitStack(StackType S); //构造一个空栈S Void ClearStack(StackType S); //将S清为空栈 int StackEmpty(StackType S); //若S为空栈，则返回1，否则返回0 《数据结构》20 12. 5 《数据结构》20 12. 5 ElemType Peek(StackType S); //返回栈元素，但不移动栈顶指针 Void Push(StackType S, const ElemType item); //元素item进栈 ElemType Pop(StackType S); //栈顶元素出栈 int StackFull(StackType S); //若栈满，返回1 ，否则返回0，顺序存储特有 End STACK 《数据结构》20 12. 5 《数据结构》20 12. 5 （1）InitStack(a); //初始化栈a （2）Push(a, 35); //元素35进栈 a=(35) （3）int x=48; Push(a, x); //48进栈