第3章 栈和队列

1、第第3 3章章 栈和队列栈和队列3.1栈栈3.2 栈栈的应用的应用3.3 队列队列3.4 队列的应用队列的应用3.5 栈与递归栈与递归教学内容教学内容1.1.掌握栈和队列的掌握栈和队列的特点特点，并能在相应的应用问，并能在相应的应用问题中正确选用题中正确选用2.2.熟练掌握栈的熟练掌握栈的两种存储结构两种存储结构的基本操作实现的基本操作实现算法，特别应注意算法，特别应注意栈满和栈空栈满和栈空的条件的条件3.3.熟练掌握熟练掌握循环队列和链队列循环队列和链队列的基本操作实现的基本操作实现算法，特别注意算法，特别注意队满和队空队满和队空的的条件条件4.4.理解理解递归算法递归算法执行过程中栈的状态

2、变化过程执行过程中栈的状态变化过程 教学目标教学目标3.1 3.1 栈栈1. 1. 定义定义用顺序存储结构用顺序存储结构（顺序栈）（顺序栈）或链式存储结或链式存储结构构（链栈）（链栈）存储均可，但顺序栈更常见存储均可，但顺序栈更常见3. 3. 存储结构存储结构与线性表相同，仍为与线性表相同，仍为一对一一对一关系关系2. 2. 逻辑结构逻辑结构只能在只能在表的一端表的一端（表尾表尾）进行插入和删）进行插入和删除运算的除运算的线性表线性表a1a2an栈底栈底栈顶栈顶出栈出栈进栈进栈术语：术语：栈顶、栈底、栈顶、栈底、进栈、出栈、进栈、出栈、空栈空栈只能在只能在栈顶栈顶运算运算后进先出后进先出（LI

3、FOLIFO）或或先进后出先进后出（FILOFILO）4.4.运算规则运算规则基本操作有基本操作有入栈、出栈、读栈顶元素值、入栈、出栈、读栈顶元素值、初始化栈、判断栈空初始化栈、判断栈空等等入栈入栈和和出栈出栈函数最关键，具体实现依顺函数最关键，具体实现依顺序栈或链栈的不同而不同序栈或链栈的不同而不同5.5.实现方式实现方式栈是一种特殊的线性表，它只能在表的一端（栈顶）栈是一种特殊的线性表，它只能在表的一端（栈顶）进行插入和删除运算进行插入和删除运算栈与一般线性表的区别：仅在于栈与一般线性表的区别：仅在于运算规则运算规则不同不同一般线性表一般线性表 逻辑结构：一对一逻辑结构：一对一 存储结构：

4、顺序表、链表存储结构：顺序表、链表 运算规则：随机运算规则：随机、顺序存取顺序存取栈栈逻辑结构：一对一逻辑结构：一对一 存储结构：顺序存储结构：顺序栈栈、链、链栈栈运算规则：运算规则：后进先出后进先出栈与一般线性表的区别栈与一般线性表的区别ADT Stack 数据对象：数据对象：D=ai|aiElemSet, i=1,2,.,n, n=0 数据关系：数据关系： R= |ai,ai+1D, i=1,2,.,n-1 基本操作：基本操作： InitStack(StackType &S) DestroyStack(StackType &S) ClearStack (StackType

5、&S) StackEmpty (StackType S) StackLength(StackType S) Push(StackType &S, ElemType e) Pop(StackType &S, ElemType &e) GetTop(SqStack S) StackTraverse(StackType S)ADT Stack栈的抽象数据类型栈的抽象数据类型1.有有6个元素个元素A、B、C、D、E、F依次进栈，允许依次进栈，允许任何时候出栈，能否得到下列的出栈序列：任何时候出栈，能否得到下列的出栈序列：(1) CDBEFA (2) ABEDFC(3)

6、DCEABF (4) BAEFCD2.有有3个元素个元素a、b、c依次进栈，任何时候都可以依次进栈，任何时候都可以出栈，请写出所有可能的出栈序列。出栈，请写出所有可能的出栈序列。栈操作运算栈操作运算5种种顺序栈的表示顺序栈的表示空栈空栈base = top 是栈空是栈空标志标志stacksize = 4topAbasebasetopABABCtopbasetopbaseABCDbasetop3120top top 指示真正的指示真正的栈顶元素之上栈顶元素之上的地址的地址栈满时的处理方法：栈满时的处理方法：1 1、报错报错, ,返回操作系统。返回操作系统。2 2、分配更大的空间分配更大的空间，作

