栈和队列.ppt

文档介绍：n n栈栈( Stack ) ( Stack ) n n队列队列( Queue ) ( Queue ) n n小结小结栈栈( Stack ) ( Stack ) n n只允许在一端插入和删除的顺序表只允许在一端插入和删除的顺序表 n n允许插入和删除允许插入和删除的一端称为的一端称为栈顶栈顶( ( top top ) ), ,另一端称另一端称为为栈底栈底( ( bottom bottom ) ) n n特点特点后进先出后进先出( ( LIFO LIFO ) ) template <class Type> class Stack { public: Stack ( int =10 ) ; //构造函数 void Push ( const Type & item ) ; //进栈 Type Pop ( ) ; //出栈 Type GetTop ( ) ; //取栈顶元素 void MakeEmpty ( ) ; //置空栈 int IsEmpty ( ) const; //判栈空否 int IsFull ( ) const; //判栈满否} 栈的抽象数据类型栈的抽象数据类型# include <> template <class Type> class Stack { public: Stack ( int =10 ) ; //构造函数~ Stack ( ) { delete [ ] elements ; } //析构函数 void Push ( const Type & item ) ; //进栈 Type Pop ( ) ; //出栈 Type GetTop ( ) ; //取栈顶 void MakeEmpty ( ) { top = -1; } //置空栈 int IsEmpty ( ) const { return top == -1;} 栈的数组表示栈的数组表示——顺序栈顺序栈 int IsFull ( ) const { return top == maxSize -1;} private: int top ; //栈顶数组指针 Type * elements ; //栈数组 int maxSize ; //栈最大容量} template <class Type> Stack <Type>:: Stack ( int s ): top (-1), maxSize (s ) { elements = new Type [ maxSize ]; assert ( elements != 0 ) ; //断言} 进栈示例进栈示例退栈示例退栈示例 template <class Type> void Stack <Type>:: Push ( const Type & item ) { assert (! IsFull ( ) ) ; //先决条件断言 elements [ ++top ] = item ; //加入新元素} template <class Type> Type Stack <Type>:: Pop ( ) { assert (! IsEmpty ( ) ) ; //先决条件断言 return elements [ top-- ] ; //退出栈顶元素} template <class Type> Type stack <Type>:: GetTop ( ) { assert (! IsEmpty ( ) ) ; //先决条件断言 return elements [ top ] ; //取出栈顶元素}双栈共享一个栈空间双栈共享一个栈空间栈的链接表示栈的链接表示——链式栈链式栈 n n链式栈无栈满问题,空间可链式栈无栈满问题,空间可扩充扩充 n n插入与删除仅在栈顶处执行插入与删除仅在栈顶处执行 n n链式栈的栈顶在链头链式栈的栈顶在链头 n n适合于多栈操作适合于多栈操作