41.3链栈—利用链式存贮结构实现的栈 与顺序表一样,顺序栈的最大尺寸( maxSize)也难以确定,大 小了容易溢出,太大了又浪费空间。因此在动态性较强的应用领域, 宜采用链栈。 链栈的结构如下图所示。与单链表相似,但不设头结点,第 个结点即为栈顶。插入(入栈)与删除(出栈)操作均只能在表头 进 栈顶元素 栈底元素 p 当top=NULL时,表示空栈 2021220
2021/2/20 6 4.1.3 链栈——利用链式存贮结构实现的栈 与顺序表一样，顺序栈的最大尺寸（maxSize）也难以确定，太 小了容易溢出，太大了又浪费空间。因此在动态性较强的应用领域， 宜采用链栈。 链栈的结构如下图所示。与单链表相似，但不设头结点，第一 个结点即为栈顶。插入（入栈）与删除（出栈）操作均只能在表头 进行。 当 top = NULL 时，表示空栈 … ^ top 栈顶元素 栈底元素
链栈的定义: 链栈结点类的定义 template< class Type> class stack;∥链栈类的前视声明 template <class Type> class Stack Node friend class Stack <Type 链栈结点结构 rivate data link Type data StackNode <Type>* link StackNode(Type d=0. Stack Node<Type>*1-NULL) data(d)link(){}∥构造函数,初始化一链栈结点 2021220
2021/2/20 7 链栈的定义： 链栈结点类的定义： template <class Type> class Stack; //链栈类的前视声明 template <class Type> class StackNode { friend class Stack <Type>; private: Type data; StackNode <Type> * link; StackNode(Type d=0,StackNode<Type> * l=NULL): data(d),link(l) { } //构造函数，初始化一链栈结点 } data link 链栈结点结构
链栈类的定义: template <class Type> class Stack i publ Stack()top(NULL){}∥构造函数,初始化一个空链栈 Stack() ∥析构函数,释放链栈的所有结点,并使top=NULL。置栈空操作 void Push(const Type item) ∥栈操作 Type Popo //栈操作 Type Get Top( ∥读取栈顶元素 void Make Empty(( top=NULL, /置栈空操作,应先删除栈内所有结点 int IsEmpty() const{ return top=NULL;}∥)判栈空操作 int IsFull( const return 0) /判栈满,在链栈中该操作无意义 privat StackNode<Type>* top ∥栈顶指针 2021220
2021/2/20 8 链栈类的定义： template <class Type> class Stack { public: Stack( ) : top(NULL) { } //构造函数，初始化一个空链栈 ~Stack( ); //析构函数，释放链栈的所有结点，并使top=NULL。置栈空操作 void Push(const Type & item); //入栈操作 Type Pop( ); //出栈操作 Type GetTop( ); //读取栈顶元素 void MakeEmpty( ) { top=NULL;} //置栈空操作，应先删除栈内所有结点 int IsEmpty( ) const {return top == NULL;} //判栈空操作 int IsFull ( ) const {return 0} //判栈满，在链栈中该操作无意义 private: StackNode<Type> * top; //栈顶指针 }
链栈的入栈算法: Template <class Type> void Stack<Type>. Push(const Type item) 将数据元素item入栈 top=new StackNode<Type>(item, top) /创建一个新的链栈结点,并将该结点的data域置为item, link域置为top,最后将该结点的指针赋值给top.参见下图 Pp 原栈顶 ∧ (2) Item 新栈顶 2021220
2021/2/20 9 链栈的入栈算法： Template <class Type> void Stack<Type> :: Push(const Type & item) //将数据元素item 入栈 { top=new StackNode<Type>(item,top); //创建一个新的链栈结点，并将该结点的data 域置为item ， //link 域置为top ,最后将该结点的指针赋值给top .参见下图 } … ^ top 原栈顶 新栈顶 item (1) (2)
比较与思考: (1)比较顺序栈与链栈的类定义 两者的类名相同,均为 Stack 两者成员函数的名、参数、返回类型与规格说明均相同,但 内部的实现有别 假定某大型软件系统原来使用顺序栈,因经常上溢,欲改用链 栈,请问哪些部分需要改动? 2021220
2021/2/20 10 比较与思考： （1）比较顺序栈与链栈的类定义 两者的类名相同，均为Stack 两者成员函数的名、参数、返回类型与规格说明均相同，但 内部的实现有别 假定某大型软件系统原来使用顺序栈，因经常上溢，欲改用链 栈，请问哪些部分需要改动？