7、为栈的存储空，作为栈的存储空间间, ,将原栈的内容移入新栈。将原栈的内容移入新栈。#define MAXSIZE 100typedef structSElemType *base;SElemType *top; int stacksize;SqStack;顺序栈的表示顺序栈的表示空栈判断条件：空栈判断条件：base = top 栈满判断条件：栈满判断条件： top = base + stacksizebasetop3120topbaseABCD 构造一个空栈构造一个空栈 步骤：步骤：(1)(1)分配空间并检查空间是否分配空间并检查空间是否分配失败，若失败则返回分配失败，若失败则返回错误错误顺序

8、栈的实现顺序栈的实现-初始化初始化basestacksizetops(2)(2)设置栈顶指针设置栈顶指针 S.top = S.base;(3)(3)设置栈大小设置栈大小void InitStack( SqStack &S ) S.base =new SElemTypeMAXSIZE；if( !S.base ) exit(OVERFLOW);S.top = S.base;S.stacksize = MAXSIZE;顺序栈的实现顺序栈的实现-判断栈是否为空判断栈是否为空bool StackEmpty( SqStack S )if (S.top = S.base) return true;

9、else return false;basetop3120顺序栈的实现顺序栈的实现-求栈的长度求栈的长度int StackLength( SqStack S ) return S.top S.base;basetopABvoid ClearStack( SqStack &S ) S.top = S.base;顺序栈的实现顺序栈的实现-清空清空basetop3120void DestroyStack( SqStack &S ) if( S.base ) delete S.base;S.stacksize = 0;S.base = S.top = NULL; 顺序栈的实现顺序栈的实

10、现-销毁销毁(1)(1)判断是否栈满，若满则重新分配空间判断是否栈满，若满则重新分配空间(2)(2)元素元素e e压入栈顶压入栈顶(3)(3)栈顶指针加栈顶指针加1 1顺序栈的实现顺序栈的实现-进栈进栈void Push( SqStack &S, SElemType e) if ( S.top - S.base= S.stacksize ) / 栈满栈满 S.base = (SElemType *) realloc( S.base, 2*S.stacksize *sizeof(SElemType) ); S.top = S.base+ S.stacksize; S.stacksize

11、= 2*S.stacksize;*S.top+=e;*S.top=e;S.top+;ABCtopbase(1)(1)判断是否栈空，若空则出错判断是否栈空，若空则出错(2)(2)获取栈顶元素获取栈顶元素e e(3)(3)栈顶指针减栈顶指针减1 1顺序栈的实现顺序栈的实现-出栈出栈void Pop( SqStack &S, SElemType &e) if ( S.top = S.base ) / 栈空栈空 cerr“栈已空无数据元素出栈！栈已空无数据元素出栈！”data=e; p-next=S; S=p; pSpSe链栈的实现链栈的实现-进栈进栈void Push(LinkSta

12、ck &S , SElemType e) StackNode *p; p=new StackNode; /生成新结点生成新结点p if (!p) exit(OVERFLOW); p-data=e; p-next=S; S=p; pSe链栈的实现链栈的实现-进栈进栈void Push(LinkStack &S , SElemType e) StackNode *p; p=new StackNode; /生成新结点生成新结点p if (!p) exit(OVERFLOW); p-data=e; p-next=S; S=p; pSeS链栈的实现链栈的实现-进栈进栈void Push(

13、LinkStack &S , SElemType e) StackNode *p; p=new StackNode; /生成新结点生成新结点p if (!p) exit(OVERFLOW); p-data=e; p-next=S; S=p; 链栈的实现链栈的实现-出栈出栈SAe = Avoid Pop (LinkStack &S, SElemType &e) StackNode *p; if (S=NULL) cerr“栈已空无数据元素出栈！栈已空无数据元素出栈！” data; p = S; S = S- next; delete p; SAe = Ap链栈的实现链栈的

