《《数据结构严蔚敏》ppt课件》由会员分享，可在线阅读，更多相关《《数据结构严蔚敏》ppt课件（708页珍藏版）》请在金锄头文库上搜索。
1、第3章 栈和队列,栈和队列是两种应用非常广泛的数据结构，它们都来自线性表数据结构，都是“操作受限”的线性表。 栈在计算机的实现有多种方式： 硬堆栈：利用CPU中的某些寄存器组或类似的硬件或使用内存的特殊区域来实现。这类堆栈容量有限，但速度很快； 软堆栈：这类堆栈主要在内存中实现。堆栈容量可以达到很大。在实现方式上，又有动态方式和静态方式两种。 本章将讨论栈和队列的基本概念、存储结构、基本操作以及这些操作的具体实现。,3.1 栈,3.1.1 栈的基本概念,1 栈的概念 栈(Stack)：是限制在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO (Last In First Out)或先
2、进后出FILO (First In Last Out)线性表。 栈顶(Top)：允许进行插入、删除操作的一端，又称为表尾。用栈顶指针(top)来指示栈顶元素。 栈底(Bottom)：是固定端，又称为表头。 空栈：当表中没有元素时称为空栈。,设栈S=(a1，a2，an)，则a1称为栈底元素，an为栈顶元素，如图3-1所示。 栈中元素按a1，a2，an的次序进栈，退栈的第一个元素应为栈顶元素。即栈的修改是按后进先出的原则进行的。,2 栈的抽象数据类型定义 ADT Stack 数据对象：D = ai|aiElemSet, i=1,2,n，n0 数据关系：R =|ai-1，aiD, i=2,3,n 基
3、本操作：初始化、进栈、出栈、取栈顶元素等 ADT Stack,栈的顺序存储结构简称为顺序栈，和线性表相类似，用一维数组来存储栈。根据数组是否可以根据需要增大，又可分为静态顺序栈和动态顺序栈。 静态顺序栈实现简单，但不能根据需要增大栈的存储空间； 动态顺序栈可以根据需要增大栈的存储空间，但实现稍为复杂。,3.1.2 栈的顺序存储表示,采用动态一维数组来存储栈。所谓动态，指的是栈的大小可以根据需要增加。 用bottom表示栈底指针，栈底固定不变的；栈顶则随着进栈和退栈操作而变化。用top(称为栈顶指针)指示当前栈顶位置。 用top=bottom作为栈空的标记，每次top指向栈顶数组中的下一个存储位
4、置。 结点进栈：首先将数据元素保存到栈顶(top所指的当前位置)，然后执行top加1，使top指向栈顶的下一个存储位置;,3.1.2.1 栈的动态顺序存储表示, 结点出栈：首先执行top减1，使top指向栈顶元素的存储位置，然后将栈顶元素取出。 图3-2是一个动态栈的变化示意图。,基本操作的实现 1 栈的类型定义 #define STACK_SIZE 100 /* 栈初始向量大小 */ #define STACKINCREMENT 10 /* 存储空间分配增量 */ #typedef int ElemType ; typedef struct sqstack ElemType *bottom;
5、 /* 栈不存在时值为NULL */ ElemType *top; /* 栈顶指针 */ int stacksize ; /* 当前已分配空间，以元素为单位 */ SqStack ;,2 栈的初始化 Status Init_Stack(void) SqStack S ; S.bottom=(ElemType *)malloc(STACK_SIZE *sizeof(ElemType); if (! S.bottom) return ERROR; S.top=S.bottom ; /* 栈空时栈顶和栈底指针相同 */ S. stacksize=STACK_SIZE; return OK ; ,3
6、压栈(元素进栈) Status push(SqStack S , ElemType e) if (S.top-S.bottom=S. stacksize-1) S.bottom=(ElemType *)realloc(S. STACKINCREMENT+STACK_SIZE) *sizeof(ElemType); /* 栈满，追加存储空间 */ if (! S.bottom) return ERROR; S.top=S.bottom+S. stacksize ; S. stacksize+=STACKINCREMENT ; *S.top=e; S.top+ ; /* 栈顶指针加1，e成为新的栈
7、顶 */ return OK; ,4 弹栈(元素出栈) Status pop( SqStack S, ElemType *e ) /*弹出栈顶元素*/ if ( S.top= S.bottom ) return ERROR ; /* 栈空，返回失败标志 */ S.top- ; e=*S. top ; return OK ; ,采用静态一维数组来存储栈。 栈底固定不变的，而栈顶则随着进栈和退栈操作变化的， 栈底固定不变的；栈顶则随着进栈和退栈操作而变化，用一个整型变量top(称为栈顶指针)来指示当前栈顶位置。 用top=0表示栈空的初始状态，每次top指向栈顶在数组中的存储位置。 结点进栈：首先
8、执行top加1，使top指向新的栈顶位置，然后将数据元素保存到栈顶(top所指的当前位置)。,3.1.2.2 栈的静态顺序存储表示, 结点出栈：首先把top指向的栈顶元素取出，然后执行top减1，使top指向新的栈顶位置。 若栈的数组有Maxsize个元素，则top=Maxsize-1时栈满。图3-3是一个大小为5的栈的变化示意图。,基本操作的实现 1 栈的类型定义 # define MAX_STACK_SIZE 100 /* 栈向量大小 */ # typedef int ElemType ; typedef struct sqstack ElemType stack_arrayMAX_STA
9、CK_SIZE ; int top; SqStack ;,2 栈的初始化 SqStack Init_Stack(void) SqStack S ; S.bottom=S.top=0 ; return(S) ; ,3 压栈(元素进栈) Status push(SqStack S , ElemType e) /* 使数据元素e进栈成为新的栈顶 */ if (S.top=MAX_STACK_SIZE-1) return ERROR; /* 栈满，返回错误标志 */ S.top+ ; /* 栈顶指针加1 */ S.stack_arrayS.top=e ; /* e成为新的栈顶 */ return OK
10、; /* 压栈成功 */ ,4 弹栈(元素出栈) Status pop( SqStack S, ElemType *e ) /*弹出栈顶元素*/ if ( S.top=0 ) return ERROR ; /* 栈空，返回错误标志 */ *e=S.stack_arrayS.top ; S.top- ; return OK ; ,当栈满时做进栈运算必定产生空间溢出，简称“上溢”。上溢是一种出错状态，应设法避免。 当栈空时做退栈运算也将产生溢出，简称“下溢”。下溢则可能是正常现象，因为栈在使用时，其初态或终态都是空栈，所以下溢常用来作为控制转移的条件。,1 栈的链式表示 栈的链式存储结构称为链栈，
11、是运算受限的单链表。其插入和删除操作只能在表头位置上进行。因此，链栈没有必要像单链表那样附加头结点，栈顶指针top就是链表的头指针。图3-4是栈的链式存储表示形式。,3.1.3 栈的链式存储表示,链栈的结点类型说明如下： typedef struct Stack_Node ElemType data ; struct Stack_Node *next ; Stack_Node ;,2 链栈基本操作的实现 (1) 栈的初始化 Stack_Node *Init_Link_Stack(void) Stack_Node *top ; top=(Stack_Node *)malloc(sizeof(St
12、ack_Node ) ; top-next=NULL ; return(top) ; ,(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(Stack_Node
13、*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(二、八、十六)的转
14、换是计算机实现计算的基本问题。 转换法则：该转换法则对应于一个简单算法原理: 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)
15、 ; n=n/d ; /* 求出所有的余数，进栈 */ while (S.top!=0) /* 栈不空时出栈，输出 */ pop(S, e) ; printf(“%1d” , *e) ; ,3.2.2 括号匹配问题,在文字处理软件或编译程序设计时，常常需要检查一个字符串或一个表达式中的括号是否相匹配? 匹配思想：从左至右扫描一个字符串(或表达式)，则每个右括号将与最近遇到的那个左括号相匹配。则可以在从左至右扫描过程中把所遇到的左括号存放到堆栈中。每当遇到一个右括号时，就将它与栈顶的左括号(如果存在)相匹配，同时从栈顶删除该左括号。 算法思想：设置一个栈，当读到左括号时，左括号进栈。当读到右括号时，则从栈中弹出一个元素，与读到的左括号进行匹配，若匹配成功，继续读入；否则匹配失败，返回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)
