《数据结构A》第03章

《《数据结构A》第03章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构DataStructuresinC++南京邮电大学计算机学院2006年9月第3章堆栈和队列南京邮电大学计算机学院2006年9月3.1   堆栈3.2   队列3.3  表达式计算3.4   递归南京邮电大学计算机学院2006年9月3.1堆栈南京邮电大学计算机学院2006年9月3.1.1堆栈ADT堆栈（或栈stack）是限定插入和删除运算只能在同一端进行的线性数据结构。南京邮电大学计算机学院2006年9月栈是后进先出（last-in-first-outLIFO）的动态线性数据结构.允许插入和删除元素的一端

2、称为栈顶，另一端称为栈底。若栈中无元素，则称为空栈。S=(a0,a1,…,an-1)南京邮电大学计算机学院2006年9月ADTStack{数据:零个或多个元素的线性序列（a0,a1,...,an-1),其最大允许长度为ＭaxStackSize。对于它插入和删除运算都限制在同一端进行，并遵循LIFO原则。运算:Create()：建立一个空栈。Destroy()：撤消一个栈。南京邮电大学计算机学院2006年9月IsEmpty()：若栈空，则返回true;否则返回false。IsFull()：若栈满，则返回true;

3、否则返回false。Top(x)：返回栈顶元素。若操作成功，则返回true;否则返回false。Push(x)：在栈顶插入元素x。Pop()：从栈中删除栈顶元素。Clear():清除堆栈中全部元素。};南京邮电大学计算机学院2006年9月程序3-1栈的C++类templateclassStack{public:virtualboolIsEmpty()const=0;virtualboolIsFull()const=0;virtualboolTop(T&x)const=0;virtualboolP

4、ush(Tx)=0;virtualboolPop()=0;virtualvoidClear()=0;};南京邮电大学计算机学院2006年9月3.1.2堆栈的顺序表示一维数组s存储栈中元素，maxTop+1为最大允许容量，top指示栈顶，top==-1表示空栈,top==maxTop表示栈满。S=(a0,a1,…,an-1)南京邮电大学计算机学院2006年9月templateclassSeqStack:publicStack{public:SeqStack(intmSize);~SeqSta

5、ck(){delete[]s;}voidClear(){top=-1;}南京邮电大学计算机学院2006年9月boolIsEmpty()const{return(top==-1);}boolIsFull()const{return(top==MaxTop);}boolTop(T&x)const;boolPush(Tx);boolPop();private:inttop;//总是指向栈顶元素intmaxTop;T*s;}南京邮电大学计算机学院2006年9月templateSeqStack::S

6、eqStack(intmSize){maxTop=mSize−1;s=newT[mSize];top=−1;}南京邮电大学计算机学院2006年9月templateboolSeqStack::Push(Tx){if(IsFull()){//溢出处理cout<<"Overflow"<boolSeqStack::Pop(){if(IsEmp

7、ty()){//空栈处理cout<<"Underflow"<boolSeqStack::Top(T&x)const{if(IsEmpty()){cout<<"Empty"<

8、学计算机学院2006年9月3.2.1队列ADT队列是限定只能在其中一端插入元素，而在另一端删除元素的线性数据结构。（动态数据结构）南京邮电大学计算机学院2006年9月队列是先进先出（firstt-in-first-outFIFO）的动态线性数据结构允许插入元素的一端称队尾，允许删除元素的另一端称队头。若队列中无元素，则称为空队列。S=(a0,a1,…,an-1)南京邮电大学计算机学院2