数据结构与算法分析-栈.ppt

1、2003-8-25,Lecture notes,1,Stacks(栈),栈是只允许在同一端进行插入和删除运算的线性表。允许插入和删除的那一端称为栈顶，另一端为栈底。若有栈 S = (s0,s1,sn-1) 则s0为栈底结点，sn-1为栈顶结点。 栈的结点插入为进栈 栈的结点删除为出栈 栈具有后进先出(LIFO)的特性,2003-8-25,Lecture notes,2,0,1,MAXN-1,top,0,1,MAXN-1,top,(a) 栈结构示意图,(b) 栈空,(c) 栈满,2003-8-25,Lecture notes,3,Array-Based Stacks(顺序栈),可以用顺序存储线性

2、表来表示栈，为了指明当前执行插入和删除运算的栈顶位置，需要一个游标变量top(习惯称为栈顶指针，注意与指针变量的区别)，top指出栈顶表元在数组中的下标。始终指向待插入元素的位置。 top是下一次进栈时，进栈表元要存入的数组元素下标。当栈为空时，top=0；栈满时，top=MAXN（数组元素个数），如图中的(b)和(c)。,top,2003-8-25,Lecture notes,4,进栈: 首先把进栈表元存入以top为下标的数组元素中，然后top加1，使top变为下一次进栈表元在数组中的下标。 出栈: 首先执行top减1，然后把以top为下标的栈顶表元送到接受出栈表元的变量中。同样限制在栈空时

3、，不能再出栈；在栈满时，不能再入栈。,2003-8-25,Lecture notes,5,Array-based stack class implementation(顺序栈类的实现),/Array-based stack class implementation Template class AStack:public Stack private: int size;/Maximum size of stack int top;/Index for top element /Array holding stack elements Elem *listArray;,表示栈中的第一个空闲位置,

4、2003-8-25,Lecture notes,6,public: AStack(int sz=DefaultListSize) /Constructor size = sz; top = 0; listArray = new Elemsz; /Destructor AStack() delete listArray; void clear() top = 0; ,2003-8-25,Lecture notes,7,bool push(const Elem ,2003-8-25,Lecture notes,8,bool topvalue(Elem,2003-8-25,Lecture notes

5、,9,An array-based stack storing variable-length strings. 每个位置存储一个字符或一个整数，该整数说明栈中位于其左边的字符串长度。,a,b,c,3,l,h,l,e,o,5,0 1 2 3 4 5 6 7 8 9 10,top=10,2003-8-25,Lecture notes,10,Linked Stacks(链式栈),即用链表来实现栈。 链表的第一个表元是栈顶结点，链表的末尾表元是栈底结点。 链表的首表元指针就是栈顶指针top，top为NULL的空链表是空栈。,top,栈底,2003-8-25,Lecture notes,11,链栈则没

6、有上溢的限制，它就象是一条一头固定的链子，可以在活动的一头自由地增加链环(结点)而不会溢出，链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要在头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。,2003-8-25,Lecture notes,12,Linked stack class implementation,/Link list-based stack implementation Template class Lstack:public Stack Private: Link* top;/pointer to first elem

7、ent int Size;/count number of elements,指向链式栈第一个结点（栈顶）的指针,2003-8-25,Lecture notes,13,Public: LStack(int sz = DefaultListSize) top = NULL; size = 0; Lstack() clear(); /Destructor,2003-8-25,Lecture notes,14,Void clear() while(top != NULL) /delete link nodes Link* temp = top; top = top-next; size = 0; d

8、elete temp; ,2003-8-25,Lecture notes,15,bool push(const Elem ,base,top,2003-8-25,Lecture notes,16,bool push(const Elem ,base,top,2003-8-25,Lecture notes,17,bool pop(Elem ,2003-8-25,Lecture notes,18,bool topValue(Elem,2003-8-25,Lecture notes,19,Comparison of Array-Based and Linked Stacks,The array-ba

9、sed stack :a fixed-size array initially,waste space The linked stack:can shrink and grow, the overhead of a link field for every element.,2003-8-25,Lecture notes,20,Two stacks implemented within in a single array,both growing toward the middle.,top1,top2,2003-8-25,Lecture notes,21,Implementing Recursion(递归的实现),栈的最广泛应用：子程序调用,返回24,2003-8-25,Lecture notes,22,递归算法,1 (n=0,1) n! = n(n-1)！ ( n1 ),2003-8-25,Lecture notes,23,例：用栈实现递归 Long fact(int n,Stack ,2003-8-25,Lecture notes,24,以求4的阶乘为例：,fac(4)=4*fac(3),fac(3)=3*fac( 2),fac(2)=2*fac( 1),fac(1)=1,fac(4)=4*3