14、实现-出栈出栈void Pop (LinkStack &S, SElemType &e) StackNode *p; if (S=NULL) cerr“栈已空无数据元素出栈！栈已空无数据元素出栈！” data; p = S; S = S- next; delete p; SAe = ApS链栈的实现链栈的实现-出栈出栈void Pop (LinkStack &S, SElemType &e) StackNode *p; if (S=NULL) cerr“栈已空无数据元素出栈！栈已空无数据元素出栈！” data; p = S; S = S- next; delet

15、e p; e = AS链栈的实现链栈的实现-出栈出栈void Pop (LinkStack &S, SElemType &e) StackNode *p; if (S=NULL) cerr“栈已空无数据元素出栈！栈已空无数据元素出栈！” data; p = S; S = S- next; delete p; 链栈的实现链栈的实现-取栈顶元素取栈顶元素SElemType GetTop(LinkStack S) if (S!=NULL) / 栈非空栈非空 return S- data;SA3.2 3.2 栈的应用栈的应用例例1 1：数制转换（十转：数制转换（十转N N）用栈暂存余数

16、低位值用栈暂存余数低位值例例2 2：括号匹配的检验括号匹配的检验 用栈暂存左括号用栈暂存左括号例例3 3：表达式求值：表达式求值用栈暂存运算符和操作数用栈暂存运算符和操作数1、数制转换、数制转换 把一个十进制数转换成其他进制数（把一个十进制数转换成其他进制数（29进进制）。制）。1348816882148205 (1348)10 = (2504)8802把余数依次入栈，最后再依次出栈。把余数依次入栈，最后再依次出栈。既可使用顺序栈，也可使用链栈，我们采用顺序栈。既可使用顺序栈，也可使用链栈，我们采用顺序栈。#include #include #define MAXSIZE 100typedef

17、 int SElemType;typedef structSElemType *base;SElemType *top; int stacksize;SqStack;#include “SeqStack.h” void Transform ( long num, int r) / 转换转换num为为r进制数，并输出进制数，并输出 SqStack a; SElemType e; InitStack(a) ; while (num) Push( a , num % r ); / 取余并入栈取余并入栈 num = num / r; / 整除整除 while ( !StackEmpty (a) ) P

18、op(a, e); coute; / 出栈并输出出栈并输出 coutendl; DestroyStack(a); void main() cout“3425的八进制数为的八进制数为: ”; Transform(3425, 8); cout“3425的二进制数为的二进制数为: ”; Transform(3425, 2);2、括号匹配的检验、括号匹配的检验 栈常被用于在计算机语言的编译过程中进行语法检查。如：栈常被用于在计算机语言的编译过程中进行语法检查。如：检查程序中的大括号、方括号、圆括号是否配对。检查程序中的大括号、方括号、圆括号是否配对。如如: ( x + y ) * 8 / (a-b)

19、; ( x + y ) * 8 / a-b) ; ( x + y ) )* 8 / (a-b) ; ( ( x + y ) * 8 / (a-b) ; 顺序扫描表达式，当读入字符为：顺序扫描表达式，当读入字符为： 左括号：进栈；左括号：进栈； 右括号：若栈顶元素与之配对，则出栈，继续读下一个；右括号：若栈顶元素与之配对，则出栈，继续读下一个； 若栈顶元素与之不配对，则配对次序不正确，若栈顶元素与之不配对，则配对次序不正确， 程序终止；程序终止； 若栈空，则若栈空，则 左括号左括号 右括号，程序终止右括号，程序终止;bool Matching() Stack S; char e; int fla

20、g=1; char ch; InitStack(S) ; cinch; while (ch!=# & flag) switch(ch) case | (: Push( S,ch ); break; case ): if (!StackEmpty (S) & GetTop(S)=( ) Pop(S, e); else flag=0; break; case : if (!StackEmpty (S) & GetTop(S)= ) Pop(S, e); else flag=0; break; /switch cinch; /while if ( StackEmpty(S)

21、& flag ) return true; else return false;3、表达式求值表达式求值表达式表达式常数常数标识符标识符操作数操作数(operand)(operand)运算符运算符(operator)(operator)界限符界限符(delimiter)(delimiter)算术算术逻辑逻辑关系关系括号括号结束符结束符只考虑只考虑算术运算算术运算，算术四则运算规则，算术四则运算规则: :(1) (1) 先乘除先乘除, ,后加减后加减(2) (2) 从左算到右从左算到右(3) (3) 先括号内先括号内, ,后括号外后括号外12+-*/()#+-*/()#x=xx 算符间的

22、优先关系算符间的优先关系【算法思想算法思想】（1）初始化）初始化OPTR栈和栈和OPND栈，将栈，将 “#”压入压入OPTR（2）读入第一个字符）读入第一个字符ch，当，当OPTR的栈顶元素和的栈顶元素和 ch均为均为“#”时，表达式求值完毕，时，表达式求值完毕，OPND栈顶元素为表达式的值，栈顶元素为表达式的值，否则循环执行以下操作：否则循环执行以下操作：设定两栈设定两栈 ：OPND-OPND-操作数操作数, OPTR-, OPTR-运算符运算符（ 3） if (ch是操作数是操作数) 则则ch进进OPND，读入下一字符，读入下一字符ch else 比较比较OPTR栈顶元素和栈顶元素和ch的

23、优先级的优先级case : 栈顶运算符退栈、计算，结果进栈顶运算符退栈、计算，结果进OPNDOPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,3) #*(7-2)#3#Push(optr,*)#,*3(7-2)#Push(optr,()#,*,(37-2)#Push(opnd,7)#,*,(3,7-2)#Push(optr,-)#,*,(,-3,72)#Push(opnd,2)#,*,(,-3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)输入：输入： 3*(7-2)# 为

