第3章栈和队列.ppt
《第3章栈和队列.ppt》由会员分享,可在线阅读,更多相关《第3章栈和队列.ppt(62页珍藏版)》请在三一文库上搜索。
1、第3章 栈和队列,栈和队列是两种应用非常广泛的数据结构,它们都来自线性表数据结构,都是“操作受限”的线性表。 栈:先进后出 (FILO) 队列:先进先出 (FIFO) 应用举例(讨论) 本章将讨论栈和队列的基本概念、存储结构、基本操作以及这些操作的具体实现。,第3章 栈和队列,说明:栈在计算机的实现有多种方式: 硬堆栈:利用CPU中的某些寄存器组或类似的硬件或使用内存的特殊区域来实现。这类堆栈容量有限,但速度很快; 软堆栈:这类堆栈主要在内存中实现。堆栈容量可以达到很大。在实现方式上,又有动态方式和静态方式两种。,3.1 栈,3.1.1 栈的基本概念,栈(Stack):是限制在表的一端进行插入
2、和删除操作的线性表。又称为后进先出LIFO (Last In First Out)或先进后出FILO (First In Last Out)线性表。 栈顶(Top):允许进行插入、删除操作的一端,又称为表尾。用栈顶指针(top)来指示栈顶元素。 栈底(Bottom):是固定端,又称为表头。 空栈:当表中没有元素时称为空栈。,设栈S=(a1,a2,an),则a1称为栈底元素,an为栈顶元素,如图3-1所示。 栈中元素按a1,a2,an的次序进栈,退栈的第一个元素应为栈顶元素。即栈的修改是按后进先出的原则进行的。,栈的抽象数据类型定义 ADT Stack 数据对象:D = ai|aiElemSet
3、, i=1,2,n,n0 数据关系:R =|ai-1,aiD, i=2,3,n 基本操作:初始化、进栈、出栈、取栈顶元素等 ADT Stack,栈的顺序存储结构简称为顺序栈,和线性表相类似,用一维数组来存储栈。根据数组是否可以根据需要增大,又可分为静态顺序栈和动态顺序栈。 静态顺序栈实现简单,但不能根据需要增大栈的存储空间; 动态顺序栈可以根据需要增大栈的存储空间,但实现稍为复杂。,3.1.2 栈的顺序存储表示,采用动态一维数组来存储栈。所谓动态,指的是栈的大小可以根据需要增加。 用bottom表示栈底指针,栈底固定不变的;栈顶则随着进栈和退栈操作而变化。用top(称为栈顶指针)指示当前栈顶位
4、置。 注意:栈顶指针top不指向栈顶元素,3.1.2.1 栈的动态顺序存储表示, 用top=bottom作为栈空的标记,每次top指向栈顶数组中的下一个存储位置。 结点进栈:首先将数据元素保存到栈顶(top所指的当前位置),然后执行top加1,使top指向栈顶的下一个存储位置; 结点出栈:首先执行top减1,使top指向栈顶元素的存储位置,然后将栈顶元素取出。,图3-2是一个动态栈的变化示意图。,栈的动态顺序存储类型定义 #define STACK_SIZE 100 / 栈初始向量大小 #define STACKINCREMENT 10 /存储空间分配增量 #typedef int ElemT
5、ype ; typedef struct sqstack ElemType *bottom; / 栈不存在时值为NULL ElemType *top; / 栈顶指针 int stacksize ; /当前已分配空间,以元素/为单位 SqStack ;,基本操作的实现栈的初始化 Status Init_Stack(SqStack ,基本操作的实现压栈(元素进栈) Status push(SqStack ,基本操作的实现弹栈(元素出栈) Status pop( SqStack ,采用静态一维数组来存储栈。 栈底固定不变的;栈顶则随着进栈和退栈操作而变化,用一个整型变量top(称为栈顶指针)来指示当
6、前栈顶位置。 用top=0表示栈空的初始状态,每次top指向栈顶在数组中的存储位置。 结点进栈:首先执行top加1,使top指向新的栈顶位置,然后将数据元素保存到栈顶(top所指的当前位置)。,3.1.2.2 栈的静态顺序存储表示, 结点出栈:首先把top指向的栈顶元素取出,然后执行top减1,使top指向新的栈顶位置。 若栈的数组有Maxsize个元素,则top=Maxsize-1时栈满。图3-3是一个大小为5的栈的变化示意图。,栈的静态顺序存储类型定义 # define MAX_STACK_SIZE 100 / 栈向量大小 # typedef int ElemType ; typedef
7、struct sqstack ElemType stack_arrayMAX_STACK_SIZE ; int top; SqStack ;,基本操作的实现栈的初始化 SqStack Init_Stack(void) SqStack S ; S.bottom=S.top=0 ; return(S) ; 或者 Status Init_Stack(SqStack ,基本操作的实现 压栈(元素进栈) Status push(SqStack / 压栈成功 ,基本操作的实现 弹栈(元素出栈) Status pop( SqStack ,当栈满时做进栈运算必定产生空间溢出,简称“上溢”。上溢是一种出错状态,
8、应设法避免。 当栈空时做退栈运算也将产生溢出,简称“下溢”。下溢则可能是正常现象,因为栈在使用时,其初态或终态都是空栈,所以下溢常用来作为控制转移的条件。,栈的链式存储结构称为链栈,是运算受限的单链表。其插入和删除操作只能在表头位置上进行。因此,链栈没有必要像单链表那样附加头结点,栈顶指针top就是链表的头指针。图3-4是栈的链式存储表示形式。,3.1.3 栈的链式存储表示,1 链栈的类型定义,链栈的结点类型说明如下: typedef struct Stack_Node ElemType data ; struct Stack_Node *next ; Stack_Node, *LinkSta
9、ck ;,2 链栈基本操作的实现 (1) 栈的初始化 status Init_Link_Stack(Stack_Node ,(2) 压栈(元素进栈) Status push(Stack_Node *top , ElemType e) Stack_Node *p ; p=(Stack_Node *)malloc(sizeof(Stack_Node) ; if (!p) return ERROR; / 申请新结点失败,返回错误标志 p-data=e ; p-next=top-next ; top-next=p ; / 钩链 return OK; ,(3) 弹栈(元素出栈) Status pop(S
10、tack_Node *top , ElemType *e) Stack_Node *p ; ElemType e ; if (top-next=NULL ) return ERROR ; / 栈空,返回错误标志 p=top-next ; e=p-data ; / 取栈顶元素 top-next=p-next ; / 修改栈顶指针 free(p) ; return OK ; ,3.2 栈的应用,由于栈具有的“后进先出”的固有特性,因此,栈成为程序设计中常用的工具和数据结构。以下是几个栈应用的例子。,3.2.1 数制转换,十进制整数N向其它进制数d(二、八、十六)的转换是计算机实现计算的基本问题。,
11、转换法则:该转换法则对应于一个简单算法原理: n=(n div d)*d+n mod d 其中:div为整除运算,mod为求余运算 例如 (1348)10= (2504)8,其运算过程如下: n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,采用静态顺序栈方式实现 void conversion(int n , int d) /将十进制整数N转换为d(2或8)进制数 SqStack S ; int k, *e ; S=Init_Stack(); while (n0) k=n%d ; push(S , k) ; n=n/d ; / 求出所有的余
12、数,进栈 while (S.top!=0) / 栈不空时出栈,输出 pop(S, e) ; printf(“%1d” , *e) ; ,3.2.2 括号匹配问题,在文字处理软件或编译程序设计时,常常需要检查一个字符串或一个表达式中的括号是否相匹配? 匹配思想:从左至右扫描一个字符串(或表达式),则每个右括号将与最近遇到的那个左括号相匹配。则可以在从左至右扫描过程中把所遇到的左括号存放到堆栈中。每当遇到一个右括号时,就将它与栈顶的左括号(如果存在)相匹配,同时从栈顶删除该左括号。,算法思想: 设置一个栈,当读到左括号时,左括号进栈。当读到右括号时,则从栈中弹出一个元素,与读到的左括号进行匹配,若
13、匹配成功,继续读入;否则匹配失败,返回FLASE。 举例。,算法描述 #define TRUE 0 #define FLASE -1 SqStack S ; S=Init_Stack() ; /*堆栈初始化*/ int Match_Brackets( ) char ch , x ; scanf(“%c” , while (asc(ch)!=13), if (ch=()|(ch=) push(S , ch) ; else if (ch=) x=pop(S) ; if (x!=) printf(“括号不匹配”) ; return FLASE ; else if (ch=) x=pop(S) ; i
14、f (x!=() printf(“(括号不匹配”) ; return FLASE ; ,if (S.top!=0) printf(“括号数量不匹配!”) ; return FLASE ; else return TRUE ; ,3.2.2 栈与递归调用的实现,栈的另一个重要应用是在程序设计语言中实现递归调用。 递归调用:一个函数(或过程)直接或间接地调用自己本身,简称递归(Recursive)。 递归是程序设计中的一个强有力的工具。因为递归函数结构清晰,程序易读,正确性很容易得到证明。 为了使递归调用不至于无终止地进行下去,实际上有效的递归调用函数(或过程)应包括两部分:递推规则(方法),终止
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 队列
链接地址:https://www.31doc.com/p-2577414.html