计算机数据结构 栈和队列.ppt

第3章 栈和队列 栈 栈的应用举例 栈与递归的实现* 队列 队列的应用举例 本章学习要点 掌握 1、 栈的基本概念、存储结构以及入栈、出栈等基本操作。 2、在处理实际问题中如何运用栈的特点解决问题 3、队列栈的基本概念、存储结构以及入队、出队等基本操作。 3、循环队列的逻辑结构及其存储结构实现，循环队列的优点 理解 1、栈和递归的关系 2、如何运用队列解决实际问题。 栈和队列 栈和队列是两种重要的线性结构 从数据结构角度看，栈和队列是线性表 栈和队列的操作是线性表的一个子集 操作受限的线性表 由于操作受限，在实现时可以针对特殊的操作进行设计 表现为两种和线性表大不相同的类型 在各种软件系统中应用广泛 2.1 栈 栈的定义 栈的表示和实现 顺序栈 链栈 栈的定义 栈（stack）是限定在表尾进行插入和删除操作的线性表。 表尾?栈顶（top） 表头?栈底（bottom） 不含元素的空表成为空栈 例如 栈S=（a1,a2,…,an） a1为栈底元素，an为栈顶元素 如果将在栈中插入元素，视为元素入线性表 如果将从栈中删除元素，视为元素出线性表 可知：先入线性表的元素后出线性表 反之：后入线性表的元素先出线性表 则：栈又称为后进先出线性表 LIFO(Last in First Out) 栈的抽象数据类型定义 ADT Stack{ 数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系：R1={ai-1, ai| ai-1,ai∈D,i=2,3,…,n} 约定a1为栈底，an为栈顶 基本操作： InitStack(S) 构造一个空栈S DestroyStack(S) 销毁一个栈S ClearStack(S) 将栈S清为空栈 StackEmpty(S) 判断S是否为空栈 StackLength(S) 求栈S的长度 GetTop(S,e) 返回栈顶元素 Push(S,e) 元素e入堆栈S Pop(S,e) 出栈到元素e StackTraverse(S,visit()) 遍历堆栈S }ADT Stack 顺序栈 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素 通常指针top指示栈顶元素在顺序栈中的位置 top=0 表示空栈,但是C的下标0表示第一个元素. 栈要定义多大合适？ 解决 首先为堆栈分配一个基本容量(STACK_INIT_SIZE)，然后按照设定的递增量(STACKINCREMENT)增加。（和线性表的顺序一样） 使用base指针指示栈底，top指针指向栈顶。 结构定义 typedef struct{ SElemType * base; SElemType * top; int stacksize; }SqStack 栈的顺序存储表示 // -----栈的顺序表示和实现 #define STACK_INIT_SIZE 100; #define STACKINSREMENT 10; typedef struct{ SElemType *base; //构造前和销毁后等于NULL SElemType *top; //栈顶指针 int stacksize; //当前已经分配的存储空间 }SqStack; //----- 基本操作的函数原型说明 。。。。。。 //-----基本操作的算法描述 ??? 基本操作算法：InitStack Status InitStack(SqStack S){ //构造一个空栈S S.base=(SElemType *) malloc(STACK_INIT_SIZE*sizeof(SElemType)); if (!S.base)exit (OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK: }//InitStack 注意：此时栈为空栈，base=top 基本操作算法：Push Status Push(SqStack S,SElemType e){ //插入元素e为新的栈顶元素 if (S.top-S.base=S.StackSize){ S.base=(SElemType*)realloc (S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base + S.stacksize ; S.stacksize+=STACKINCREMENT; } //栈分配空间