文档介绍：1第四章栈与队列? 栈? . 1栈的结构特点和操作? . 2栈的表示和操作的实现? 栈的应用举例? 队列? 队列的结构特点和操作? 队列的表示和操作的实现? 队列的应用举例 2 栈? 栈的结构特点与操作?栈( stack )是限定只能在一端进行插入和删除操作的线性表。其中允许进行插入和删除的一端称为“栈顶( top )”,另一端称为“栈底( bottom )”。数据元素个数为零的栈是“空栈”?栈是一种“先进后出( LIFO )”的线性表。?例:假设栈中元素以( a 1 ,a2, …,a n)的顺序进栈,出栈的第一个元素是 a 1a 2…栈顶栈底进栈出栈 a n 出栈的第一个元素为栈顶元素a n… a 2a 13 在应用中,常用的栈的基本操作有: ? InitStack (&s): 构造一个空栈 S ; ? DestoryStack (&s): 销毁一个已存在的栈 s; ? ClearStack (&s): 将栈 s清为空栈; ? StackLength (s): 返回 s的元素个数; ? StackEmpty (S): 判断栈 S是否为空,为空返回“ TRUE ”,否则,返回“ FALSE ”; 栈的基本操作 4 ? Push(&S ,e): 将新元素 e插入作为栈S的栈顶。? Pop ( &S , &e ): 删除 S的栈顶元素, 并用 e返回其值。? GetTop (S, &e ): 用e返回栈顶元素, S保持不变。? StackTraverse (S): 从栈底到栈顶依次输出 S中的各个元素。 栈的基本操作 5 栈的表示和操作的实现?栈有两种表示方法: 顺序栈和链栈。? ?用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,并附设一栈顶指针 Top 指示栈顶元素在顺序栈中的位置。?顺序栈通常用一维数组来实现,并预设一最大数组空间,并且还可以根据需要设一个增补量。 6 ?栈的顺序存储表示 Const STACK_INT_SIZE=100;// 初始分配的最大空间量 Const STACKINCREMENT=10;// 增补空间量 Typedef struct { SElemType * elem ; // 存储空间的基地址 int top;// 栈顶指针 int satcksize ;// 当前分配的最大容量 int incrementsize ;// 约定的增补空间} Sqstack ; // stacksize 和 incrementsize 以 SElemType 为单位?用C做描述语言时,通常以 top=-1 表示顺序栈为空。 7 ?基本操作的实现?初始化操作 void InitStack _Sq ( Sqstack &S, int maxsize = STACK_INIT_SIZE, int incresize = STACKINCREMENT) { //构造一个最大容量为 maxsize 的顺序栈 S. elem = new SElemType [ maxsize ]; =-1; S. stacksize = maxsize ; S. incrementsize = incresize ; } // Initstack _Sq ?复杂度为 O(1) 8 ?取栈顶元素 bool GetTop _Sq ( SqStack S, SElemType &e) { // 若栈不空,用 e返回 S的栈顶元素,并返回 TRUE ,否则返回 FALSE if(==-1) return FALSE; e=S. elem []; return TRUE; } e= “数据结构” C语言数据结构 C语言数据结构 9 ?将新元素压入栈中的操作: void Push_Sq( SqStack &S, SElemType e) {// 将新元素 e压入栈中作为新的栈顶元素 if(==S. stacksize ) incrementStacksize (S) ; // 若栈已满,则重新分配存储空间,并追加 S. incrementsize 个元素空间。 S. elem [++]=e; }// Push_Sq 10 例:已知顺序栈 S如图所示, x= “数据结构”执行 push(S,x )后的结果为: 执行后