北京大学：《数据结构与算法》课程教学资源（实验班讲义）第二章 线性表、栈和队列

栈的抽象数据类型 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; // 表示栈空 }

压入栈顶 从栈顶弹出 template <class ELEM> template <class ELEM> void Stack<ELEM>: Push(ELEM item) ELEM Stack<ELEM>: Popo 判非栈满,否则栈溢出,退出运行 判栈非空,否则断言栈空异常退出运行 ssert(sfUll) top++;/栈顶 ElmList topl=item; return ElmListtop-; next back 真太血张写 大血张體 新有食究 从栈顶读取,但不弹出 其他函数 template <class ELEM> ∥函数在类定义之内实现,不用“”修饰 ELEM Stack<ELEM>: GetTopo bool IsEmptyo∥返回真,若栈已空 i return top==-1;3 判栈非空,否则断言栈空异常退出 ∥栈满时,返回非零值(真true) assert( IsEmpty o); bool Is Fullo return top==maxsize-1: return ElmList topl a Clearstacko{top=1;}∥变空栈 StackO{ delete EnlIst;}∥栈消亡 CK bacK 真太张铭写 北盒大管血歌张写 新究 sTL中关于堆栈的函数 252链式栈 其中t。p函数表示取栈项元,并将结果返回给用户 (如果栈不空的话 用单链表方式存储 将果返回 指针的方向从栈顶向下链接 有些库函数提供了这样的函数ptop? Nt2|{3-4Z STL为什么这两个操作分开? 使舞函数之间的合度降低 Top栈顶 back 真大带酱张储 新有,种究 北大管息歌张帖习

7 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 37 back next 压入栈顶 template <class ELEM> void Stack<ELEM>::Push(ELEM item) { //判非栈满，否则栈溢出，退出运行 assert(!IsFull()); top++; //栈顶 ElmList[top]=item; } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 38 back next 从栈顶弹出 template <class ELEM> ELEM Stack<ELEM>::Pop() { //判栈非空，否则断言栈空异常退出运行 assert(!IsEmpty()); return ElmList[top--]; } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 39 back next 从栈顶读取，但不弹出 template <class ELEM> ELEM Stack<ELEM>::GetTop() { //判栈非空，否则断言栈空异常退出 assert(!IsEmpty()); return ElmList[top]; } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 40 back next 其他函数 „ // 函数在类定义之内实现, 不用“::”修饰 „ bool IsEmpty() // 返回真，若栈已空 { return top == -1;} „ // 栈满时，返回非零值（真true） bool IsFull() {return top==maxsize-1;} „ ClearStack() { top=-1; } // 变空栈 „ ~Stack() {delete []ElmList;} // 栈消亡 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 41 back next STL中关于堆栈的函数 „ 其中top函数表示取栈顶元素，并将结果返回给用户 „ pop函数表示将栈顶元素弹出（如果栈不空的话） „ pop函数仅仅是一个操作，并不将结果返回。 „ pointer=aStack.pop()？错误！ „ 有些库函数提供了这样的函数ptop？ „ STL为什么这两个操作分开？ „ 主要是概念上显得清晰 „ 保证一个函数只确定地完成一项特定的功能 „ 使得函数之间的耦合度降低 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 42 back next 2.5.2 链式栈 „ 用单链表方式存储 „ 指针的方向从栈顶向下链接 N 1 2 3 4 Top 栈顶