24、简化问题，只考虑一位数为简化问题，只考虑一位数int EvaluateExpression( ) InitStack (OPND); InitStack (OPTR); Push(OPTR, #); ch = getchar(); while ( !(ch=# & GetTop(OPTR)=#) ) if (! In(ch) / ch不是运算符则进栈不是运算符则进栈 Push(OPND, ch); ch = getchar(); else switch (Precede( GetTop(OPTR),ch) ) /比较优先权比较优先权 case : /弹出弹出OPTR栈顶的运算符栈顶的运

25、算符,运算后将结果入栈运算后将结果入栈 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b) ); break; case = : /脱括号并接收下一字符脱括号并接收下一字符 Pop(OPTR, x); ch = getchar(); break; / switch / while return GetTop(OPND); 3.3 3.3 队列队列队列也是一种操作受限的线性表，只允许在表的一队列也是一种操作受限的线性表，只允许在表的一端进行插入（表尾），在表的另一端进行删除（表端进行插入（表尾

26、），在表的另一端进行删除（表头）。头）。a1a2a3an.入队列入队列队头队头队尾队尾先进先出先进先出(FIFO)的线性表的线性表术语：术语：队头、队尾、入队头、队尾、入队列、出队列、空队列。队列、出队列、空队列。出队列出队列ADT Queue 数据对象：数据对象： D=ai|aiElemSet, i=1,2,.,n, n=0 数据关系：数据关系： R= |ai,ai+1D, i=1,2,.,n-1 基本操作：基本操作： InitQueue (&Q) /构造空队列构造空队列 DestroyQueue (&Q) /销毁队列销毁队列 ClearQueue (&Q) /清空队

27、列清空队列 QueueEmpty(Q) /判空判空 QueueLength(Q) /取队列长度取队列长度 GetHead (Q) /取队头元素取队头元素 EnQueue (&Q,e) /入队列入队列 DeQueue (&Q,&e) /出队列出队列 QueueTraverse(Q) /遍历遍历ADT Queue队列的抽象数据类型队列的抽象数据类型顺序存储结构的队列称为顺序存储结构的队列称为顺序队列顺序队列#define MAXQSIZE 100 /初始初始最大队列长度最大队列长度typedef struct QElemType *base; /初始化的动态分配存储空间初始

28、化的动态分配存储空间 int front; /头指针头指针，指向队头元素的位置，指向队头元素的位置 int rear; /尾指针，指向队尾元素的下一个位置尾指针，指向队尾元素的下一个位置 int queuesize; /最大队列长度最大队列长度SqQueue; 队列的顺序表示队列的顺序表示a1a2a3a4a5 0 1 2 3 4 queuesize -1 front rear base队列的顺序表示队列的顺序表示frontfront0 01 12 23 34 45 5rearrearfrontfrontrearrearJ J1 1J J2 2J J3 3frontfrontrearrearJ

