辛运帏全套配套课件数据结构与算法 DSChapter04.ppt

《辛运帏全套配套课件数据结构与算法 DSChapter04.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章栈、队列和数组4.1栈4.2队列4.3数组4.1栈栈栈（stack）是限定仅在一端进行插入和删除的线性表。能进行插入和删除的这一端称为栈顶（top），表的另一端称为栈底（bottom）。插入和删除元素都要涉及栈顶，因此栈顶是栈的最重要的概念。在栈顶插入一个元素称为压栈（push）或入栈，从栈顶删除一个元素称为出栈（pop）。当我们用原来线性表的记号来表示栈的时候，栈可以写为：S=(a0,a1,…,an-1)当指定an-1那一端为栈顶的时候，另一端a0就是栈底。当n=0时，称为空栈。入栈时按a0,a1,…,an-1的次序入栈，而出栈时次序刚好相反，先退出an-1，然后才能退出an

2、-2，最后退出a0。所以栈又称为后进先出（LIFO，LastInFirstOut）结构。和线性表一样，实现栈的方法有许多种，下面介绍两种方法：顺序栈和链式栈，它们分别对应于顺序表和单链表，但实现起来更简单些。下面给出栈的抽象数据类型描述：栈的抽象数据类型描述抽象数据类型stack{实例元素的线性表一端为栈底，另一端为栈顶操作Create():创建一个空栈isEmpty():如果栈为空，则返回TRUE，否则返回FALSEIsFull():如果栈满，则返回TRUE，否则返回FALSETop():返回栈顶元素Add(x):向栈中添加元素xDelete(x):删除栈顶元素，并将它传送给

3、x}4.1.1顺序栈顺序栈用数组实现的栈。实现中使用数组listarray保存栈中各元素，listarray说明为私有类型，实现了对栈的封装，这意味着对这个数组的访问只能通过类中定义的方法push()、pop()、topValue()等进行，从而保证栈中数据的合法性。顺序栈的具体实现如下：classstack{//基于数组的栈类private:intsize;//栈的最大容量inttop;//栈顶元素的下标ELEM*listarray;//保存栈元素的数组public:stack(constintsz=LIST_SIZE)//构造函数：初始化{size=sz;top=0;lista

4、rray=newELEM[sz];}~stack();//析构函数：释放数组占用空间{delete[]listarray;}voidclear()//从栈中清除所有元素{top=0;}voidpush(constELEM&item)//将元素item压入栈中{assert(top

5、tarray[top-1];}boolisEmptyconst//如果栈为空则返回TRUE{returntop==0;}};4.1.2链式栈链式栈它简单地利用单链表，其运算只是在表的一端进行插入和删除。唯一需要考虑的问题是将单链表的哪一端看作栈顶，若将表尾看成栈顶，则每次进栈（压栈）和出栈时，都要从表头找到表尾，其时间开销为O(n)（n为表中元素个数）。若将栈顶设在表头，则进出栈的时间开销仅O(1)。stack……a1a2an^栈顶栈底stack^空栈图4.1用单链表表示栈classstack{//链式栈类private:link*top;//指向栈顶元素的指针public:

6、stack(constintsz=LIST_SIZE)//构造函数：初始化{top=NULL；}~stack(){clear();}//析构函数：返回一切元素ELEMvoidclear();//从栈中清除所有元素ELEMvoidpush(constELEM&item){//将元素item压入栈中top=newlink(item,top)};ELEMpop();//从栈顶弹出元素ELEMtopValue()const//获得栈顶元素的值{assert(!isEmpty());returntop->element;}boolisEmpty()const//如果栈为空则返回TRUE

7、{returntop==NULL;}};voidstack::clear(){//从栈中清除所有元素while(top!=NULL)//返回链的所有结点给以可利用空间表{link*temp=top;top=top->next;deletetemp;}}ELEMstack::pop(){//从栈顶弹出元素assert(!isEmpty());ELEMtemp=top->element;link*ltemp=top->next;deletetop