《数据结构与算法设计PPT (16).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法设计PPT (16).pdf（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第4章栈和队列4.1 栈及其实现栈和队列 栈和队列都是特殊的线性表 线性表：表中数据元素之间存在线性关系 栈和队列特殊性：-对表的插入和删除的位置受到了限制栈(Stack)的定义 栈-只允许在一端插入和删除的顺序表-允许插入和删除的一端称为栈顶(top)-另一端称为栈底(bottom)-特点：后进先出(LIFO)普通的线性表：插入位置n+1个删除位置1,2,.n栈的操作特点LIFO 输入（插入）顺序 a0,a1,a2.an-1 输出（删除）顺序an-1,an-2,a1,a0 特点：后进先出Last In First Out栈(Stack)的定义 输入 ABC 输出哪一种是可能的？ABC ACB
2、 BAC BCA CAB CBAABC ACB BAC BCA CAB CBAtemplate class Stackpublic:Stack(int=10);/构造函数void Push(const Type&item);/进栈Type Pop();/出栈Type GetTop();/取栈顶元素void MakeEmpty();/置空栈int IsEmpty()const;/判栈空否int IsFull()const;/判栈满否栈的抽象数据类型#include template classStackpublic:Stack(int=10);/构造函数Stack()delete element
3、s;/析构函数voidPush(const Type&item);/进栈Type Pop();/出栈TypeGetTop();/取栈顶voidMakeEmpty()top=-1;/置空栈int IsEmpty()const returntop=-1;栈的数组表示 顺序栈intIsFull()const returntop=maxSize-1;private:inttop;/栈顶数组指针Type*elements;/栈数组intmaxSize;/栈最大容量template Stack:Stack(int s):top(-1),maxSize(s)elements=new TypemaxSize;
4、assert(elements!=0);/断言栈的数组表示 顺序栈栈的数组表示 初始化、入栈top=-1543210MaxSize-1elementtop=3543a32a21a10a0MaxSize-1判空 top=-1 求个数 top+1栈的数组表示 出栈elementtop=3543a32a21a10a0MaxSize-1判满 top=MaxSizeelementtop=25432a21a10a0MaxSize-1template voidStack:Push(const Type&item)assert(!IsFull();/先决条件断言elements+top=item;/加入新元素
5、template Type Stack:Pop()assert(!IsEmpty();/先决条件断言return elementstop-;/退出栈顶元素栈的数组表示 入栈出栈实现template Type stack:GetTop()assert(!IsEmpty();/先决条件断言returnelementstop;/取出栈顶元素栈的数组表示 取栈顶元素栈的链接表示 链式栈 链式栈用链表存储无栈满问题，空间可扩充 插入与删除仅在栈顶处执行 一般用不带头节点的单链表表示 链式栈的栈顶在链头栈的链接表示 链式栈a3a2a1a0 空栈非空栈判空 top=NULLtopNULLtop栈的链接表示
6、入栈操作a3a2a1a0topa3a2a1a0 xtop栈的链接表示 出栈操作a3a2a1a0topa2a1a0toptemplate classStack;template class StackNodefriend class Stack;private:Type data;/结点数据StackNode*link;/结点链指针StackNode(Type d=0,StackNode*l=NULL):data(d),link(l);链式栈(LinkedStack)类的定义template classStack public:Stack():top(NULL)Stack();voidPush(
7、const Type&item);TypePop();Type GetTop();void MakeEmpty();/实现与Stack()同int IsEmpty()const returntop=NULL;private:StackNode*top;/栈顶指针链式栈(LinkedStack)类的定义template Stack:Stack()StackNode*p;while(top!=NULL)/逐结点回收p=top;top=toplink;deletep;template void Stack:Push(const Type&item)top=new StackNode(item,top);/新结点链入top之前,并成为新栈顶链式栈(LinkedStack)类的定义template Type Stack:Pop()assert(!IsEmpty();StackNode*p=top;Typeretvalue=pdata;/暂存栈顶数据top=toplink;/修改栈顶指针deletep;returnretvalue;/释放,返回数据template Type Stack:GetTop()assert(!IsEmpty();returntopdata;链式栈(LinkedStack)类的定义