南京邮电大学数据结构A第3章

数据结构A·第3章第3章堆栈和队列引言堆栈和队列也是最常见的数据结构，在算法设计中经常使用，它们在逻辑上同线性表一样，都是线性结构，差别在于：线性表可以在表的任意位置插入和删除元素，而堆栈和队列只能在表的端点插入和删除元素。第3章堆栈和队列内容提要1、定义堆栈与队列抽象数据类型2、讨论堆栈与队列的顺序表示方法3、讨论堆栈与队列的链接表示方法4、以表达式计算为例讨论堆栈的应用5、介绍递归的概念和递归算法3.1堆栈a0a1…ai…an-1入栈出栈bottomtop图3-1栈的示意图堆栈（简称栈）的示意图S=(a0,a1,…,an-1)课堂提要第3章堆栈和队列3.1堆栈3.2队列3.3表达式的计算3.4递归3.1堆栈3.1.1堆栈抽象数据类型堆栈是后进先出（LastInFirstOut——LIFO）的动态线性数据结构。1.堆栈的定义堆栈工作的演示ACB3.1堆栈3.1.1堆栈抽象数据类型同时，堆栈也是是后进先出（LastInFirstOut——LIFO）的动态线性数据结构。1.堆栈的定义ACB堆栈工作的演示3.1堆栈3.1.1堆栈抽象数据类型ADTStack{数据:0个或多个元素的线性序列（a0,a1,...,an-1),其最大允许长度为ＭaxStackSize。其插入和删除运算都限制在同一端进行，并遵循LIFO原则。运算:Create()：建立一个空栈。Destroy()：撤消一个栈。IsEmpty()：若栈空，则返回true;否则返回false。IsFull()：若栈满，则返回true;否则返回false。Top(x)：返回栈顶元素。若操作成功，则返回true;否则返回false。Push(x)：在栈顶插入元素x。Pop()：从栈中删除栈顶元素。Clear():清除堆栈中全部元素。}2.栈的抽象数据类型3.1堆栈3.1.1堆栈抽象数据类型3.栈的C++模板抽象类程序3-1堆栈的C++类#includeiostream.htemplateclassTclassStack{public:virtualboolIsEmpty()const=0;virtualboolIsFull()const=0;virtualboolTop(T&x)const=0;virtualboolPush(Tx)=0;virtualboolPop()=0;virtualvoidClear()=0;};3.1堆栈3.1.2栈的顺序表示1.栈的顺序表示法an-1a1a0topn-110栈s图3-2顺序栈maxTop………一维数组s存储栈中元素，maxTop+1为最大允许容量，top指示栈顶，top==-1表示空栈,top==maxTop表示栈满。S=(a0,a1,…,an-1)3.1堆栈3.1.2栈的顺序表示2.顺序栈类templateclassTclassSeqStack:publicStackT{public:SeqStack(intmSize);~SeqStack(){delete[]s;}boolIsEmpty()const{return(top==-1);}boolIsFull()const{return(top==MaxTop);}boolTop(T&x)const;boolPush(Tx);boolPop();voidClear(){top=-1;}private:inttop;//总是指向栈顶元素intmaxTop;T*s;}an-1a1a0topn-110栈s图3-2顺序栈maxTop………3.1堆栈3.1.2栈的顺序表示3.动态一维数组描述顺序栈类an-1a1a0topn-110栈s图3-2顺序栈maxTop………templateclassTclassSeqStack:publicStackT{public:……private:intmaxTop;inttop;T*s;}3.1堆栈3.1.2栈的顺序表示3.动态一维数组描述顺序栈类an-1a1a0topn-110栈s图3-2顺序栈maxTop………构造函数templateclassTSeqStackT::SeqStack(intmSize){maxTop=mSize-1;s=newT[mSize];top=-1;}析构函数SeqStackT::~SeqStack(intMaxSize){delete[]s;}3.1堆栈3.1.2栈的顺序表示4.在顺序存储表示下实现栈上定义的操作an-1a1a0topn-110栈s图3-2顺序栈maxTop………（1）取栈顶元素templateclassTboolSeqStackT::Top(T&x)const{if(IsEmpty()){//空栈处理coutEmptyendl;returnfalse;}x=s[top];returntrue;}3.1堆栈3.1.2栈的顺序表示4.在顺序存储表示下实现栈上定义的操作an-1a1a0topn-110栈s图3-2顺序栈maxTop………（2）进栈（压入）templateclassTboolSeqStackT::Push(T&x){if(IsFull()){//溢出处理coutOverflowendl;returnfalse;}s[++top]=x;returntrue;}3.1堆栈3.1.2栈的顺序表示4.在顺序存储表示下实现栈上定义的操作an-1a1a0topn-110栈s图3-2顺序栈maxTop………（3）出栈（弹出）templateclassTboolSeqStackT::Pop(){if(IsEmpty()){//空栈处理coutUnderflowendl;returnfalse;}top--;returntrue;}3.1堆栈3.1.3栈的链接表示1.栈的链接表示法（链式栈）链式栈的定义和操作的实现类似于单链表。an-1a0…top∧图3-3链式栈an-2an-3不带表头结点的单链表课堂提要第3章堆栈和队列3.1堆栈3.1.1栈抽象数据类型3.1.2栈的顺序表示3.1.3栈的链接表示3.2队列3.3表达式的计算3.4递归3.1堆栈3.1.3栈的链接表示2.在链接表示下实现栈上定义的操作an-1a0…top∧图3-3链式栈an-2an-3入栈操作push(Tx)NodeT*q=newNodeT;q-element=x;q-link=top;top=q;3.1堆栈3.1.3栈的链接表示2.在链接表示下实现栈上定义的操作an-1a0…top∧图3-3链式栈an-2an-3出栈操作Pop()NodeT*q=top;top=top-link;deleteq;3.2队列3.1.3栈的链接表示课堂提要第3章堆栈和队列3.1堆栈3.2队列3.2.1队列抽象数据类型3.2.2队列的顺序表示3.2.3队列的链接表示3.3表达式的计算3.4递归队列的示意图Q=(a0,a1,…,an-1)a0a1…an-1frontrear入队出队3.2队列3.2.1队列抽象数据类型1.队列的定义队列是限定在表的一端插入，在表的另一端删除的线性数据结构。若队列中无元素，则为空队列队尾——允许插入元素的一端队头——允许删除元素的另一端Q=(a0,a1,…,an-1)课堂提要第3章堆栈和队列3.1堆栈3.2队列3.2.1队列抽象数据类型3.2.2队列的顺序表示3.2.3队列的链接表示3.3表达式的计算3.4递归3.2队列3.2.1队列抽象数据类型1.队列的定义a0a1…an-1frontrear入队出队若给定队列Q=(a0,a1,…,an-1)，则称a0是队头元素，an-1是队尾元素。元素a0,…,an-1依次入队，出队的顺序与入队相同，a0出队后，a1才能出队，因此又称队列为先进先出（FirstInFirstOut——FIFO）的动态线性数据结构。3.2队列3.2.1队列抽象数据类型1.队列的定义ACBrearfront队列工作的演示(入队)3.2队列3.2.1队列抽象数据类型1.队列的定义rearfront队列工作的演示(出队)ACB3.2队列3.2.1队列抽象数据类型2.队列的抽象数据类型ADTQueue{数据:0个或多个元素的线性序列（a0,a1,…,an-1),其最大长度为MaxQueueSize。它插入在一端进行，而删除在另一端进行，并遵循FIFO原则。运算:Create()：建立一个空队列。Destroy()：撤消一个队列。IsEmpty()：若队列空，则返回true;否则返回false。IsFull()：若队列满，则返回true;否则返回false。Front(x)：在x中返回队头元素。操作成功返回true；否则返回false。EnQueue(x)：在队尾插入元素x。操作成功返回true；否则返回false。DeQueue()：从队列中删除队头元素。操作成功返回true；否则返回falseClear():清除队列中全部元素。}3.2队列3.2.1队列抽象数据类型3.队列的C++模板抽象类templateclassTclassQueue{public:Queue(){};~Queue(){};virtualboolEnQueue(constTx)=0;virtualboolDeQueue()=0;virtualboolFront(T&x)=0;virtualboolIsEmpty()const=0;virtualboolIsFull()const=0;virtualvoidClear()=0;};3.2队列3.2.2队列的顺序表示1.队列的顺序表示法课堂提要第3章堆栈和队列3.1堆栈3.2队列3.2.1队列抽象数据类型3.2.2队列的顺序表示3.2.3队列的链接表示3.3表达式的计算3.4递归01234=maxSize-1(a)空队列fr图中f为front,r为rear3.2队列3.2.2队列的顺序表示1.队列的顺序表示法从(d)可以看到，当再有元素需要入队时将产生“溢出”，然而队列中尚有三个空元素单元，我们称这种现象为“假溢出”。指针f指向队首元素的前一个位置，指针r指向队尾元素50403020(b)元素20，30，40，50入队01234=maxSize-1fr50(c)元素20，30，40依次出队01234=maxSize-1fr50(d)元素60入队01234=maxSize-1fr603.2队列3.2.2队列的顺序表示2.循环队列表示法把数组从逻辑上看成是一个头尾相连的环。（a）空队列满队列front==rear实际仍有一个元素的空间未使用0fr12340f123420304050r3.2队列3.2.2队列的顺序表示2.循环队列表示法注意r值的变化：4+1=00f123420304050r（b）元素20，30，40，50入队列（c）元素20，30，40出队列0f123450r（d）元素60，70入队列0f123450r60703.2队列3.2.2队列的顺序表示2.循环队列表示法实现循环队列操作：(1)为使入队和出队实现循环，可以利用取余运算符%。(2)队头指针进一：front=(front+1)%maxSize；(3)队尾指针进一：rear=(rear+1)%maxSize；(4)空队列：当front==rear时为空队列，(5)满队列：当(rear+1)%maxSize==front时为满队列。满队列时实际仍有一个元素的空间未使用。3.2队列3.2.2队列的顺序表示3.顺序队列类templateclassTclassSeqQueue:publicQueueT{public:SeqQueue(intmSize);~SeqQueue(){delete[]q;}boolIsEmpty()const；boolIsFull()const；boolFront(T&x)const;boolEnQueue(Tx);boolDeQueue();voidClear(){front=rear=0;}