数据结构ds-03(栈和队列13)

《数据结构ds-03(栈和队列13)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构第三章栈与队列第3章栈和队列本章的基本内容是：两种特殊的线性表——栈和队列从数据结构角度看，栈和队列是操作受限的线性表，他们的逻辑结构相同,是线性结构。从抽象数据类型角度看，栈和队列是两种重要的抽象数据类型。第三章栈与队列栈队列栈的应用：表达式求值栈的应用：递归队列的应用：打印杨辉三角形优先级队列33.1栈(Stack)栈是很常用也很重要的数据结构，用途广泛，句法识别、表达式计算都基于栈来实现，在函数调用时也常使用栈。1.栈的定义退栈进栈只允许在一端插入和删除的线性表。topan允许插入和删除的一端称为栈顶an-1(top)，另一端称栈底(bottom)2.栈的特

2、点bottoma1后进先出(LIFO)4栈的抽象数据类型template//此程序放入stack.hclassStack{//栈的类定义public:Stack(){};//构造函数virtualvoidPush(T&x)=0;//进栈virtualboolPop(T&x)=0;//出栈virtualboolgetTop(T&x)const=0;//取栈顶virtualboolIsEmpty()const=0;//判栈空virtualboolIsFull()const=0;//判栈满virtualintgetSize()const=0;}；53.1.2顺序栈栈有两种典型存

3、储表示，基于数组的存储表示和基于链表的存储表示。用数组表示的栈称为顺序栈，用链表表示的栈称为链式栈。6栈的数组存储表示—顺序栈p3-10123456789maxSize-1elementstop(栈空)7栈的数组存储表示—顺序栈p3-2#include//P89程序3.2#include#include“stack.h”//P88栈的类定义ConstintstackIncrement=20;templateclassSeqStack:publicStack{//顺序栈类定义private:T*elements;//栈元素存

4、放数组inttop;//栈顶指针intmaxSize;//栈最大容量voidoverflowProcess();//栈的溢出处理8栈的数组存储表示—顺序栈p3-3public:SeqStack(intsz=50);//构造函数～SeqStack(){delete[]elements;}//析构函数voidPush(Tx);//进栈书上参数为(constT&x)boolPop(T&x);//出栈boolgetTop(T&x);//取栈顶内容boolIsEmpty()const{returntop==-1;}boolIsFull()const{returntop==maxSize-1;}int

5、getSize()const{returntop+1;}voidmakeEmpty(){top=-1;}};9maxSize=5进栈：topbtopa=1atop空栈=0a进栈b进栈=-1topetope=4d=4dtop=maxSize-1栈满cc栈满再进栈就会溢出bbaae进栈f进栈-溢出10maxSize=5退栈：etopdd=3ctopccb=2btopbaa=1ae退栈d退栈c退栈btopaa=0b退栈topa退栈top空栈=-111栈满、栈空的条件栈空：下标top=-1，表示一个元素都没有栈满：下标top=maxSize-1，此时再入栈会溢出12顺序栈的操作p3-1temp

6、latevoidSeqStack::overflowProcess(){//私有函数：当栈满则执行扩充栈存储空间处理T*newArray=newT[maxSize+stackIncrement];//创建更大的存储数组if(newArray==NULL){cerr<<“失败”<

7、templatevoidSeqStack::Push(Tx){//若栈不满,则将元素x插入该栈栈顶,否则溢出处理if(IsFull()==true)overflowProcess;//栈满elements[++top]=x;//栈顶指针先加1,再进栈};14template顺序栈的操作p3-2boolSeqStack::Pop(T&x){//函数退出栈顶元素并返回栈顶元素的值i