29、J3 3frontfrontrearrearJ J5 5J J6 6front=rear=0空队标志：空队标志：front= =rear入队：入队：baserear+=x;出队：出队：x=basefront+;base frontfrontrearrearJ5J5J6J6frontfront0 01 12 23 34 45 5rearrearJ5J5J6J6J1J1J2J2J3J3J4J4存在的问题存在的问题数组大小为数组大小为queuesizefront=0rear=queuesize时时再入队再入队真溢出真溢出front 0rear=queuesize时时再入队再入队假溢出假溢出解决的方法

30、循环队列解决的方法循环队列1 10 0Q.rearQ.rearQ.frontQ.front.base0接在接在basequeuesize-1之之后后实现：利用实现：利用“模模”运算运算入队：入队： baserear=x; rear=(rear+1)%queuesize;出队：出队： x=basefront; front=(front+1)%queuesize; 顺序队列存在一个顺序队列存在一个假溢出问题，假溢出问题，解决办法是构造解决办法是构造一个逻辑上首尾相连的循环空间，称为一个逻辑上首尾相连的循环空间，称为循环队列循环队列J4J4J5J5J6J60 01 12 23 34 45 5rear

31、rearfrontfrontJ9J9J8J8J7J7J7,J8,J9J7,J8,J9入队入队队空：队空：front=rearfront=rear队满：队满：front=rearfront=rearJ4J4J5J5J6J60 01 12 23 34 45 5rearrearfrontfront0 01 12 23 34 45 5frontfrontJ4,J5,J6J4,J5,J6出队出队rearrear如何判断如何判断循环队列的队满与队空情况？循环队列的队满与队空情况？J4J4J5J5J6J60 01 12 23 34 45 5rearrearfrontfrontJ8J8J7J7循环队列的队满与

32、队空判断问题解决办法：循环队列的队满与队空判断问题解决办法：1. 设置一个长度变量设置一个长度变量len，用以统计队列的元素个数，用以统计队列的元素个数 当有元素入队时当有元素入队时: len+ ; 元素出队时：元素出队时：len- 队满条件：队满条件： len= queuesize 队空条件队空条件: len=0 2.少用一个元素空间少用一个元素空间： 队空：队空：front=rear 队满：队满：(rear+1)% queuesize=front0 01 12 23 34 45 5frontfrontrearrearvoid InitQueue (SqQueue &Q) Q.bas

33、e =new QElemTypeMAXQSIZE; if (!Q.base) exit(OVERFLOW); Q.queuesize= MAXQSIZE; Q.front=Q.rear=0;循环队列实现循环队列实现-初始化初始化typedef struct QElemType *base; int front, rear; int queuesize; SqQueue; bool QueueEmpty(SqQueue Q) return Q.front=Q.rear; 循环队列实现循环队列实现-判断是否为空判断是否为空循环队列实现循环队列实现-求长度求长度int QueueLength (Sq

34、Queue Q) return (Q.rear-Q.front+Q.queuesize)%Q.queuesize;J4J4J5J5J6J60 01 12 23 34 45 5rearrearfrontfrontJ8J8J7J70 01 12 23 34 45 5frontfrontrearrearJ4J4J5J5首先判断队列是否已满，若满，重新分配更大的空间首先判断队列是否已满，若满，重新分配更大的空间循环队列实现循环队列实现-入队入队EFCDrear=2front=34321098765CDrear=7front=343210EF98765EFCDrear=2front=343210队列已满

