栈和队列PPT课件.ppt

文档介绍：第三章栈和队列栈和队列是两种特殊的线性表,是操作受限的线性表,(stack)栈的定义和特点定义:限定仅在表尾进行插入或删除操作的线性表,表尾—栈顶,表头—栈底,不含元素的空表称空栈特点:先进后出(FILO)或后进先出(LIFO)ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)栈的存储结构栈顺序存储表示:#defineSTACK_INIT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量typedefstruct {Selemtype*base;//在栈构造之前和销毁之后,base的值为NULL Selemtype*top;//栈顶指针 intstacksize;//当前已分配的存储空间,以元素为单位 }sqstack;栈的基本操作:P46base123450栈空栈顶指针top,指向实际栈顶后的空位置,初值为0top123450进栈Atop出栈栈满BCDEFtop=0,栈空,此时出栈,则下溢top=stacksize,栈满,此时入栈,则上溢toptoptoptoptop123450ABCDEFtoptoptopbasetopbase栈的操作演示:top构造一个空栈statusinitstack(sqstack&s) {=(Selemtype*)malloc(STACK_INIT_SIZE*sizeof(Selemtype)); if(!)exit(overflow);=; =STACK_INIT_SIZE; returnOK; }销毁栈statusdestorystack(sqstack&s) {if(!) exit(error); free(); ==NULL; returnOK; }置栈为空栈statusclearstack(sqstack&s) {if(!) exit(error); =; returnOK; }判空intstackempty(sqstacks) {==; }0M-1栈1底栈1顶栈2底栈2顶在一个程序中同时使用两个栈链栈栈顶^…...top栈底^…...栈底toptopxp入栈top^…...栈底topq出栈栈的应用数值转换例把十进制数159转换成八进制数(159)10=(237)81598198280237余7余3余2toptop7top73top732回文游戏:顺读与逆读字符串一样(不含空格)(原串),非回文若直到栈空都相等,回文括号匹配的检验:行编辑程序迷宫求解字符串:“madamimadam”