文档介绍：第三章栈和队列栈和队列是两种特殊的线性表,是操作受限的线性表,(stack)栈的定义和特点定义:限定仅在表尾进行插入或删除操作的线性表,表尾—栈顶,表头—栈底,不含元素的空表称空栈特点:先进后出(FILO)或后进先出(LIFO)ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)#defineSTACK_INIT_SIZE100;#defineSTACKINCREAMENT10;typedefstruct{ SELemType*base; SElemType*top; intstacksize;}SqStack;栈的存储结构顺序栈实现:动态栈顶指针top,指向实际栈顶后的空位置,初值为top=basetop进栈Atop出栈栈满BCDEFtop=base,栈空,此时出栈,则下溢(underflow)top-base>=stacksize,栈满,此时入栈,需重新分配空间,如空间分配失败则上溢(overflow)toptoptoptoptoptoptoptoptoptoptop栈空base=0123450栈空top=0123450base123450ABCDEFbase算法构造空栈s返回栈顶元素if(==)returnERROR;e=*(-1);进栈if(->=){=(ElemType*)realloc(,+STACKINCREAMENT)*sizeof(ElemType);if(!)exit(OVERFLOW);=+;+=STACKINCREAMENT;}*++=e;出栈if(==)retuen ERROR;e=*--;入栈算法出栈算法链栈栈顶^…...topdatalink栈底结点定义入栈算法出栈算法typedefstructnode{intdata;structnode*next;}JD;^…...栈底toptopxptop^…...栈底topq数制转换:(159)10=(237)81598198280237余7余3余2toptop7top73top732栈的应用例把十进制数159转换成八进制数括号匹配的检验检验括号是否匹配的方法可用"期待的急迫程度"这个概念来描述。toptop[top[(top[((top[(top[top例如考虑下列括号序列:[(())]123456回文游戏:顺读与逆读字符串一样(不含空格)(原串),非回文若直到栈空都相等,回文字符串:“madamimadam”