《数据结构 栈和队列讲义》由会员分享，可在线阅读，更多相关《数据结构 栈和队列讲义（99页珍藏版）》请在金锄头文库上搜索。
1、第3章 栈和队列,3.1 栈,3.2 队列,本章小结,3.1.1 栈的定义,3.1.2 栈的顺序存储结构及其基本运算实现,3.1.3 栈的链式存储结构及其基本运算的实现,3.1.4 栈的应用例子,3.1 栈,栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。 栈顶的当前位置是动态的,栈顶的当前位置由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。 当栈中没有数据元素时,称为空栈。 栈的插入操作通常称为进栈或入栈,栈的删除操作通常称为退栈或出栈。,3.1.1 栈的定义,栈顶,栈底,出栈,进栈,栈示意图,例3.1 设有4个元素a、b、c、d进栈,给出它们
2、所有可能的出栈次序。 答:所有可能的出栈次序如下: abcd abdc acbd acdb adcb bacd badc bcad bcda bdca cbad cbda cdba dcba,例3.2 设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是 。 (A) A,B,C,D (B) D,C,B,A (C) A,C,D,B (D) D,A,B,C,答:可以简单地推算,得容易得出D,A,B,C是不可能的,因为D先出来,说明A,B,C,D均在栈中,按照入栈顺序,在栈中顺序应为D,C,B,A,出栈的顺序只能是D,C,B,A。所以本题答案为D。,例3.3 已知一个栈的进栈序列
3、是1,2,3,n,其输出序列是p1,p2,pn,若p1=n,则pi的值 。 (A) i (B) n-i (C) n-i+1 (D) 不确定,答:当p1=n时,输出序列必是n,n-1,3,2,1,则有: p2=n-1, p3=n-2, , pn=1 推断出pi=n-i+1,所以本题答案为C。,例3.4 设n个元素进栈序列是1,2,3,n,其输出序列是p1,p2,pn,若p1=3,则p2的值 。 (A) 一定是2 (B) 一定是1 (C) 不可能是1 (D) 以上都不对,答:当p1=3时,说明1,2,3先进栈,立即出栈3,然后可能出栈,即为2,也可能4或后面的元素进栈,再出栈。因此,p2可能是2,
4、也可能是4,n,但一定不能是1。所以本题答案为C。,栈的几种基本运算如下: (1) 初始化栈InitStack(&s):构造一个空栈s。 (2) 销毁栈ClearStack(&s):释放栈s占用的存储空间。 (3) 求栈的长度StackLength(s):返回栈s中的元素个数。 (4) 判断栈是否为空StackEmpty(s):若栈s为空,则返回真；否则返回假。,(5) 进栈Push(&S,e):将元素e插入到栈s中作为栈顶元素。 (6) 出栈Pop(&s,&e):从栈s中退出栈顶元素,并将其值赋给e。 (7) 取栈顶元素GetTop(s,&e):返回当前的栈顶元素,并将其值赋给e。 (8)
5、显示栈中元素DispStack(s):从栈顶到栈底顺序显示栈中所有元素。,3.1.2 栈的顺序存储结构及其基本运算实现 假设栈的元素个数最大不超过正整数MaxSize,所有的元素都具有同一数据类型ElemType,则可用下列方式来定义栈类型SqStack: typedef struct ElemType dataMaxSize； int top； /*栈指针*/ SqStack；,顺序栈进栈和出栈示意图,在顺序栈中实现栈的基本运算算法: (1) 初始化栈initStack( ,(2) 销毁栈ClearStack( ,(3) 求栈的长度StackLength(s) 返回栈s中的元素个数,即栈指针
6、加1的结果。对应算法如下: int StackLength(SqStack *s) return(s-top+1); ,(4) 判断栈是否为空StackEmpty(s) 栈S为空的条件是s-top=-1。对应算法如下: int StackEmpty(SqStack *s) return(s-top=-1); ,(5) 进栈Push( ,(6) 出栈Pop( ,(7) 取栈顶元素GetTop(s) 在栈不为空的条件下,将栈顶元素赋给e。对应算法如下: int GetTop(SqStack *s,ElemType ,(8) 显示栈中元素DispStack(s) 从栈顶到栈底顺序显示栈中所有元素。对
7、应算法如下: void DispStack(SqStack *s) int i; for (i=s-top;i=0;i-) printf(“%c “,s-datai); printf(“n“); ,3.1.3 栈的链式存储结构及其基本运算的实现 采用链式存储的栈称为链栈,这里采用单链表实现。 链栈的优点是不存在栈满上溢的情况。我们规定栈的所有操作都是在单链表的表头进行的,下图是头结点为*lhead的链栈,第一个数据结点是栈顶结点,最后一个结点是栈底结点。栈中元素自栈顶到栈底依次是a1、a2、an。,链栈示意图,链栈中数据结点的类型LiStack定义如下: typedef struct link
8、node ElemType data; /*数据域*/ struct linknode *next; /*指针域*/ LiStack;,在链栈中,栈的基本运算算法如下: (1) 初始化栈initStack( ,(2) 销毁栈ClearStack( ,(3) 求栈的长度StackLength(s) 从第一个数据结点开始扫描单链表,用i记录访问的数据结点个数,最后返回i值。对应算法如下: int StackLength(LiStack *s) int i=0; LiStack *p; p=s-next; while (p!=NULL) i+;p=p-next; return(i); ,(4) 判断
9、栈是否为空StackEmpty(s) 栈S为空的条件是s-next=NULL,即单链表中没有数据结点。对应算法如下: int StackEmpty(LiStack *s) return(s-next=NULL); ,s,(5) 进栈Push( ,(6) 出栈Pop( ,(7) 取栈顶元素GetTop(s) 在栈不为空的条件下,将头结点后继数据结点的数据域赋给e。对应算法如下: int GetTop(LiStack *s,ElemType ,(8) 显示栈中元素DispStack(s) 从第一个数据结点开始扫描单链表,并输出当前访问结点的数据域值。对应算法如下: void DispStack(L
10、iStack *s) LiStack *p=s-next; while (p!=NULL) printf(“%c “,p-data); p=p-next; printf(“n“); ,例3.5 假设表达式中允许包含三种括号:圆括号、方括号和大括号。编写一个算法判断表达式中的括号是否正确配对。,解: 设置一个括号栈,扫描表达式：遇到左括号(包括(、和)时进栈,遇到右括号时,若栈是相匹配的左括号,则出栈,否则,返回0。 若表达式扫描结束,栈为空,返回1表示括号正确匹配,否则返回0。,int correct(char exp,int n) char stMaxSize; int top=-1,i=0
11、,tag=1; while (in ,if (expi=) /*遇到,若栈顶是, 则继续处 理,否则以不配对返回*/ if (sttop=) top-; else tag=0; if (expi=) /*遇到,若栈顶是 ,则继续处 理,否则以不配对返回*/ if (sttop=) top-; else tag=0; i+; /*表达式扫描完毕*/ if (top-1) tag=0; /*若栈不空,则不配对*/ return(tag); ,3.1.4 栈的应用例子 1. 表达式求值 这里限定的表达式求值问题是:用户输入一个包含“+”、“-”、“*”、“/”、正整数和圆括号的合法数学表达式,计算该
12、表达式的运算结果。,在程序语言中,运算符位于两个操作数中间的表达式称为中缀表达式。例如： 1+2*3 就是一个中缀表达式,中缀表达式是最常用的一种表达式方式。对中缀表达式的运算一般遵循“先乘除,后加减,从左到右计算,先括号内,后括号外”的规则。因此,中缀表达式不仅要依赖运算符优先级,而且还要处理括号。,所谓后缀表达式,就是运算符在操作数的后面,如1+2*3的后缀表达式为123*+。在后缀表达式中已考虑了运算符的优先级,没有括号,只有操作数和运算符。 对后缀表达式求值过程是:从左到右读入后缀表达式,若读入的是一个操作数,就将它入数值栈,若读入的是一个运算符op,就从数值栈中连续出栈两个元素(两个
13、操作数),假设为x和y,计算x op y之值,并将计算结果入数值栈；对整个后缀表达式读入结束时,栈顶元素就是计算结果。,算术表达式求值过程是:先将算术表达式转换成后缀表达式,然后对该后缀表达式求值。 假设算术表达式中的符号以字符形式由键盘输入,并存放在字符型数组str中,其后缀表达式存放在字符型数组exp中,在将算术表达式转换成后缀表达式的过程中用一个字符型数组op作为栈。将算术表达式转换成后缀表示的方法如下:,while (从exp读取字符ch,ch!=0) 若ch为数字,将后续的所有数字均依次存放到postexp中,并以字符“#”标志数值串结束。 若ch为左括号“(”,则将此括号进栈到运算
14、符栈op中。 若ch为右括号“)”,则将运算符栈op中左括号“(”以前的运算符依次出栈并存放到postexp中,然后将左括号“(”删除。 若ch运算符优先级小于或等于op栈顶运算符的优先级 (除栈顶运算符为“(”外)的优先级,则依次出栈并存入到postexp中,然后将ch进栈。 若字符串exp扫描完毕,则将运算栈op中的所有运算符依次出栈并存放到postexp中。最后得到后缀表达式postexp。,中缀表达式后缀表达式,对于表达式“(56-20)/(4+2)”,其转换成后缀表达式的过程 如下：,将算术表达式str转换成后缀表达式exp void trans(char str,char exp)
15、 struct char dataMaxSize; /*存放运算符*/ int top; /*栈指针*/ op; /*定义运算符栈*/ char ch; int i=0,t=0; /*t作为exp的下标,i作为str的下标*/ op.top=-1; ch=stri;i+;,while (ch!=0) /*str表达式未扫描完时循环*/ switch(ch) case (: /*判定为左括号*/ op.top+;op.dataop.top=ch; break; case ): /*判定为右括号*/ while (op.dataop.top!=() expt=op.dataop.top; op.top-; t+; op.top-; break; case +: case -: /*判定为加或减号*/ while (op.top!=-1 ,case *: case /: /*判定为*或/号*/ while (op.dataop.top=* | op.dataop.top=/) expt=op.dataop.top; op.top-; t+; op.top+;op.dataop.top=ch; break; case :break; /*过滤掉空格*/ default: whi