35、队列已满EFHrear=4front=043210 Gvoid EnQueue(SqQueue &Q, QElemType e) if (Q.rear+1)% Q.queuesize =Q.front) /若队列已满，重新分配若队列已满，重新分配 Q.base = (QElemType *) realloc (Q.base, 2* Q.queuesize *sizeof(QElemType); if (Q.rear != Q.queuesize-1) /原队列尾部内容向后移原队列尾部内容向后移 for ( int i=0; i=Q.rear-1; i+) Q.base i+Q. que

36、uesize = Q.basei; Q.rear = Q.rear + Q. queuesize; Q. queuesize = 2*Q. queuesize; Q.baseQ.rear=e; Q.rear=(Q.rear+1)% Q.queuesize;循环队列实现循环队列实现-入队入队CDrear=7front=343210EF98765void DeQueue (SqQueue &Q, QElemType &e) if (Q.front=Q.rear) cerr“队列已空无数据元素出栈！队列已空无数据元素出栈！”next=NULL;链队列实现链队列实现-初始化初始化fro

37、ntreartypedef struct QueuePtr front; QueuePtr rear; LinkQueue; void DestroyQueue (LinkQueue &Q) while(Q.front) Q.rear=Q.front-next; delete Q.front; Q.front=Q.rear; 链队列实现链队列实现-销毁销毁fronta1a2a3 rear bool QueueEmpty(LinkQueue Q) return Q.front=Q.rear; 链队列实现链队列实现-判断是否为空判断是否为空QElemType GetHead (LinkQu

38、eue Q) if (Q.front!=Q.rear) return Q.front-next-data;链队列实现链队列实现-求队头元素求队头元素fronta1a2a3 rearvoid EnQueue(LinkQueue &Q, QElemType e) p= new QNode; p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p;链队列实现链队列实现-入队入队fronta1a2a3 rearPevoid DeQueue (LinkQueue &Q, QElemType &e) if(Q.front=Q.rear) cer

39、r 队列已空，无法删除队列已空，无法删除! next; e=p-data; Q.front-next=p-next; if (Q.rear=p) Q.rear=Q.front; delete p;链队列实现链队列实现-出队出队fronta1a2a3 rearp1栈和队列是一种特殊的线性表，其特殊性体现在栈和队列是一种特殊的线性表，其特殊性体现在它们是它们是 的线性表。设现有元素的线性表。设现有元素e1,e2,e3,e4,e5和和e6依次进栈，若出栈的序列是依次进栈，若出栈的序列是e2,e4,e3,e6,e5,e1，则栈，则栈S的容量至少是的容量至少是 。 2顺序循环队列中，设队头指针为顺序循环

40、队列中，设队头指针为front，队尾指针，队尾指针为为rear，队中最多可有，队中最多可有MAX个元素，采用少用一个个元素，采用少用一个存储单元的方法区分队满与队空问题，则元素入队列存储单元的方法区分队满与队空问题，则元素入队列时队尾指针的变化为时队尾指针的变化为 ；元素；元素出队列时队头指针的变化为出队列时队头指针的变化为 ；队满的判别条件为为队满的判别条件为为 ，队，队空的判别条件为空的判别条件为 。操作受限操作受限3rear=(rear+1)%MAXfront=(front+1)%MAX(rear+1)%MAX=frontrear=front练习练习-填空题填空题用一维数组用一维数组a7

41、 顺序存储一个循环队列，队首和队尾顺序存储一个循环队列，队首和队尾指针分别用指针分别用front和和rear表示，当前队列中已有表示，当前队列中已有5个元个元素：素：22，30，16，36，58，其中，其中22是队首，是队首， front值值为为5，请画出对应的存储状态图，当连续做两次出队，请画出对应的存储状态图，当连续做两次出队运算后，再做两次入队运算，让元素运算后，再做两次入队运算，让元素80，55依次进队，依次进队，请再画出对应的存储状态图。请再画出对应的存储状态图。0123456163658223001234561636588055初始状态：初始状态：front=5,rear=3操作后

42、：操作后：front=0,rear=5练习练习-解答解答题题【例例】编程判断一个字符序列是否是回文。编程判断一个字符序列是否是回文。如：如：“ABCDEDCBA” 是回文，是回文，“ABCDEDBAC”不不是回文。是回文。算法思想算法思想: 使用栈和队列。使用栈和队列。 把字符依次进栈和进队列；把字符依次进栈和进队列； 然后逐个出栈和出队列，并比较每两个是否相同；然后逐个出栈和出队列，并比较每两个是否相同； 若全部相同，则说明是回文。若全部相同，则说明是回文。 可以用顺序结构也可以用链结构，这里用顺序结构。可以用顺序结构也可以用链结构，这里用顺序结构。3.4 3.4 队列的应用队列的应用#in

43、clude #include typedef char ElemType;typedef struct ElemType *base; ElemType *top; int stacksize; SqStack；typedef struct ElemType *base; int front, rear; int queuesize; SqQueue;#include “SeqStack.h”#include “SeqQueue.h”void HuiWen(char str ) SqQueue myQueue; SqStack myStack; char x, y; int i, length; length = strlen(str); InitQueue (myQueue); InitStack (myStack); for ( i=0; ilength; i+ ) EnQueue ( myQueue, stri ); Push( myStack, stri ); w