第3章栈和队

《第3章栈和队》由会员分享，可在线阅读，更多相关《第3章栈和队（88页珍藏版）》请在金锄头文库上搜索。

1、第3章 栈和队列,南理工大学紫金学院计算机系 路红,第3章 栈和队列,3.1 栈 3.2 队列,本章小结,本章内容,南理工大学紫金学院计算机系 路红,3.1.1 栈的定义,3.1.2 栈的顺序存储结构及其基运算实现,3.1.3 栈的链式存储结构及其基本运算的实现,3.1.4 栈的应用例子,3.1 栈,本节内容,掌握,南理工大学紫金学院计算机系 路红,栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。表的另一端称为栈底。 栈顶的当前位置是动态的,栈顶的当前位置由一个称为栈顶指针的位置指示器指示。 当栈中没有数据元素时,称为空栈。 栈的插入操作通常称为进栈或入

2、栈,栈的删除操作通常称为退栈或出栈。,3.1.1 栈的定义,栈的定义,南理工大学紫金学院计算机系 路红,栈顶,栈底,出栈,进栈,栈示意图,南理工大学紫金学院计算机系 路红,进出栈顺序,每次进栈的数据元素都放在原当前栈顶元素之前成为新的栈顶元素，每次出栈的数据元素都是原当前栈顶元素。因此，可以称为后进先出。,进出栈特征,南理工大学紫金学院计算机系 路红,进出栈顺序,“后进先出”，即后进栈的元素先弹出。,栈的主要特点,南理工大学紫金学院计算机系 路红,a,b,c,d,进栈出栈示意图,进栈,出栈,进出栈顺序,南理工大学紫金学院计算机系 路红,a,b,c,d,进栈出栈示意图,进出栈顺序,南理工大学紫金

3、学院计算机系 路红,例3.1 设有4个元素a、b、c、d进栈,给出它们所有可能的出栈次序。 答:所有可能的出栈次序如下: abcd abdc acbd acdb adcb bacd badc bcad bcda bdca cbad cbda cdba dcba,出栈例题,出栈时如果序号大的在前面 则比其小的元素一定是逆序出栈的,进出栈顺序,南理工大学紫金学院计算机系 路红,设一个栈的输入序列为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是不可

4、能的,因为D先出来,说明A,B,C,D均在栈中,按照入栈顺序,在栈中顺序应为D,C,B,A,出栈的顺序只能是D,C,B,A。所以本题答案为D。,例3.2,进出栈顺序,南理工大学紫金学院计算机系 路红,已知一个栈的进栈序列是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.3,进出栈顺序,南理工大学紫金学院计算机系 路红,设n个元素进栈序列是1,2,3,

5、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,n,但一定不能是1。所以本题答案为C。,例3.4,进出栈顺序,南理工大学紫金学院计算机系 路红,(1) 初始化栈InitStack(&s):构造一个空栈s。 (2) 销毁栈ClearStack(&s):释放栈s占用的存储空间。 (3) 求栈的长度StackLength(s):返回栈s中的元素个数。 (4) 判断栈是否为空

6、StackEmpty(s):若栈s为空,则返回真；否则返回假。,栈的几种基本运算,南理工大学紫金学院计算机系 路红,(5) 进栈Push(&S,e):将元素e插入到栈s中作为栈顶元素。 (6) 出栈Pop(&s,&e):从栈s中退出栈顶元素,并将其值赋给e。 (7) 取栈顶元素GetTop(s,&e):返回当前的栈顶元素,并将其值赋给e。 (8) 显示栈中元素DispStack(s):从栈顶到栈底顺序显示栈中所有元素。,栈的几种基本运算,南理工大学紫金学院计算机系 路红,顺序栈：采用顺序存储的栈。 特点：分配一块连续的存储区域存放栈中的元素，并用一个变量指向当前的栈顶。,3.1.2 栈的顺序存

7、储结构及其基本运算实现,顺序栈,南理工大学紫金学院计算机系 路红,a,b,c,d,进栈示意图,进栈,进栈示意图,南理工大学紫金学院计算机系 路红,假设栈的元素个数最大不超过正整数MaxSize,所有的元素都具有同一数据类型ElemType,则可用下列方式来定义栈类型SqStack: typedef struct ElemType dataMaxSize； int top； /*栈顶指针*/ SqStack；,3.1.2 栈的顺序存储结构及其基本运算实现,顺序栈类型定义,南理工大学紫金学院计算机系 路红,顺序栈进栈和出栈示意图,南理工大学紫金学院计算机系 路红,(1) 初始化栈initStack

