数据结构与算法分析lcture4(栈).pptVIP

2003-8-25 Lecture notes Stacks(栈) 栈是只允许在同一端进行插入和删除运算的线性表。允许插入和删除的那一端称为栈顶，另一端为栈底。若有栈 S = (s0,s1,……sn-1) 则s0为栈底结点，sn-1为栈顶结点。 栈的结点插入为进栈 栈的结点删除为出栈 栈具有后进先出(LIFO)的特性 Array-Based Stacks(顺序栈) 可以用顺序存储线性表来表示栈，为了指明当前执行插入和删除运算的栈顶位置，需要一个游标变量top(习惯称为栈顶指针)，top指出栈顶表元在数组中的下标。始终指向待插入元素的位置。 top是下一次进栈时，进栈表元要存入的数组元素下标。当栈为空时，top=0；栈满时，top=MAXN（数组元素个数），如图中的(b)和(c)。 进栈: 首先把进栈表元存入以top为下标的数组元素中，然后top加1，使top变为下一次进栈表元在数组中的下标。 出栈: 首先执行top减1，然后把以top为下标的栈顶表元送到接受出栈表元的变量中。同样限制在栈空时，不能再出栈；在栈满时，不能再入栈。 Array-based stack class implementation(顺序栈类的实现) //Array-based stack class implementation Template class Elem class AStack:public StackElem { private: int size;//Maximum size of stack int top;//Index for top element //Array holding stack elements Elem *listArray; public: AStack(int sz=DefaultListSize) {//Constructor size = sz; top = 0; listArray = new Elem[sz]; } //Destructor ~AStack() { delete [] listArray; } void clear() { top = 0; } bool push(const Elem item) { if(top == size) return false;//Stack is full else { listArray[top++] = item;return true; }  } bool pop(Elem it)//Pop top element { if (top == 0) return false; else { it = listArray[--top]; return true; } } bool topvalue(Elem it) const {//Return top element if (top == 0) return false; else { it = listArray[top-1]; return true; } } int length() const {return top;} }; An array-based stack storing variable-length strings. 每个位置存储一个字符或一个整数，该整数说明栈中位于其左边的字符串长度。 Linked Stacks(链式栈) 即用链表来实现栈。 链表的第一个表元是栈顶结点，链表的末尾表元是栈底结点。 链表的首表元指针就是栈顶指针top，top为NULL的空链表是空栈。 链栈则没有上溢的限制，它就象是一条一头固定的链子，可以在活动的一头自由地增加链环(结点)而不会溢出，链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要在头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。 Linked stack class implementation //Link list-based stack implementation