第三章栈以及队列.ppt

[内容提要]*定义:栈(Stack)是限制仅在表的一端进行插入和删除操作的线性表。栈又称为后进先出的线性表,简称LIFO线性表。允许进行插入和删除的一端称为栈顶(top)不允许插入和删除的一端称为栈底(bottom)不含元素的空表称为空栈。特点:线性结构后进先出(LIFO)或先进后出(FILO)栈的基本概念*栈的示例图12345进出*用除法把十进制数转换成二进制数,把所有的余数按出现的逆序排列起来(先出现的余数排在后面,后出现的余数排在前面),十进制数35转换成二进制数35178421011001余数结果:10011例:*栈的顺序存储结构(顺序栈)顺序栈:是利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素,通常用一维数组存放栈的元素。设“指针”top指示栈顶元素的当前位置的后一空位置(下标)。*maxsize...210elemtop=0(初始,堆栈为空)记录当前堆栈顶端元素的后一位置的索引值elemtypeelem[maxsize];inttop=0;top栈的顺序存储结构(顺序栈)*顺序栈的类型说明:#definemaxsize100typedefstruct{elemtypeelem[maxsize];inttop;}sqstacktp;栈的顺序存储结构(顺序栈)*base123450栈空栈顶指针top,=0,栈空,此时出栈,=maxsize,栈满,此时入栈,则上溢toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空topbasebase假设maxsize=6顺序栈的几种情况*初始化(栈置空)操作判栈空函数进栈操作出栈函数求栈深函数读栈顶元函数顺序栈上实现的操作*初始化(栈置空)操作顺序栈上实现的操作voidini_sqstack(sqstacktp*s){s->top=0;}