8、( ,顺序栈基本运算:,南理工大学紫金学院计算机系 路红,(2) 销毁栈ClearStack( ,顺序栈基本运算:,南理工大学紫金学院计算机系 路红,(3) 求栈的长度StackLength(s) 返回栈s中的元素个数,即栈指针加1的结果。对应算法如下: int StackLength(SqStack *s) return(s-top+1); ,顺序栈基本运算:,南理工大学紫金学院计算机系 路红,(4) 判断栈是否为空StackEmpty(s) 栈S为空的条件是s-top= -1。对应算法如下: int StackEmpty(SqStack *s) return(s-top= -1); ,顺序

9、栈基本运算:,南理工大学紫金学院计算机系 路红,(5) 进栈Push( ,顺序栈基本运算:,南理工大学紫金学院计算机系 路红,a,b,c,d,进栈示意图,进栈,进栈示意图,南理工大学紫金学院计算机系 路红,(6) 出栈Pop( ,顺序栈基本运算:,南理工大学紫金学院计算机系 路红,a,b,c,d,进栈示意图,进栈示意图,出栈,a,b,c,d,3,2,1,0,南理工大学紫金学院计算机系 路红,(7) 取栈顶元素GetTop(s) 在栈不为空的条件下,将栈顶元素赋给e。对应算法如下: int GetTop(SqStack *s,ElemType ,顺序栈基本运算:,南理工大学紫金学院计算机系 路红

10、,(8) 显示栈中元素DispStack(s) 从栈顶到栈底顺序显示栈中所有元素。对应算法如下: void DispStack(SqStack *s) int i; for (i=s-top;i=0;i-) printf(“%c “,s-datai); printf(“n“); ,顺序栈基本运算:,南理工大学紫金学院计算机系 路红,算法思考,1. 设计一个算法，利用栈的基本运算，将指定栈中的内容进行逆转。 2. 设计一个算法，利用栈的基本运算返回指定栈中的栈底元素。 3. 数制转换,南理工大学紫金学院计算机系 路红,采用链式存储的栈称为链栈,这里采用单链表实现。 链栈的优点是不存在栈满上溢的情

11、况。我们规定栈的所有操作都是在单链表的表头进行的,下图是头结点为*lhead的链栈,第一个数据结点是栈顶结点,最后一个结点是栈底结点。栈中元素自栈顶到栈底依次是a1、a2、an。,3.1.3 栈的链式存储结构及其基本运算的实现,链栈定义及特点,南理工大学紫金学院计算机系 路红,链栈示意图,南理工大学紫金学院计算机系 路红,链栈中数据结点的类型LiStack定义如下: typedef struct linknode ElemType data; /*数据域*/ struct linknode *next; /*指针域*/ LiStack;,链栈类型定义,南理工大学紫金学院计算机系 路红,(1)

12、初始化栈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) 判断栈是否为空StackEmpty(s) 栈S为空的

13、条件是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) 显示栈中元素DispS

14、tack(s) 从第一个数据结点开始扫描单链表,并输出当前访问结点的数据域值。对应算法如下: void DispStack(LiStack *s) LiStack *p=s-next; while (p!=NULL) printf(“%c “,p-data); p=p-next; printf(“n“); ,南理工大学紫金学院计算机系 路红,例3.5 假设表达式中允许包含一种括号:圆括号。编写一个算法判断表达式中的括号是否正确配对。,解: 设置一个括号栈,扫描表达式：遇到左括号( “( ” )时进栈,遇到右括号时,若栈是相匹配的左括号,则出栈,否则,返回0。 若表达式扫描结束,栈为空,返回1表

15、示括号正确匹配,否则返回0。,南理工大学紫金学院计算机系 路红,int Match(char exp,int n) int i=0; char e; SqStack *st; InitStack(st); while(in) if (expi= =( ) Push(st,expi); else if (expi= =） ),南理工大学紫金学院计算机系 路红,if (GetTop(st,e)= =1) if(e!= ） ) return 0; else Pop(st,e); else return 0; i+; if (StackEmepty(st)=1) return(1); else return(0); ,南理工大学紫金学院计算机系 路红,1. 一个栈的进栈顺序是1、2、3、4，则栈输出序列不可能是 D 。 A. 4、3、2、1 B. 1、2、3、4 C. 1、4、3、2 D. 3、1、4、2 2.编写算法实现顺序栈基本运算。,作业,南理工大学紫金学院计算机系 路红,3.向一个头结点为*HS的链栈中插入s所指结点，则执行 B 。 A. HS-next = s; B. s-next = HS-next;