数据结构（Python Java）（微课版） 课件 3.1 栈

数据结构与算法设计3.1栈栈的定义与基本操作栈的顺序存储结构与实现栈的链式存储结构与实现顺序栈和链栈的比较栈的应用案例栈的定义与基本操作栈的定义栈：限定仅在一端进行插入和删除操作的线性表（a1,…,an-1,an）栈顶（top）：允许插入和删除的一端称为栈顶栈底（bottom）：另一端称为栈底插入位置：1~n+1删除位置：1~n线性表插入位置：n+1删除位置：n栈栈底栈顶栈的定义与基本操作栈的操作插入：入栈、进栈、压栈删除：出栈、弹栈a插入删除bc此时执行出栈操作，哪个元素可以出栈呢？栈的操作特性：后进先出（LastInFirstOut，LIFO）空栈：不含任何数据元素的栈

如何判空栈

initStack()：初始化操作。设置一个空栈isEmpty()：判栈空函数。若为空，则返回true，否则返回false。getTop()：读栈顶元函数。若栈不空，函数值为栈顶元素，否则为空元素NULLpush(x)：进栈操作。将元素x插入栈中，使x成为栈的栈顶元素pop()：出栈函数。若栈不空，函数值为栈顶元素，且从栈中删除当前栈顶元素，否则函数值为空元素NULLclearStack()：栈置空操作。不论栈是否为空栈，置为空栈栈的定义与基本操作栈的基本操作栈的定义与基本操作栈的抽象数据类型定义ADTStackDataModelOperationendADT栈中元素具有相同类型及后进先出特性，相邻元素具有前驱和后继关系initStack：栈的初始化clearStack：清空栈内元素push：入栈pop：出栈getTop：取栈顶元素isEmpty：判空利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素a1a2……an顺序栈Sai……0n栈底栈顶top栈的顺序存储结构与实现顺序栈用数组的一端作为栈底设变量top存储栈顶元素所在的下标组织形式与单链表类似，链表的尾部是栈底，链表的头部是栈顶FtopdatanextEDANULL栈顶栈底栈的链式存储结构与实现链栈顺序栈和链栈的比较顺序栈和链栈的基本算法的时间复杂度均为O(1)空间复杂度比较Java中，初始时顺序栈需要确定栈的长度，所以存在存储元素个数的限制和浪费存储空间的问题。链栈没有栈满的问题，只有当内存没有可用存储空间时才会出现栈满，但是每个元素都需要指针域，从而存在结构性开销。把所有的余数按出现的逆序排列起来（先出现的余数排在后面，后出现的余数排在前面）十进制数转换成二进制数栈的应用351784210110001余数结果：100011表达式求值栈的应用对算术表达式求值：

1+2*4-9/3遵循先乘除后加减、先左后右及先括号内，后括号外的四则运算法则，其计算顺序应为：1+2*4-9/3└─┘└─┘①②└──┘③└───┘④采用“运算符优先数法”对每种运算符赋于一个优先数，如：运算符：*/+-#优先数：22110其中

#是表达式结束符表达式求值时，设立两个栈运算符栈(OPTR)操作数栈(OPND)分别存放表达式中的运算符和操作数

步骤OPTR栈OPND栈输入字符主要操作──────────────────────────────────────────

1 # 1+2*4-9/3# PUSH(OPND,'1')2 # 1+2*4-9/3#PUSH(OPTR,'+')3 #+ 12*4-9/3# PUSH(OPND,'2')4 #+ 12*4-9/3# PUSH(OPTR,'*')5 #+* 124-9/3# PUSH(OPND,'4')6 #+* 124-9/3# OPERATE('2','*','4')7 #+ 18-9/3# OPERATE('1','+','8')8 # 9-9/3# PUSH(OPTR,'-')9 #- 99/3# PUSH(OPND,'9')10 #- 99/3# PUSH(OPTR,'/')11 #-/ 993# PUSH(OPND,'3')12 #-/ 993# OPERATE('9','/','3')13 #- 93# OPERATE('9','-','3')14