数据结构之栈和队列

《数据结构之栈和队列》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章栈和队列栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS3.1栈（stack）栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)#defineSTACK_INIT_SIZE100;#defineSTACKINCREAMENT10;typedefstruct{SELemType*base;SElemType*top;i

2、ntstacksize;}SqStack;栈的存储结构顺序栈实现：动态栈顶指针top,指向实际栈顶后的空位置，初值为top=basetop进栈Atop出栈栈满BCDEFtop=base,栈空，此时出栈，则下溢（underflow)top-base>=stacksize,栈满，此时入栈，需重新分配空间，如空间分配失败则上溢（overflow)toptoptoptoptoptoptoptoptoptoptop栈空base=0123450栈空top=0123450base123450ABCDEFbase算法构造空栈

3、s返回栈顶元素if(S.top==S.base)returnERROR;e=*(S.top-1);进栈if(S.top－S.base>=S.StackSize){S.base=(ElemType*)realloc(S.base,S.stacksize+STACKINCREAMENT)*sizeof(ElemType);if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREAMENT;}*S.top++=e;出栈if(

4、S.top==S.base)retuenERROR;e=*--S.top;入栈算法出栈算法链栈栈顶^…...topdatalink栈底结点定义入栈算法出栈算法typedefstructnode{intdata;structnode*next;}JD;^…...栈底toptopxptop^…...栈底topq数制转换：(159)10=(237)81598198280237余7余3余2toptop7top73top732栈的应用例把十进制数159转换成八进制数括号匹配的检验检验括号是否匹配的方法可用"期待的急迫程

5、度"这个概念来描述。toptop[top[(top[((top[(top[top例如考虑下列括号序列：[(（）)]123456回文游戏：顺读与逆读字符串一样（不含空格）dadtop1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较若不等，非回文若直到栈空都相等，回文字符串：“madamimadam”行编辑程序一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。例如，可用一个退格符“#”表示前一个字符无效；可用一个退行符“@”，表示当前行中的字符均无效。例如

6、，假设从终端接受了这样两行字符：whli##ilr#e（s#*s)outcha@putchar(*s=#++);则实际有效的是下列两行：while(*s)putchar(*s++);迷宫问题(a)迷宫的图形表示(b)迷宫的二维数组表示求解迷宫中一条路径的方法：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行探索，直到所有可能的通路都探索到为止。这类方法统称回溯法。用一个栈记录走过的位置，，栈中每个元素包括三项，分别记录当前位置的行坐标、列坐标以及在该位置上所选的方向（即d

7、irecton数组的下标值）表达式求值优先关系表3*（7+3*6/2-5）＃<*<(<+<*>/=3*（7+18/2-5）＃<*<(<+-=3*（7+9-5）＃<*<(<+>-=3*（16-5）＃<*<(<->)=3*11输入：3*（7+3*6/2-5#)运算对象栈运算符栈3＃*(7+3*618/2916-51133表达式求值后缀表达式：31522-*70+中缀表达式：31*(5-22)+70中缀表达式到后缀表达式的转换基本思想：顺序扫描中缀表达式，当读入一个运算分量时就立即输出，而在读入一个运算符时，

8、则判断其与栈顶运算符的优先级，是右括号或优先级低于栈顶（乘除优于加法）则栈顶首先把它压入一个运算符栈中，一直等到它的两个运算分量都读到后，才能把它输出，当扫描遇到一个左括号时立即把它推入栈中，继续扫描直到右括号出现，括号内的表达式也按如上规则进行压栈和输出。注意：括号不必输出。后缀表达式求值：使用一个存放运算分量的栈，求值过程顺序扫描后缀表达式，每次遇到运算分量就把它推如栈中，遇到运算符，就从栈中弹