《数据结构与算法分析lecture4(栈)》由会员分享，可在线阅读，更多相关《数据结构与算法分析lecture4(栈)（25页珍藏版）》请在金锄头文库上搜索。
1、Stacks(栈)l栈是只允许在同一端进行插入和删除运算 的线性表。允许插入和删除的那一端称为 栈顶，另一端为栈底。若有栈lS = (s0,s1,sn-1)l则s0为栈底结点，sn-1为栈顶结点。l栈的结点插入为进栈l栈的结点删除为出栈l栈具有后进先出(LIFO)的特性S0S1.Sn-1进栈进栈出栈栈栈顶栈顶栈栈底2003-8-251Lecture notes01MAXN-1top 01MAXN-1top(a) 栈结构示意图(b) 栈空(c) 栈满2003-8-252Lecture notesArray-Based Stacks(顺序栈)l可以用顺序存储线性表来表示栈， 为了指明当前执行插入和
2、删除运算 的栈顶位置，需要一个游标变量 top(习惯称为栈顶指针)，top指出 栈顶表元在数组中的下标。始终指 向待插入元素的位置。ltop是下一次进栈时，进栈表元 要存入的数组元素下标。当栈为空 时，top=0；栈满时，top=MAXN（ 数组元素个数），如图中的(b)和(c) 。a2a1a1a2top2003-8-253Lecture notesl进栈:l首先把进栈表元存入以top为下标的数组 元素中，然后top加1，使top变为下一次 进栈表元在数组中的下标。l出栈:l首先执行top减1，然后把以top为下标的 栈顶表元送到接受出栈表元的变量中。 同样限制在栈空时，不能再出栈；在栈 满时
3、，不能再入栈。2003-8-254Lecture notesArray-based stack class implementation(顺序栈类的实现)l/Array-based stack class implementationlTemplate class AStack:public Stackll private:l int size;/Maximum size of stackl int top;/Index for top elementl /Array holding stack elements l Elem *listArray; 表示栈中的第 一个空闲位置 2003-8-
4、255Lecture noteslpublic:l AStack(int sz=DefaultListSize)l /Constructorl size = sz;l top = 0;l listArray = new Elemsz;l l /Destructorl AStack() delete listArray; l void clear() top = 0; 2003-8-256Lecture noteslbool push(const Elem/Stack is fulll else listArraytop+ = item;return true; llbool pop(Eleml
5、 else it = listArray-top; return true; ll 2003-8-257Lecture notesl bool topvalue(Eleml else l l it = listArraytop-1;l return true;l l l int length() const return top;l;2003-8-258Lecture notesAn array-based stack storing variable-length strings.每个位置存储一个字符或一个整数，该整 数说明栈中位于其左边的字符串长度。a b c3lhleo50 1 2 3
6、4 5 6 7 8 9 10 top=102003-8-259Lecture notesLinked Stacks(链式栈)l即用链表来实现栈。l链表的第一个表元是栈 顶结点，链表的末尾表 元是栈底结点。l链表的首表元指针就是 栈顶指针top，top为 NULL的空链表是空栈。 xtop栈底2003-8-2510Lecture notesl链栈则没有上溢的限制，它就象是一条 一头固定的链子，可以在活动的一头自 由地增加链环(结点)而不会溢出，链栈不 需要在头部附加头结点，因为栈都是在 头部进行操作的，如果加了头结点，等 于要在头结点之后的结点进行操作，反 而使算法更复杂，所以只要有链表的头 指
7、针就可以了。2003-8-2511Lecture notesLinked stack class implementationl/Link list-based stack implementation lTemplate class Lstack:public StacklPrivate:l Link* top;/pointer to first elementl int Size;/count number of elements指向链式栈第 一个结点（栈 顶）的指针2003-8-2512Lecture noteslPublic:l LStack(int sz = DefaultListS
8、ize)l l top = NULL;l size = 0;l l Lstack() clear(); /Destructorl 2003-8-2513Lecture noteslVoid clear()l l while(top != NULL) /delete link nodesl Link* temp = top;l top = top-next;l size = 0;l delete temp;l l2003-8-2514Lecture noteslbool push(const Eleml size+;l return true;lbasetop2003-8-2515Lecture
9、 noteslbool push(const Eleml size+;l return true;litembas eto pto p2003-8-2516Lecture noteslbool pop(Eleml it = top-element;l Link* ltemp = top-next;l delete top;l top = ltemp;l size-;l return true;l2003-8-2517Lecture notesl bool topValue(Eleml it = top-element;l return true;l l int length() const r
10、eturn size; l;2003-8-2518Lecture notesComparison of Array-Based and Linked StackslThe array-based stack :a fixed-size l array initially,waste spacelThe linked stack:can shrink and grow,l the overhead of a link field for everyl element.2003-8-2519Lecture noteslTwo stacks implemented within in a singl
11、e array,both growing toward the middle.top1top22003-8-2520Lecture notesImplementing Recursion (递归的实现)l栈的最广泛应用：子程序调用 Currptr 调用fact(4)Currptr 返回6返回24 1 4 Currptr 调用fact(3)Currptrn 2 3 1 4 Currptr 调用fact(2)CurrptrCurrptrnn返回2 1 4 CurrptrCurrptrn 3 2 2 3 1 4 Currptr 调用fact(1)CurrptrCurrptrCurrptrnnn返回1
12、 2 3 1 4 CurrptrCurrptrCurrptrnn2003-8-2521Lecture notes递归算法1 (n=0,1) n! = n(n-1)！ ( n1 )2003-8-2522Lecture notesl例：用栈实现递归 Long fact(int n,Stack/load up the stacklong result=1;/holds final resultint val;/holds current valuewhile(s.pop(val) result = result*val;/computereturn result; 2003-8-2523Lectur
13、e notes以求4的阶乘为例：fac(4)=4*fac(3)fac(3)=3*fac( 2)fac(2)=2*fac( 1)fac(1)=1fac(4)=4*3*2*1fac(2)=2*1fac(3)=3*2*1下推回代2003-8-2524Lecture notes利用栈实现递归调用主程序(1)输出f(4);4f (4);top(2) s=4*f(3)n(1 ) 43f (3);（2）n=3 （1）n=4 top(3) s=3*f(2)n2f (2);（3）n=2 （2）n=3 （1）n=4 top(4)s=2*f(1)n 1（4）n=1 （3）n=2 （2）n=3 （1）n=4 topss=3*2*1;(2) 3 (1) 4tops=2*1(3) 2 (2) 3 (1) 4top（1）n=4s=4*3*2*1 top返回(3) 2 (2) 3 (1) 4top (4) 1结束输出242003-8-2525Lecture notes
