栈的抽象数据类型 25栈( stack) plate <class ELEM> class Stack 算集为: 栈:限制访问端口的线性 LIF0寝 该实例消亡 Push:元章插入,“压入 Pop:元素删除,弹出 void push( ELEM item);∥item压入栈项 Top:表首被称为栈顶 ELEM Popo;∥返回栈顶内容,并从栈顶弹出 ELEM GetTop0;∥返回栈顶内容,但不弹出 Begrime 4 bool IsEmptyo; ∥若找已空返回 bool SuLlo;∥若梭已满返回真,顺序栈有用 栈顶」 最大长度 int length: ∥当前栈长 真太血张写 大血张體 新有食究 栈的实现 21顺序栈 template <class ELEM> 顺序栈 使用向量实现 ○链式栈 ELEM* EImList;∥存放据元章微組 用单链表方式存储,其中指针的方向 ∥校顶在的位置,即下标值 是从栈顶向下链接 MansiZe;∥栈的最大长度 构建栈的实例,向量空间长度为size 栈的应用计算表达式的值 栈与递归 ∥其他运算同视ADT CK back 真太张铭写 魏张写 新究 顺序栈 顺序栈的创建 ∥实例的创建,指定最大长度100。在类的内部实 laxsIzesize ∥开辟向量存储空间 size 5 栈顶 ElmList-new ElEM maxsize 判晰nw命令成功否,否则断言程序异常 sert(ElmList -NULL): ∥表示栈空 back 真大带酱张储 北大管息歌张帖习6 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 31 back next 2.5 栈(stack) 栈：限制访问端口的线性表 LIFO表 „ Push：元素插入 ，‘压入’ „ Pop：元素删除，‘弹出’ „ Top：表首被称为‘栈顶’ 1 2 3 4 栈底 栈顶 栈最大长度 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 32 back next 栈的抽象数据类型 template <class ELEM> class Stack { // 栈的运算集为： Stack(int sz); //创建栈的实例 ~Stack(); //该实例消亡 void Push(ELEM item); // item压入栈顶 ELEM Pop(); // 返回栈顶内容，并从栈顶弹出 ELEM GetTop(); // 返回栈顶内容，但不弹出 void ClearStack(); // 变为空栈MakeEmpty(); bool IsEmpty(); // 若栈已空返回真 bool IsFull(); // 若栈已满返回真，顺序栈有用 int length(); // 当前栈长 }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 33 back next 栈的实现 „ 顺序栈 „ 使用向量实现 „ 链式栈 „ 用单链表方式存储，其中指针的方向 是从栈顶向下链接 „ 栈的应用--计算表达式的值 „ 栈与递归 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 34 back next 2.5.1 顺序栈 template <class ELEM> class Stack { private: ELEM *ElmList; // 存放数据元素数组 int top; // 栈顶在的位置，即下标值 int maxsize; // 栈的最大长度 //构建栈的实例，向量空间长度为size Public: Stack(int size); // 其他运算同栈ADT … }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 35 back next 顺序栈 栈顶 5 4 8 7 1 element [0] [1] [2] [3] [4] max_size - 1 size = 5 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 36 back next 顺序栈的创建 //栈实例的创建，指定最大长度100。在类的内部实现 Stack(int size=100) { maxsize=size; //开辟向量存储空间 ElmList=new ELEM[maxsize]; //判断new命令成功否，否则断言程序异常 assert(ElmList!=NULL); top=-1; // 表示栈空 }