文档介绍：数数据据结结构( 构( Data Structure Data Structure ) ) 主讲:严冬梅第第3 3章章栈与队列( 栈与队列( Stack & Queue Stack & Queue ) ) 第3章栈与队列? 栈? 栈的结构特点和操作? 栈的表示和操作的实现? 栈的应用举例? 栈与递归的实现* ? 队列? 队列的结构特点和操作? 队列的表示和操作的实现? 队列的应用举例 栈? 栈的结构特点与操作?栈( stack )是限定只能在一端进行插入和删除操作的线性表。其中允许进行插入和删除的一端称为“栈顶( top )”,另一端称为“栈底( bottom )”。数据元素个数为零的栈是“空栈”?栈是一种“先进后出(FILO) ”(“后进先出(LIFO) ”)的线性表。?例:假设栈中元素以( a 1,a2, …,a n)的顺序进栈,出栈的第一个元素是 a n。a 1a 2…栈顶栈底进栈出栈 a n 出栈的第一个元素为栈顶元素 a n… a 2a 1 栈的基本操作栈的抽象数据类型定义: ADT Stack { 数据对象: D={a i| a i∈ElemSet, i=1,2,...,n, n ≥0} 数据关系: R1={< a i-1, a i >|a i-1, a i ∈D, i=2,...,n} 约定 a n端为栈顶, a 1端为栈底基本操作: InitStack(&S) :构造一个空栈 S ; DestoryStack(&S) :销毁一个已存在的栈 s; ClearStack(&S) :将栈 s清为空栈; StackLength(&S) :返回 s的元素个数; more StackEmpty (S):判断栈 S是否为空,为空返回“ TRUE ”,否则,返回“ FALSE ”; Push(&S ,e):将新元素 e插入作为栈 S的栈顶。 Pop ( &S , &e ):删除 S的栈顶元素,并用 e返回其值。 GetTop (S, &e ):用 e返回栈顶元素, S保持不变。 StackTraverse (S):从栈底到栈顶依次输出 S 中的各个元素。}// ADT Stack 栈的基本操作 栈的表示和操作的实现?栈有两种表示方法: 顺序栈和链栈。? 顺序栈?用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,并附设一栈顶指针 Top 指示栈顶元素在顺序栈中的位置。?顺序栈通常用一维数组来实现,并预设一最大数组空间,并且还可以根据需要设一个增补量。 顺序栈?栈的顺序存储表示 const STACK_INT_SIZE=100;// 初始分配的最大空间量 const STACKINCREMENT=10;// 增补空间量 typedef struct { SElemType * elem; // 存储空间的基地址 int top; //栈顶指针 int stacksize;// 当前分配的最大容量 int incrementsize;// 约定的增补空间}SqStack; // stacksize 和 incrementsize 以 SElemType 为单位?用C做描述语言时,通常以 top=-1 表示顺序栈为空。 顺序栈 Status InitStack_Sq (SqStack & , int = STACK_INT_SIZE, int = STACKINCREMENT) ; Status CreatStack_Sq(SqStack & ,ElemType [], int ); //Status CreatStack_Sq(SqStack &, int); Status StackEmpty_Sq ( SqStack ); int StackLength_Sq ( SqStack ); Status Push_Sq( SqLisst & , int , ElemType); Status incrememt(SqStack & ); Status Pop_Sq(SqLisst & , int , ElemType & ); Status GetTop_Sq(SqStack, SElemType & e) void StackTraverse(SqStack); void DestroyStack_Sq (SqStack & ); 顺序栈?基本操作的实现?初始化操作 void In