第三章栈和队列通常称，栈和队列是限定插入和删除插入和删除只能只能在表的“端点端点”进行的线性表。 线性表线性表 栈栈 队列队列Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in栈和队列是两种常用的数据类型栈和队列是两种常用的数据类型3.1 栈的类型定义栈的类型定义3.2 栈类型的实现栈类型的实现3.3 栈的应用举例栈的应用举例3.4 队列的类型定义队列的类型定义3.5 队列类型的实现队列类型的实现栈（stack）定义定义 栈是只能在一端插入和删除的线性表栈是只能在一端插入和删除的线性表特性：后进先出（特性：后进先出（LIFO）或或 先进后出（先进后出（FILO）设栈设栈s=s=（a a1 1，a a2 2，. . . ,. . . ,a ai i，. . . . . . ，a an n），其中其中a a1 1是栈底元素，是栈底元素， a an n是栈顶元素。是栈顶元素。栈顶（栈顶（top)top)：允许插入和删除的一端；允许插入和删除的一端； 约定约定toptop始终指向新数据元素将存放的位置。始终指向新数据元素将存放的位置。栈底（栈底（bottom):bottom):不允许插入和删除的一端。不允许插入和删除的一端。 a1 a2 . an进栈进栈出栈出栈栈顶栈顶栈底栈底3.1 栈的类型定义栈的类型定义 ADT Stack 数据对象数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作：基本操作： ADT StackInitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S, &e)Push(&S, e)Pop(&S, &e)StackTravers(S, visit() InitStack(&S) 操作结果：构造一个空栈S。 DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。StackEmpty(S)初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈，则返回 TRUE，否则 FALE。StackLength(S)初始条件：栈 S 已存在。 操作结果：返回 S 的元素个数，即栈的长度。 GetTop(S, &e) 初始条件：栈 S 已存在且非空。操作结果：用 e 返回 S 的栈顶元素。a1a2an ClearStack(&S)初始条件：栈 S 已存在。 操作结果：将 S 清为空栈。Push(&S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。a1a2ane Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。a1a2anan-1 设数组设数组S是一个顺序栈，栈的最大容量是一个顺序栈，栈的最大容量stacksize=4 ，初始状态初始状态top=0 10S42310basestop=xtop=top+1top 10 25 30S42310topbasetop=top-1x=stop栈空栈空10进栈进栈30出栈出栈S42310Top=0top栈满栈满 top=stacksize 10 25 30 40S42310top=4base3.2栈类型的实现栈类型的实现顺序栈顺序栈链栈链栈 a1 a2 top1.1.顺序栈：顺序栈：一维数组一维数组sM 用顺序存储结构表示的栈。用顺序存储结构表示的栈。 顺顺序序栈栈用用一一组组连连续续的的存存储储单单元元存存放放自自栈栈底底到到栈栈顶顶的的数数据据元元素素，一一般般用用一一维维数数组组表表示示，设设置置一一个个简简单单变变量量top指指示示栈栈顶顶位位置置，称称为为栈栈顶顶指指针针，它它始始终终指指向向待插入元素的位置。待插入元素的位置。top=0123450栈空栈空栈顶指针栈顶指针top,指向实际栈顶后的空位置，初值为0top123450进栈进栈Atop出栈出栈栈满栈满BCDEF设数组维数为Mtop=0,栈空，此时出栈，则下溢下溢（underflow)top=M,栈满，此时入栈，则上溢上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空栈空/- 栈的顺序存储表示栈的顺序存储表示 - #define STACK_INIT_SIZE 100; / 存储空间的初始分配量存储空间的初始分配量 #define STACKINCREMENT 10; / 存储空间的分配增量存储空间的分配增量 typedef struct SElemType *base; / 栈底指针栈底指针 SElemType *top; / 栈顶指针栈顶指针(栈顶元素的下一个位置栈顶元素的下一个位置) int stacksize; / 当前分配的存储容量当前分配的存储容量 SqStack; 类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。1 1）和顺序表一样采用增量式的空间分配；和顺序表一样采用增量式的空间分配；2 2）操作和栈顶相关：）操作和栈顶相关：插入操作（入栈）：将待插元素插入到栈顶插入操作（入栈）：将待插元素插入到栈顶元素的下一个位置；元素的下一个位置；删除操作（出栈）：删除栈顶元素；删除操作（出栈）：删除栈顶元素；取元素操作：取栈顶元素的值。取元素操作：取栈顶元素的值。各操作的操作位置与栈顶元素的位置或其下各操作的操作位置与栈顶元素的位置或其下一个位置相关，希望在一个位置相关，希望在O(1)O(1)时间内能获取操时间内能获取操作位置，故可设置作位置，故可设置专门的栈顶指针专门的栈顶指针toptop。3 3）约定：）约定：toptop指向栈顶元素的下一个位置指向栈顶元素的下一个位置（便于（便于表示空栈）。表示空栈）。4 4）栈顶的初始化：）栈顶的初始化：S.topS.top = = S.baseS.base( (在上述在上述3)3)约约定下的空栈形式定下的空栈形式) )，5 5）栈空：）栈空：S.baseS.base = = S.topS.top， 栈满：栈满：S.topS.top - - S.baseS.base = = S.stacksizeS.stacksize6 6）入栈：）入栈：* *S.topS.top + = e + = e， 出栈：出栈：e = *-e = *-S.topS.top注意：注意：4), 5), 6)4), 5), 6)步受步受3)3)制约。约定不同，相应制约。约定不同，相应的判定和处理也不一样。的判定和处理也不一样。如假设如假设toptop就指向栈顶元素，此时就指向栈顶元素，此时4),5),6)4),5),6)如何如何？基本操作的实现基本操作的实现base空栈a 进栈b 进栈atopbasetopbasetopab约定：约定：top指向栈顶元素的下一个位置指向栈顶元素的下一个位置basee 进栈f 进栈溢出e出栈edcbatopbasetopbasetopedcbadcba Status InitStack (SqStack &S)/ 构造一个空栈S S.base=(ElemType*)malloc(STACK_INIT_SIZE* sizeof(ElemType); if (!S.base) exit (OVERFLOW); /存储分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;取栈顶元素取栈顶元素GetTop_Sq算法设计算法设计参数：顺序栈参数：顺序栈S S、取得的栈顶元素、取得的栈顶元素&e&e分析：由于分析：由于toptop指向栈顶元素的下一个位置，因此实际的栈顶指向栈顶元素的下一个位置，因此实际的栈顶元素的位置应是元素的位置应是top -1top -1；栈非空时，此操作有效。栈非空时，此操作有效。算法算法Status GetTop_Sq(SqStack S, ElemType &e)/* 判断栈是否为空判断栈是否为空 */if ( S.base = S.top) return ERROR;e = *( S.top -1);return OK;入栈操作入栈操作Push_Sq算法设计算法设计参数：顺序栈参数：顺序栈&S&S、插入元素、插入元素e e分析：插入位置为栈顶元素的下一个，无分析：插入位置为栈顶元素的下一个，无须判断位置的合法性；须判断位置的合法性；上溢即栈满的条件需要判断，由于是增量上溢即栈满的条件需要判断，由于是增量式分配，故栈满时需要重新申请空间式分配，故栈满时需要重新申请空间; ; Status Push (SqStack &S, SElemType e) if (S.top - S.base = S.stacksize) /栈满，追加存储空间 S.base = (ElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof (ElemType); if (!S.base) exit (OVERFLOW); /存储分配失败 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; T(n) = O(1) return OK;出栈操作出栈操作Pop_SqPop_Sq算法设计算法设计参数：顺序栈参数：顺序栈&S&S、删除的栈顶元素、删除的栈顶元素&e&e分析：在栈非空时，删除栈顶元素分析：在栈非空时，删除栈顶元素Status Pop (SqStack &S, SElemType &e) / 若栈不空，则删除S的栈顶元素， / 用e返回其值，并返回OK； / 否则返回ERROR if (S.top = S.base) return ERROR; e = *-S.top; /* /* 注意与注意与GetTopGetTop( )( )的区别的区别* */ / return OK; T(n) = O(1) 在一个程序中同时使用两个栈在一个程序中同时使用两个栈0M-1栈1底栈1顶栈2底栈2顶栈顶指针链栈链栈a1an注意注意: 链栈中链栈中指针的方向指针的方向an-1与链表类似，只是链表的头指与链表类似，只是链表的头指针即为栈顶指针。因其操作均针即为栈顶指针。因其操作均在栈顶进行，故可以不引入头在栈顶进行，故可以不引入头结点。结点。 用指针来实现的栈叫链栈。栈用指针来实现的栈叫链栈。栈的容量事先不能估计时采用这的容量事先不能估计时采用这种存储结构。种存储结构。无栈满问题无栈满问题(除非分配不出除非分配不出内存内存), 空间可扩充空间可扩充栈顶栈顶-链表的表头链表的表头3.3 栈的应用举例栈的应用举例例一、例一、 数制转换数制转换例二、例二、 括号匹配的检验括号匹配的检验例三、例三、 行编辑程序问题行编辑程序问题例四、例四、 迷宫求解迷宫求解例五、例五、 表达式求值表达式求值例六、例六、 实现递归实现递归 例一、例一、 数制转换数制转换 算法基于原理： N = (N div d)d + N mod d 多进制输出：多进制输出：例例 把十进制数把十进制数159转换成八进制数转换成八进制数(159)10=(237)815981982802 3 7 余 7余 3余 2toptop7top73top732 1 1）将）将N%dN%d的结果保存，的结果保存，2 2）N=N/dN=N/d，3 3）若）若N=0N=0结束，否则继续结束，否则继续1 1）。）。保存的余数从先到后依次表示转换后的保存的余数从先到后依次表示转换后的d d 进进制数的低位到高位，而输出是由高位到低位制数的低位到高位，而输出是由高位到低位的，因此必须定义先进后出的线性表的，因此必须定义先进后出的线性表栈栈来保存；当全部的余数求出后，通过逐个出来保存；当全部的余数求出后，通过逐个出栈输出栈输出d d进制数。进制数。 例如：例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2计计算算顺顺序序输输出出顺顺序序void conversion () InitStack(S); scanf (%d,N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion例二、例二、 括号匹配的检验括号匹配的检验假设在表达式中（）或（ ）等为正确的格式，（ ）或（ ）或 （）)均为不正确的格式。则 检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。 从左至右扫描表达式，遇左括号入栈，从左至右扫描表达式，遇左括号入栈，遇右括号与栈顶元素比较：若左右括号遇右括号与栈顶元素比较：若左右括号匹配，则继续扫描；否则说明不匹配，匹配，则继续扫描；否则说明不匹配，结束。在上述操作中，若栈为空，或扫结束。在上述操作中，若栈为空，或扫描结束后栈不为空，均说明不匹配。描结束后栈不为空，均说明不匹配。分析可能出现的不匹配不匹配的情况:到来的右括弧并非是所“期待”的；例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8到来的是“不速之客”；直到结束，也没有到来所“期待”的括弧。算法的设计思想：算法的设计思想：1）凡出现左括弧左括弧，则进栈进栈；2）凡出现右括弧右括弧，首先检查栈是否空 若栈空栈空，则表明该“右括弧右括弧”多余多余， 否则和栈顶元素和栈顶元素比较， 若相匹配相匹配，则“左括弧出栈左括弧出栈” ” ， 否则表明不匹配不匹配。3）表达式表达式检验结束时结束时， 若栈空栈空，则表明表达式中匹配正确匹配正确， 否则表明“左括弧左括弧”有余有余。Status matching(string& exp) int state = 1; while (i=Length(exp) & state) switch of expi case 左括弧:Push(S,expi); i+; break; case”)”: if(NOT StackEmpty(S)&GetTop(S)=“(“ Pop(S,e); ii+; else state = 0; break; if (StackEmpty(S)&state) return OK; .例三、行编辑程序问题例三、行编辑程序问题如何实现？如何实现？“每接受一个字符即存入存储器每接受一个字符即存入存储器” ? 并不恰当！处理规则：遇处理规则：遇#退一格；遇退一格；遇退一行退一行算法思想：引入栈，保存终端输入的一行字符（逐行处理）；算法思想：引入栈，保存终端输入的一行字符（逐行处理）；遇遇#退一格退一格出栈一次出栈一次遇遇退一行退一行清栈清栈步骤：步骤：1 1）初始化栈）初始化栈S S2 2）读入字符）读入字符chch3 3）chch!=EOF!=EOF3.1) 3.1) chch!=EOF & !=EOF & chch!=n!=n 3.1.1 3.1.1）chch为为#：Pop(SPop(S, c), , c), 转转3.1.4)3.1.4)3.1.23.1.2）chch为为： ClearStackClearStack (S) , (S) , 转转3.1.4)3.1.4)3.1.33.1.3）chch为其他：为其他： Push (S, Push (S, chch) , ) , 转转3.1.4)3.1.4)3.1.43.1.4）再读入字符）再读入字符chch，继续，继续3.1)3.1)3.2) 3.2) 处理完一行，清空栈处理完一行，清空栈3.3) 3.3) 如如chch!=EOF!=EOF，读入字符，读入字符chch，继续，继续3)3) 设立一个输入缓冲区，用以接受用设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户输入的一行字符，然后逐行存入用户数据区，并假设户数据区，并假设“#”为退格符，为退格符，“”为退行符。为退行符。 在用户输入一行的过程中，允许在用户输入一行的过程中，允许 用户输入出差错，并在发现有误时用户输入出差错，并在发现有误时 可以及时更正。可以及时更正。合理的作法是：假设从终端接受了这样两行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);则实际有效的是下列两行： while (*s) putchar(*s+); while (ch != EOF & ch != n) switch (ch) case # : Pop(S, c); break; case : ClearStack(S); break;/ 重置S为空栈 default : Push(S, ch); break; ch = getchar(); / 从终端接收下一个字符 ClearStack(S); / 重置S为空栈if (ch != EOF) ch = get char();while (ch != EOF) /EOF为全文结束符将从栈底到栈顶的字符传送至调用过程的数据区；例四、例四、 迷宫求解迷宫求解通常用的是“穷举求解穷举求解”的方法求迷宫路径算法的基本思想基本思想是：若当前位置若当前位置“可通可通”，则纳入路，则纳入路径，继续前进径，继续前进;若当前位置若当前位置“不可通不可通”，则后退，则后退，换方向继续探索换方向继续探索;若四周若四周“均无通路均无通路”，则将当前，则将当前位置从路径中删除出去。位置从路径中删除出去。问题：找从问题：找从“入口入口”到到“出口出口”的路径（所经过的路径（所经过的通道方块）的通道方块）分析：分析：方块的表示方块的表示坐标，当前的状态（障碍、未走坐标，当前的状态（障碍、未走的通路、已走的通路）；的通路、已走的通路）；已走的路径：已走的路径：路径中各方块的位置及在路径中的序号路径中各方块的位置及在路径中的序号; ;从各方块出发已探索的方向，注意不能重复（可从各方块出发已探索的方向，注意不能重复（可约定按东、南、西、北的方向顺次探索）；约定按东、南、西、北的方向顺次探索）；从当前方块无路可走时，将已走路径回退一个方从当前方块无路可走时，将已走路径回退一个方块，继续探索其他未走的方向块，继续探索其他未走的方向栈栈存储已走的通道块存储已走的通道块设定当前位置的初值为入口位置； do 若当前位置可通若当前位置可通， 则则将当前位置插入栈顶插入栈顶； 若若该位置是出口位置，则则算法结束； 否则切换否则切换当前位置的东邻方块为 新的当前位置； 否则否则 while (栈不空）栈不空）；求迷宫中一条从入口到出口的路径的算法：求迷宫中一条从入口到出口的路径的算法： 若若栈不空且栈顶位置尚有其他方向未被探索栈不空且栈顶位置尚有其他方向未被探索，则则设定新的当前位置为: 沿顺时针方向旋转 找到的栈顶位置的下一相邻块栈顶位置的下一相邻块；若若栈不空但栈顶位置的四周均不可通栈不空但栈顶位置的四周均不可通，则则删去栈顶位置；/ 从路径中删去该通道块 若若栈不空，则则重新测试新的栈顶位置， 直至直至找到一个可通的相邻块或出栈至栈空；若若栈空栈空，则则表明迷宫没有通路。 限于二元运算符的表达式定义: 表达式表达式 := (操作数操作数) + (运算符运算符) + (操作数操作数) 操作数操作数 := 简单变量简单变量 | 表达式表达式 简单变量简单变量 : = 标识符标识符 | 无符号整数无符号整数例五、例五、 表达式求值表达式求值只包含只包含+, -, *, / +, -, *, / 四个双目运算符，且算符本四个双目运算符，且算符本身不具有二义性；身不具有二义性；三个运算规则三个运算规则运算符优先关系（考虑算符本身运算符优先关系（考虑算符本身的优先级和结合性）；的优先级和结合性）；只有只有 (=)(=)，#=#=#；假设输入的是一个合法的表达式。假设输入的是一个合法的表达式。问题描述问题描述引入引入OPTROPTR和和OPNDOPND两个栈两个栈初始：初始：OPTROPTR有一个元素有一个元素#，OPNDOPND为空为空读入一字符读入一字符c cc=#c=#：return(GetTop(OPNDreturn(GetTop(OPND)c c非运算符：非运算符：Push(OPND,cPush(OPND,c) )c c运算符：运算符：t=t=GetTop(OPTRGetTop(OPTR) )，比较，比较t t和和c c的优先关系的优先关系tctctc：Pop(OPTRPop(OPTR, theta); , theta); Pop(OPNDPop(OPND, b); , b); Pop(OPNDPop(OPND, a);, a); x= x=Operate(aOperate(a, theta, b); , theta, b); Push(OPNDPush(OPND, x);, x);继续读入字符处理。继续读入字符处理。 算法思想算法思想 表达式的三种标识方法：表达式的三种标识方法：设设 Exp = S1 + OP + S2则称则称 OP + S1 + S2 为前缀表示法前缀表示法(波兰式波兰式) S1 + OP + S2 为中缀表示法中缀表示法 S1 + S2 + OP 为后缀表示法后缀表示法(逆波兰式逆波兰式) 例如: Exp = a b + (c d / e) f前缀式: + a b c / d e f中缀式: a b + c d / e f后缀式: a b c d e / f + 结论结论:1）操作数之间的相对次序不变）操作数之间的相对次序不变;2）运算符的相对次序不同）运算符的相对次序不同;3）中缀式丢失了括弧信息， 致使运算的次序不确定;4)前缀式的运算规则前缀式的运算规则为:连续出现的两个操作数和在它们连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一之前且紧靠它们的运算符构成一个最小表达式个最小表达式; 5)后缀式的运算规则后缀式的运算规则为: 运算符在式中出现的顺序恰为运算符在式中出现的顺序恰为 表达式的运算顺序表达式的运算顺序; 每个运算符和在它之前出现每个运算符和在它之前出现 且且 紧靠它的两个操作数构成一个最小紧靠它的两个操作数构成一个最小 表达式。表达式。运算符：运算符： * / * + - （ ） 界限符：界限符： ；以表达式以表达式 A*B + CD 为例说明利用栈的为例说明利用栈的求值过程。求值过程。 优先级：优先级： 4 3 3 2 2 1 1 0操作数变量：操作数变量：A B C DA*B + C/D;top2top1初态;(a)OSNSBA*;(b)NSOST1;(c)T1=A*BNSOSDCT1/+;(d)NSOS(g)NSOST2=C/DT2T1+;(e)NSOST3;(f)T3=T2+T1NSOS思思想想：从从左左到到右右扫扫描描表表达达式式，若若当当前前读读入入的的是是操操作作数数，则则进进操操作数（作数（NS）栈，若读入的符号是运算符，应进行判断：栈，若读入的符号是运算符，应进行判断：1.若若是是“（”，进进运运算算符符栈栈；若若是是“）”，当当运运算算符符栈栈顶顶是是“（”，则则弹弹出出栈栈顶顶元元素素，继继续续扫扫描描下下一一符符号号。否否则则当当前前读读入入符符号号暂暂不不处处理理，从从操操作作数数栈栈弹弹出出两两个个操操作作数数，从从运运算算符符栈栈弹弹出出一一个个运运算算符符，生生成成运运算算指指令令，结结果果送送入入操操作作数数栈栈，继继续续处处理当前读入符号。理当前读入符号。2.2.若若读读入入的的运运算算符符的的优优先先级级大大于于运运算算符符栈栈顶顶的的优优先先级级，则则进进运运算算符符栈栈，继继续续扫扫描描下下一一符符号号；否否则则从从操操作作数数栈栈顶顶弹弹出出两两个个操操作作数数，从从运运算算符符栈栈弹弹出出一一个个运运算算符符，生生成成运运算算指指令令，把把结结果送入操作数栈。继续处理刚才读入的符号。果送入操作数栈。继续处理刚才读入的符号。3.3. 若若读读入入的的是是“；”，且且运运算算符符栈栈顶顶的的符符号号也也是是“；”时时，则表达式处理结束。从操作数栈弹出表达式结果。则表达式处理结束。从操作数栈弹出表达式结果。例例 计算计算 2+4-3*6操作数运算符24+操作数运算符6-操作数运算符6-36*操作数运算符6-18操作数运算符12n表达式的不同表示之间的相互转换表达式的不同表示之间的相互转换n逆波兰式逆波兰式波兰式波兰式n如：如：abcd+*e*+ +a*b+cden共同点共同点n运算对象的次序一致运算对象的次序一致n不需要括号区分优先级和结合性不需要括号区分优先级和结合性n某算符在所有算符中的次序决定了它的计算次序某算符在所有算符中的次序决定了它的计算次序n转换的思想转换的思想n参照逆波兰式的计算过程，将计算转换为待计算的算符和运算对参照逆波兰式的计算过程，将计算转换为待计算的算符和运算对象的串的拼接象的串的拼接n逆波兰式逆波兰式中缀表达式中缀表达式n如：如： abcd+*e*+ a+b*(c+d)*e 练习练习1：A+B*C-D/E；top1初态;(a)top2OSNSBA+;(b)OS*C NST1=B*CA+;(c)NSOST1T2;(d)NSOST2=A+T1EDT2/-;(e)NSOST3T2-;(f)T3=D/ENSOS(g)NSOST4；T4=T2-T3(h) 练习：练习：A-B/C+D*E；top2初态;(a)OSNSBA;(b)OS/C NSA;(c)NSOST1T1=B/CA;(d)NSOST1 DE+*T2T1A+;(e)NSOST2=D*ET2T3+;(f)T3=A-T1NSOST4=T2+T3(g)NSOST4；(h)优先级相同时，应先处理栈中数据错在错在哪？哪？ 练习练习2：若进栈序列为：若进栈序列为3，5，7，9，进栈过程中可以出栈，则，进栈过程中可以出栈，则不可能的一个出栈次序是（不可能的一个出栈次序是（ ）。）。 (a) 7,5,3,9 (b) 9,7,5,3 (c) 7,5,9,3 (d) 9,5,7,3d练习练习3 3：用一维数组设计栈，初态是栈空，用一维数组设计栈，初态是栈空，top=0top=0。现有输入。现有输入序列是序列是 a a、b b、c c、d d，经过，经过 pushpush、pushpush、poppop、pushpush、poppop、pushpush操作后，输出序列是操作后，输出序列是（ ），栈），栈顶指针顶指针是（是（ ）b、c2如何从后缀式求值？如何从后缀式求值？先找运算符，先找运算符， 再找操作数再找操作数例如：例如： a b c d e / f +a bd/ec-d/e(c-d/e) fl如何从原表达式求得后缀式？如何从原表达式求得后缀式？ 每个运算符的运算次序要由它之后它之后的一个运算符的一个运算符来定，在后缀式中，优先数高的运算符领先于优先数低的运算符。分析 “原表达式” 和 “后缀式”中的运算符:原表达式: a + b c d / e f 后缀式: a b c + d e / f 从原表达式求得后缀式的规律为：从原表达式求得后缀式的规律为：1) 设立操作数栈；栈；2) 设表达式的结束符为“#”， 予设运算符栈的栈底为“#”；3) 若当前字符是操作数， 则直接发送给后缀式。4) 若当前运算符的优先数高于栈顶运算符，则进栈；5) 否则，退出栈顶运算符发送给后缀式； 6) “(” 对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。从原表达式求得后缀式的规律为：从原表达式求得后缀式的规律为：void transform(char suffix , char exp ) InitStack(S); Push(S, #); p = exp; ch = *p; while (!StackEmpty(S) if (!IN(ch, OP) Pass( Suffix, ch); else if ( ch!= # ) p+; ch = *p; else Pop(S, ch); Pass(Suffix, ch); / while / CrtExptree switch (ch) case ( : Push(S, ch); break; case ) : Pop(S, c); while (c!= ( ) Pass( Suffix, c); Pop(S, c) break; defult : while(Gettop(S, c) & ( precede(c,ch) Pass( Suffix, c); Pop(S, c); if ( ch!= # ) Push( S, ch); break; / switch 1、栈（、栈（stack）定义定义 栈是只能在一端插入和删除的线性表栈是只能在一端插入和删除的线性表特性：后进先出（特性：后进先出（LIFOLIFO）或或 先进后出（先进后出（FILOFILO）设栈设栈s=s=（a a1 1，a a2 2，. . . ,. . . ,a ai i，. . . . . . ，a an n），其中其中a a1 1是栈底元素，是栈底元素， a an n是栈顶元素。是栈顶元素。栈顶（栈顶（top)top)：允许插入和删除的一端；允许插入和删除的一端； 约定约定toptop始终指向新数据元素将存放的位置。始终指向新数据元素将存放的位置。栈底（栈底（bottom):bottom):不允许插入和删除的一端。不允许插入和删除的一端。 a1 a2 . an进栈进栈出栈出栈栈顶栈顶栈底栈底内容回顾内容回顾2、栈的类型定义栈的类型定义 ADT Stack 数据对象数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作：基本操作： ADT Stack内容回顾内容回顾InitStack(&S) DestroyStack(&S)StackLength(S) StackEmpty(S)GetTop(S, &e) ClearStack(&S)Push(&S, e) Pop(&S, &e)StackTravers(S, visit()3 3、栈类型的实现栈类型的实现顺序栈顺序栈链栈链栈内容回顾内容回顾 a1 a2 top顺序栈顺序栈一维数组一维数组SMSM，即用顺，即用顺序存储结构表示的栈序存储结构表示的栈顺序栈用一组连续的存储单元存放自顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维栈底到栈顶的数据元素，一般用一维数组表示，设置一个简单变量数组表示，设置一个简单变量top指指示栈顶位置，示栈顶位置，称为称为栈顶指针栈顶指针，它始终它始终指向待插入元素的位置。指向待插入元素的位置。栈顶指针链栈链栈a1an注意注意: 链栈中链栈中指针的方向指针的方向an-1与链表类似，只是链表的头指与链表类似，只是链表的头指针即为栈顶指针。因其操作均针即为栈顶指针。因其操作均在栈顶进行，故可以不引入头在栈顶进行，故可以不引入头结点。结点。 用指针来实现的栈叫链栈。栈用指针来实现的栈叫链栈。栈的容量事先不能估计时采用这的容量事先不能估计时采用这种存储结构。种存储结构。无栈满问题无栈满问题(除非分配不出除非分配不出内存内存), 空间可扩充空间可扩充栈顶栈顶-链表的表头链表的表头4 4、栈的应用举例、栈的应用举例例一、例一、 数制转换数制转换例二、例二、 括号匹配的检验括号匹配的检验例三、例三、 行编辑程序问题行编辑程序问题例四、例四、 迷宫求解迷宫求解例五、例五、 表达式求值表达式求值例六、例六、 实现递归实现递归例六、实现递归例六、实现递归直接直接或或间接间接地调用自身的函数地调用自身的函数，称为递归函数。递归表现为：在该函数的所有可能执行路径中，存在一条由于调用自身或其它函数所导致的环路路径；为确保函数最终在有限的时间内执行完毕，必须在环路中存在一个出口，即当某种条件成立时，不必执行环路，而直接执行一条通向结束的非环路线。开始开始结束结束形形 成成了了 环环递归定义递归定义直接调用直接调用int f(int x) int y,z; . z=f(x); return (2*z); f 函数调用 f函数int f1(int x) int y,z; . z=f2( y); return (2*z); int f2(int t) int a,c; . c=f1(a); return (3+c); 间接调用间接调用递归应用的特点递归应用的特点对于一个问题，当问题规模很大时，往往难于直接求解，此时： 将大问题分解成若干小问题 考虑如何利用这些小问题的解构成大问题的解这种分解、合成的方法就是递归求解中的递归方法；另外，递归应用要注意避免陷入死循环，递归必须有出口，即要确立递归的结束条件，给出此时的直接求解方法。 以求4的阶乘为例：4！=4*3！3! =3* 2!2! =2* 1!1! =1*0！4! =4*3*2*12! =2*13! =3*2*1下下推推回回代代例如：写一函数求例如：写一函数求n! 1 (n=0)n! = n * (n-1)！ (n1)1! =1*10! =1 float fac ( int n) float f; if(n0) printf(“n0,data error!n”); else if(n=0) f=1; else f=fac(n-1)* n ; return f; 例如：写一函数求例如：写一函数求n! 1 (n=0)n! = n(n-1)！ (n 1)以求4的阶乘为例：fac(4)=4*fac(3)fac(3)=3*fac(2)fac(2)=2*fac(1)fac(1)=1*fac(0)fac(4) =4*3*2*1fac(2) =2*1fac(3) =3*2*1下下推推回回代代fac(1) =1*1fac(0)=1利用栈实现递归调用利用栈实现递归调用主程序主程序(1)输出输出f(4); 4 f (4);（1）n=4top(2) s=4*f(3)n3 f (3);（2）n=3 （1）n=4 top(3) s=3*f(2)n2 f (2);（3）n=2 （2）n=3 （1）n=4 top(4)s=2*f(1)n1（4）n=1 （3）n=2 （2）n=3 （1）n=4 tops s=3*2*1;(2) 3(1) 4top s=2*1(3) 2(2) 3(1) 4top s=4*3*2*1 (1 ) 4top返回返回(3) 2(2) 3(1) 4top(4) 1结束结束输出输出24将所有的实在参数、返回地址等信息传递给被调用函数保存；为被调用函数的局部变量分配存储区；将控制转移到被调用函数的入口。 当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：递归的实现递归的实现 保存被调函数的计算结果；释放被调函数的数据区；依照被调函数保存的返回地址将控制转移到调用函数。从被调用函数返回返回调用函数之前之前，应该完成下列三项任务：多个函数嵌套调用的规则是：此时的内存管理实行“栈式管理栈式管理”后调用先返回后调用先返回 ！例如：void main( ) void a( ) void b( ) a( ); b( ); /main / a / bmain的数据区函数a的数据区函数b的数据区 递归工作栈：递归工作栈：递归过程执行过程中占用的 数据区。递归工作记录：递归工作记录：每一层的递归参数合成 一个记录。当前活动记录：当前活动记录：栈顶记录指示当前层的 执行情况。当前环境指针：当前环境指针：递归工作栈的栈顶指针。递归函数执行的过程可视为同一函数同一函数进行嵌套调用：例例 递归的执行情况分析递归的执行情况分析 void print(int w) int i; if ( w!=0) print(w-1); for(i=1;icn1:hanoi(n-1, a, c, b)a-chanoi(n-1, b, a, c)注意用递归调用的结果，用递归调用的结果，不关注该结果如何不关注该结果如何获得的细节获得的细节执行情况：执行情况：递归工作栈保存内容：形参递归工作栈保存内容：形参n,x,y,z和返回地址和返回地址返回地址用行编号表示返回地址用行编号表示n x y z 返回地址 解决方法：解决方法：n=1时，直接把圆盘从时，直接把圆盘从A移到移到Cn1时，先把上面时，先把上面n-1个圆盘从个圆盘从A移到移到B,然后将然后将n号盘从号盘从A移到移到C,再将再将n-1个盘从个盘从B移到移到C。即即把求把求解解n个圆盘的个圆盘的Hanoi问题转化为求解问题转化为求解n-1个圆盘个圆盘的的Hanoi问题问题，依次类推，直至转化成只有一，依次类推，直至转化成只有一个圆盘的个圆盘的Hanoi问题问题void hanoi (int n, char x, char y, char z) / 将塔座x上按直径由小到大且至上而下编号为1至n/ 的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1 if (n=1)2 move(x, 1, z); / 将编号为的圆盘从x移到z3 else 4 hanoi(n-1, x, z, y); / 将x上编号为至n-1的 /圆盘移到y, z作辅助塔5 move(x, n, z); / 将编号为n的圆盘从x移到z6 hanoi(n-1, y, x, z); / 将y上编号为至n-1的 /圆盘移到z, x作辅助塔7 8 8 3 a b c返址 n x y z5 2 a c b5 1 a b c7 1 c a bvoid hanoi (int n, char x, char y, char z) 1 if (n=1)2 move(x, 1, z); 3 else 4 hanoi(n-1, x, z, y); 5 move(x, n, z); 6 hanoi(n-1, y, x, z); 7 8 回文游戏：顺读与逆读字符串一样（不含空格）回文游戏：顺读与逆读字符串一样（不含空格）dadtop1.读入字符串读入字符串2.去掉空格（原串）去掉空格（原串）3.压入栈压入栈4.原串字符与出栈字符依次比较原串字符与出栈字符依次比较 若不等，非回文若不等，非回文 若直到栈空都相等，回文若直到栈空都相等，回文字符串：“madam im adam”雾锁山头山锁雾，天连水尾水连天 蜜蜂酿蜂蜜 黄山落叶松叶落山黄 递归与回溯递归与回溯N N皇后问题皇后问题 在n行n列的国际象棋棋盘上，若两个皇后位于同一行、同一列或同一对角线上，则称它们为互相攻击。n皇后问题是指： 找到这 n 个皇后的互不攻击的布局1#主对角线主对角线0 1 2 3 0123k = i+jk = n+i- -j- -10#主对角线主对角线2#主对角线主对角线4#主对角线主对角线6#主对角线主对角线3#主对角线主对角线5#主对角线主对角线1#次对角线次对角线3#次对角线次对角线0#次对角线次对角线2#次对角线次对角线4#次对角线次对角线6#次对角线次对角线5#次对角线次对角线基本思路基本思路依次为每一行确定该行皇后的合法位置依次为每一行确定该行皇后的合法位置安放第安放第 i 行皇后时，需要在列的方向从行皇后时，需要在列的方向从 0 到到 n-1 试探试探 ( j = 0, , n-1 )在第在第 j 列安放一个皇后列安放一个皇后如果在如果在列、主对角线、次对角线列、主对角线、次对角线方向有其它皇后，方向有其它皇后，则出现攻击，撤消在第则出现攻击，撤消在第 j 列安放的皇后：列安放的皇后：如果没有出现攻击，在第如果没有出现攻击，在第 j 列安放的皇后不动列安放的皇后不动递归安放第递归安放第 i+1行皇后行皇后如果第如果第 i 行不能安放皇后，则回溯到第行不能安放皇后，则回溯到第 i-1 行，从下行，从下一个列一个列(j+1)继续试探继续试探数据结构设计数据结构设计标识标识每一列每一列是否已经安放了皇后是否已经安放了皇后线性表，表长为线性表，表长为N N标识各条标识各条主对角线主对角线是否已经安放了皇后是否已经安放了皇后 线性表，表长为线性表，表长为2N-12N-1标识各条标识各条次对角线次对角线是否已经安放了皇后是否已经安放了皇后 线性表，表长为线性表，表长为2N-12N-1记录当前各行的皇后在第几列记录当前各行的皇后在第几列布局状况布局状况 线性表，表长为线性表，表长为N N存储结构的选择存储结构的选择表长固定，有随机存取的要求表长固定，有随机存取的要求顺序表顺序表存储结构存储结构标识标识每一列每一列是否已经安放了皇后是否已经安放了皇后数组数组colcol，表长为表长为N N标识各条标识各条主对角线主对角线是否已经安放了皇后是否已经安放了皇后 数组数组mdmd，表长为表长为2N-12N-1标识各条标识各条次对角线次对角线是否已经安放了皇后是否已经安放了皇后 数组数组sdsd，表长为表长为2N-12N-1记录当前各行的皇后在第几列记录当前各行的皇后在第几列布局状况布局状况 数组数组q q，表长为表长为N N算法算法void Queen( int i, int n ) for ( int j = 0; j n; j+ ) if ( 第第 i 行第行第 j 列没有攻击列没有攻击 ) 在在第第 i 行第行第 j 列安放皇后列安放皇后; if ( i = n-1 ) 输出一个布局输出一个布局; else Queen ( i+1, n ); 撤消撤消第第 i 行第行第 j 列的皇后列的皇后; !colj & !mdn+i- -j- -1 & !sdi+jcolj= 1;mdn+i- -j- -1=1; sdi+j=1;qi = j;输出输出qcolj= 0;mdn+i- -j- -1=0; sdi+j=0;qi = 0;练习题：1、请写出下面程序的运行结果。#include “stdlib.h”void p(int w) int i; if (w!=0)1 printf(“%3d”,w)2 p(w-1);3 p(w-1); main print(3);1 2 3运行结果：运行结果：32112112 1 3运行结果：运行结果：12131212、编写一个程序计算2阶Fibonacci数列： 0 n=0Fib(n)= 1 n=1 Fib(n-1)+Fib(n-2) 其它 ADT Queue 数据对象：数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系：数据关系： R1 | ai-1, ai D, i=2,.,n 约定其中a1 端为队列头队列头， an 端为队列尾队列尾基本操作：基本操作：3.4 队列的类型定义队列的类型定义 ADT Queue定义：队列是限定只能在表的一端进行插入，定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表在表的另一端进行删除的线性表队尾队尾(rear)允许插入的一端允许插入的一端队头队头(front)允许删除的一端允许删除的一端队列特点：先进先出队列特点：先进先出(FIFO)队头队头Q.front入队入队 出队出队a1a2a3 anQ.rear队尾队尾队列的基本操作：队列的基本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQueue(&Q, e)QueueTravers(Q, visit()InitQueue(&Q) 操作结果：操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：初始条件：队列Q已存在。 操作结果：操作结果：队列Q被销毁， 不再存在。 QueueEmpty(Q)初始条件：初始条件：队列Q已存在。 操作结果：操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。 QueueLength(Q) 初始条件：初始条件：队列Q已存在。 操作结果：操作结果：返回Q的元素个数，即队列的长度。 GetHead(Q, &e) 初始条件：初始条件：Q为非空队列。 操作结果：操作结果：用e返回Q的队头元素。a1a2an ClearQueue(&Q)初始条件：初始条件：队列Q已存在。 操作结果：操作结果：将Q清为空队列。 EnQueue(&Q, e) 初始条件：初始条件：队列Q已存在。 操作结果：操作结果：插入元素e为Q的新的队尾元素。a1a2ane DeQueue(&Q, &e) 初始条件：初始条件：Q为非空队列。 操作结果：操作结果：删除Q的队头元素，并用e返回其值。a1a2an 线性队列线性队列实现：用一维数组实现实现：用一维数组实现sqMfront=-1rear=-1123450队空123450frontJ1,J1,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素前一位置初值front=rear=-1空队列条件：front=rear入队列：sq+rear=x;出队列：x=sq+front;rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfront存在问题存在问题设数组维数为设数组维数为M，则：则：当当front=-1,rear=M-1时，再有元素入队发生溢出时，再有元素入队发生溢出真溢出真溢出当当front -1,rear=M-1时，再有元素入队发生溢出时，再有元素入队发生溢出假溢出假溢出解决方案解决方案队首固定，每次出队剩余元素向下移动队首固定，每次出队剩余元素向下移动浪费时间浪费时间循环队列循环队列3.5 队列类型的实现队列类型的实现链队列链队列链式映象循环队列循环队列顺序映象 typedef struct QNode / 结点类型结点类型 QElemType data; struct QNode *next; QNode, *QueuePtr;链队列链队列链式映象typedef struct / 链队列类型链队列类型 QueuePtr front; / 队头指针队头指针 QueuePtr rear; / 队尾指针队尾指针 LinkQueue;a1anQ.frontQ.rearQ.frontQ.rear空队列空队列头结点 .front队头队尾rear设队首、队尾指针front和rear,front指向头结点，rear指向队尾frontrearx入队xfrontreary入队xyfrontrearx出队xyfront rear空队front reary出队入队算法入队算法JD *ldcr(JD *rear,int x) JD *p; p=(JD *)malloc(sizeof(JD); p-data=x; p-next=NULL; rear-next=p; return(p);出队算法出队算法int ldsc(JD *front,JD *rear) JD *s; int x; if(front=rear) return(-1); s=front-next; front-next=s-next; if(s-next=NULL) rear=front; x=s-data; free(s); return(x); Status InitQueue (LinkQueue &Q) / 构造一个空队列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if (!Q.front) exit (OVERFLOW); /存储分配失败 Q.front-next = NULL; return OK; Status EnQueue (LinkQueue &Q, QElemType e) / 插入元素e为Q的新的队尾元素 p = (QueuePtr) malloc (sizeof (QNode); if (!p) exit (OVERFLOW); /存储分配失败 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK; Status DeQueue (LinkQueue &Q, QElemType &e) / 若队列不空，则删除Q的队头元素， /用 e 返回其值，并返回OK；否则返回ERROR if (Q.front = Q.rear) return ERROR; p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear = p) Q.rear = Q.front; free (p); return OK;循环队列循环队列基本思想：把队列基本思想：把队列设想成环形设想成环形，让，让sq0接在接在sqM-1之后，若之后，若rear+1=M,则令则令rear=0;0M-11frontrear.实现：利用实现：利用“模模”运算运算入队：入队： rear=(rear+1)%M; sqrear=x;出队：出队： front=(front+1)%M; x=sqfront;队满、队空判定条件队满、队空判定条件#define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base; / 动态分配存储空间 int front; / 头指针，若队列不空， / 指向队列头元素 int rear; / 尾指针，若队列不空，指向 / 队列尾元素 的下一个位置 SqQueue;循环队列循环队列顺序映象012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空：队空：front=rear队满：队满：front=rear如何区分队空和队满？如何区分队空和队满？区分队空和队满的方法区分队空和队满的方法设标志位设标志位(上次的更新动作上次的更新动作)：0-创建创建/删除，删除，1-插入插入引入队列长度引入队列长度少用一个元素空间：少用一个元素空间：插入前判断插入前判断 Q.front=(Q.rear+1)%MAXQSIZE01723456Q.frontQ.rear01723456Q.frontQ.reara1a2a3a4a5a6a7有维护有维护的代价的代价难点难点连续的存储单元的上下界连续的存储单元的上下界：d1,d2初始化空队：初始化空队：Q.front = Q.rear = d1;队空：队空： Q.front=Q.rear队满队满： Q.front=(Q.rear-d1+1)%(d2-d1+1)+d1入队入队： 前提：队列不满前提：队列不满 Q.baseQ.rear = e; Q.rear = (Q.rear-d1+1)%(d2-d1+1)+d1;出队出队：前提：队列不空前提：队列不空 e = Q.baseQ.front; Q.front = (Q. front-d1+1)%(d2-d1+1)+d1入队算法：入队算法：void en_cycque(int sq, int front, int rear, int x) if(rear+1)%M)=front) printf(overflow); else rear=(rear+1)%M; sqrear=x; 出队算法：出队算法：int dl_cycque(int sq, int front, int rear, int *q) if(front=rear) return(0); else front=(front+1)%M; *q=sqfront; return(1); Status InitQueue (SqQueue &Q) / 构造一个空队列Q Q.base = (ElemType *) malloc (MAXQSIZE *sizeof (ElemType); if (!Q.base) exit (OVERFLOW); / 存储分配失败 Q.front = Q.rear = 0; return OK; Status EnQueue (SqQueue &Q, ElemType e) / 插入元素e为Q的新的队尾元素 if (Q.rear+1) % MAXQSIZE = Q.front) return ERROR; /队列满 Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK; Status DeQueue (SqQueue &Q, ElemType &e) / 若队列不空，则删除Q的队头元素， / 用e返回其值，并返回OK; 否则返回ERROR if (Q.front = Q.rear) return ERROR; e = Q.baseQ.front; Q.front = (Q.front+1) % MAXQSIZE; return OK; 1. 掌掌握握栈栈和和队队列列类类型型的的特特点点，并并能能在在相相应应的应用问题中正确选用它们。的应用问题中正确选用它们。2. 熟练掌握栈类型的两种实现方法，特别应熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。注意栈满和栈空的条件以及它们的描述方法。3. 熟练掌握循环队列和链队列的基本操作实熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。现算法，特别注意队满和队空的描述方法。 4. 理解递归算法执行过程中栈的状态变化过理解递归算法执行过程中栈的状态变化过程。程。本章学习要点本章学习要点本章小结本章小结 本章主要介绍了如下一些基本概念：本章主要介绍了如下一些基本概念：栈栈：是是一一种种只只允允许许在在一一端端进进行行插插入入和和删删除除的的线线性性表表，它它是是一一种种操操作作受受限限的的线线性性表表。在在表表中中只只允允许许进进行行插插入入和和删删除除的的一一端端称称为为栈栈顶顶（top），另另一一端端称称为为栈栈底底(bottom)。栈栈顶顶元元素素总总是是最最后后入入栈栈的的，因因而而是是最最先先出出栈栈；栈栈底底元元素素总总是是最最先先入入栈栈的的，因因而而也也是是最最后后出出栈栈。因此，栈也被称为因此，栈也被称为“后进先出后进先出”的线性表。的线性表。栈栈的的顺顺序序存存储储结结构构：利利用用一一组组地地址址连连续续的的存存储储单单元元依依次次存存放放自自栈栈底底到到栈栈顶顶的的各各个个数数据据元元素素，称称为为栈栈的的顺顺序序存储结构。存储结构。双向栈双向栈：使两个栈共享一维数组：使两个栈共享一维数组stackMAXNUM，利利用栈的用栈的“栈底位置不变，栈顶位置动态变化栈底位置不变，栈顶位置动态变化”的特性，的特性，将两个栈底分别设为将两个栈底分别设为-1和和MAXNUM，而它们的栈顶都而它们的栈顶都往中间方向延伸的栈称为双向栈。往中间方向延伸的栈称为双向栈。栈的链式存储结构栈的链式存储结构：栈的链式存储结构就是用一组任：栈的链式存储结构就是用一组任意的存储单元（可以是不连续的）存储栈中的数据元意的存储单元（可以是不连续的）存储栈中的数据元素，这种结构的栈简称为链栈。在一个链栈中，栈底素，这种结构的栈简称为链栈。在一个链栈中，栈底就是链表的最后一个结点，而栈顶总是链表的第一个就是链表的最后一个结点，而栈顶总是链表的第一个结点。结点。队列队列：队列（：队列（queue）是一种只允许在一端进行插入是一种只允许在一端进行插入，而在另一端进行删除的线性表，它是一种操作受限，而在另一端进行删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入的一端称为队尾的线性表。在表中只允许进行插入的一端称为队尾（rear），），只允许进行删除的一端称为队头只允许进行删除的一端称为队头(front)。队头元素总是最先进队列的，也总是最先出队列；队队头元素总是最先进队列的，也总是最先出队列；队尾元素总是最后进队列，因而也是最后出队列。因此，尾元素总是最后进队列，因而也是最后出队列。因此，队列也被称为队列也被称为“先进先出先进先出”表。表。队队列列的的顺顺序序存存储储结结构构：利利用用一一组组地地址址连连续续的的存存储储单单元元依依次次存存放放队队列列中中的的数数据据元元素素，称称为为队队列列的的顺顺序序存存储储结构。结构。队队列列的的链链式式存存储储结结构构：队队列列的的链链式式存存储储结结构构就就是是用用一一组组任任意意的的存存储储单单元元（可可以以是是不不连连续续的的）存存储储队队列列中中的的数数据据元元素素，这这种种结结构构的的队队列列称称为为链链队队列列。在在一一个个链链队队列列中中需需设设定定两两个个指指针针(头头指指针针和和尾尾指指针针)分分别别指指向向队队列的头和尾。列的头和尾。 除除上上述述基基本本概概念念以以外外，学学生生还还应应该该了了解解：栈栈的的基基本本操操作作（初初始始化化、栈栈的的非非空空判判断断、入入栈栈、出出栈栈、取取栈栈元元素素、置置栈栈空空操操作作）、栈栈的的顺顺序序存存储储结结构构的的表表示示、栈栈的的链链式式存存储储结结构构的的表表示示、队队列列的的基基本本操操作作（初初始始化化、队队列列非非空空判判断断、入入队队列列、出出队队列列、取取队队头头元元素素、求求队队列列长长度度）、队队列列的的顺顺序序存存储储结结构构、队队列列的的链链式式存存储储结结构构，掌掌握握顺顺序序栈栈（入入栈栈操操作作、出出栈栈操操作作）、链链栈栈（入入栈栈操操作作、出出栈栈操操作作）、顺顺序序队队列列（入入队队列列操操作作、出出队队列操作）、链队列（入队列操作、出队列操作）。列操作）、链队列（入队列操作、出队列操作）。习题习题1假设一个算术表达式中包含圆括弧、方括弧和花括弧三种类型的假设一个算术表达式中包含圆括弧、方括弧和花括弧三种类型的括弧括弧,编写一个判别表达式中括弧是否正确配对的函数编写一个判别表达式中括弧是否正确配对的函数.#define size 100int Correct(char expsize , int len) char ssize; int top=0, i=0,tag=1;while(i0) tag=0; return tag;void main()int len, tag;char expsize=“dsgdsg(wetewteewtwrwer)etewtewtwetwetetwet;len=strlen(exp);tag=Correct(exp, len);if (tag=1) printf(rightn);else printf(wrongn);输出结果：wrong习题习题2设栈S为空，队Q的状态是abcd，其中a为队首元素，d为队尾元素，经过下面两个操作后，队Q的状态是（ ）。（1）删除队Q中的元素，将删除的元素插入栈S，直到队Q为空。（2）依次将栈S中的元素插入队Q，直到栈S为空。 (a) abcd (b) acbd (c) dcba (d) bacddcbafrontreartop队Q栈Sfrontreardcbatop队Q栈Sabcdfrontreartop队Q栈Sc