数据结构之栈对列串课件.ppt

数据结构 第三章 栈 对列 串 要 求 熟练掌握以下内容： 堆栈的特征、基本运算并能设计简单算法 队列、循环队列的特征、基本运算并能设计简单算法 串的定义和应用 了解以下内容： 线性表运算时间复杂性分析 堆栈、队列实际应用 3.1 堆栈(Stack) 堆栈也简称为栈，是限定在表的一端进行插入或删除操作的线性表。 进行插入或删除操作的一段称为栈顶（top），另一端称为栈底（bottom）。 插入元素又称为入栈（push），删除元素操作称为出栈（pop）。 不含元素的栈称为空栈。 堆栈元素的插入和删除只在栈顶进行，总是后进去的元素先出来，所以堆栈又称为后进先出线性表或LIFO（Last-In-First-Out）表。 堆栈的表示 堆栈的最简单的表示方法是采用一维数组，为形象起见，一般在图中将堆栈画成竖直的 。 设数组名为STACK，其下标的下界为1，上界为n。 一般需用一个变量top记录当前栈顶的下标值，top也叫做栈指针。 本例中top=4 栈的基本运算 进栈 push(s,x) 出栈 pop(s) 取栈顶元素 gettop(s) 判断栈空 emptystack(s) 置空栈 setstacknull 求栈的长度 stacklen(s) 栈的遍历 stacktraverse(s) 1. 入栈（push） 入栈的主要操作是先将栈顶指针加1； 然后将入栈元素放到栈顶指针所指示下标值的位置上。 设用下标从1到n的数组ST表示堆栈，入栈的元素值为G，则可得到入栈函数如下： 栈的顺序存储结构 用一个一维数组作栈，加一个指针。 其定义如下： #define maxsize 允许的最大元素个数 Typedef struct { elementtype elenents[maxsize]; Int top; } stacktype; 入栈函数 int push (stacktype s, elementtype x) { if (s.top==maxsize-1) { printf(“栈溢出!\n”); /*栈满*/ return(-1) } s. top++; s.elements[s.top]=x; return(0); } 2. 出栈（Pop） 出栈运算时，先将栈顶的元素值赋给某个变量，以备后面的运算应用； 然后栈顶指针减1，将栈顶位置下移。 假设已指定的变量为*p，则出栈的函数如下： 出栈函数 Int pop (stacktype s, elementtype *p) { if (s.top== -1) printf(“空栈!\n”); /*栈为空*/ p=s.elements[s.top]; s.top--; return(0); } 例3.1 一个双向栈是将两个栈用一个数组构成，它们的栈底分别设在数组的两端。写出以数组高端为底的栈的入栈和出栈的算法。 例3.1解答 这个栈的栈顶指针top2是按相反的方向移动的，因此,在操作时要判断： 入栈时：top2-1=top1 ？ 出栈时：top2=n+1 ? 入栈算法 void push (S, int n, top1, top2, G) { if (top2-1==top1) printf(“溢出!\n”); else { top2=top2-1; S[top2]=G; /*插入新元素*/ } } 出栈算法 void pop (S, int n, top1, top2, x) { if (top2==n+1) printf(“下溢出!\n”); else { x=S[top2]; top2=top2+1; } } 栈的链式存储结构 用一头结点单链表的第一个元素，头结点的指针表示栈顶，若一进栈序列a,b,c, 其链式结构如下： head 其结构定义如下： typedef struct node { elementtype da