1、第3章 栈和队列n栈 栈的定义 顺序栈的表示和实现 链栈的表示和实现n队列 队列的定义 循环队列 链队列 3.1 栈1.栈的定义2栈是限定仅在表的一端进行插入和删除操作的线性表，允许插入和删除的一端称为栈顶，另一端称为栈底。栈的插入操作称为入栈，栈的删除操作称为出栈。不含任何数据元素的栈称为空栈。设有栈S=(a1，a2，a3,，an)，则一般称a1为栈底元素，an为栈顶元素。入栈：按a1，a2，a3,，an的顺序出栈：按an，an-1，a2，a1的顺序栈称为后进先出的线性表（LIFO：Last In First Out）a2a1an.栈底栈顶入栈出栈栈的基本操作的基本操作操作操作结果果int
2、Length()返回栈元素个数bool Empty()如栈为空，则返回true，否则返回falsevoid Clear()清空栈bool Push(T e)插入元素e为新的栈顶元素bool Top(T&e)用e返回栈顶元素bool Pop(T&e)删除栈顶元素，并用e返回栈顶元素3.1 栈2.顺序栈的表示和实现3顺序序栈是指利用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。顺序栈可以用一维数组来实现。通常把数组中下标为0的一端作为栈底，同时附设变量top指示栈顶元素在数组中的位置。设存储栈的数组长度为maxSize，则栈空时栈顶位置top=-1，栈满时栈顶位
3、置top=maxSize-1。入栈时，栈顶位置top加1；出栈时，栈顶位置top-1。3.1 栈2.顺序栈的表示和实现4template class SqStackprivate:int top;/栈顶元素在数组中的下标int maxSize;/栈可用的最大容量T*elem;/存储空间的基地址public:SqStack(int size=DEFAULT_SIZE);/构造函数SqStack(SqStack&st);/复制构造函数SqStack();/析构函数int Length();/返回栈中元素个数bool Empty();/判断栈是否为空void Clear();/清空栈bool Pus
4、h(T e);/入栈bool Pop(T&e);/出栈bool GetTop(T&e);/返回栈顶元素;3.1 栈2.顺序栈的表示和实现5/返回栈中元素个数template int SqStack:Length()return top+1;/判断栈是否为空template bool SqStack:Empty()return top=-1;/清空顺序表template void SqStack:Clear()top=-1;/入栈template bool SqStack:Push(T e)if(top=maxSize-1)return false;elem+top=e;return true;
5、/返回栈顶元素template bool SqStack:GetTop(T&e)if(top=-1)return false;e=elemtop;return true;/出栈template bool SqStack:Pop(T&e)if(top=-1)return false;e=elemtop-;return true;3.1 栈3.链栈的表示和实现6链栈是指采用链式存储结构实现的栈，通常用单链表来表示。由于栈的插入和删除操作只能在栈顶执行，因此以单链表的头部作为栈顶是最方便的，而且没有必要像单链表那样为了运算方便附加一个头结点。链栈的结点结构与单链表的结点结构相同template st
6、ruct StNodeT data;StNode *next;3.1 栈3.链栈的表示和实现7template class LinkStackprivate:StNode*top;/栈顶指针public:LinkStack();/构造函数LinkStack(LinkStack&lst);/复制构造函数LinkStack();/析构函数int Length();/返回栈中元素个数bool Empty();/判断栈是否为空void Clear();/清空栈bool Push(T e);/入栈 bool Pop(T&e);/出栈bool GetTop(T&e);/返回栈顶元素;3.1 栈3.链栈的表
7、示和实现8/返回栈中元素个数template int LinkStack:Length()int len=0;StNode*p=top;while(p!=NULL)len+;p=p-next;return len;/判断栈是否为空template bool LinkStack:Empty()return top=NULL;/清空顺序表template void LinkStack:Clear()StNode*p;while(top!=NULL)p=top;top=p-next;delete p;/返回栈顶元素template bool LinkStack:GetTop(T&e)if(top=N
8、ULL)return false;e=top-data;return true;3.1 栈3.链栈的表示和实现9template bool LinkStack:Push(T e)StNode*p=new StNode;/生成新结点if(p=NULL)/动态内存耗尽return false;p-data=e;/将新结点数据域置为ep-next=top;/将新结点插入栈顶top=p;/修改栈顶指针return true;3.1 栈3.链栈的表示和实现10template bool LinkStack:Pop(T&e)if(top=NULL)/栈空return false;StNode*old_to
9、p=top;e=old_top-data;/用e保存栈顶元素的值top=old_top-next;/修改栈顶指针delete old_top;/释放原栈顶元素的空间return true;3.1 栈4.栈的应用进制转换问题11将十进制数转换为二进制数的方法很多，其中一个常用的算法是“除2取余法”。上述计算过程是从低位到高位顺序产生二进制数的各个数位，而输出过程应从高位到低位进行，恰好和计算过程相反，因此可以使用栈来解决这个问题。在计算过程中依次将得到的余数压入栈中，计算完毕后，将栈中的余数依次出栈输出，输出结果就是转换后的二进制数。(1)当n0时重复执行以下操作：计算n除以2的余数并将其压入栈
10、中；用n/2代替n。(2)重复执行以下操作直到栈为空：弹出栈顶元素，并输出被弹出元素的值。3.1 栈4.栈的应用括号匹配问题12给定一个算数表达式，目测怎么判断括号是否匹配呢？可以从左向右看这个表达式中的括号，看到一个“(”就记住它，如果下一个括号是“)”，则划掉这两个括号，如果下一个括号还是“(”，则暂时不管前一个“(”，先把它放在那里，等后面的“(”处理完再来处理它，这正好符合栈的后进先出特性，因此可以使用栈来解决这个问题。从左向右依次扫描表达式字符串中的各字符，若读入的是“(”，则进栈；若读入的是“)”，且栈不为空则出栈，如果栈空则说明没有与之匹配的左括号，匹配失败。当表达式扫描结束时，
11、若栈为空则匹配成功，否则，说明没有与栈中的“(”相匹配的“)”，匹配失败。(1)初始化一个空栈。(2)扫描表达式，依次读入字符，直到表达式扫描完毕。如果读入的字符是(，则将其压入栈；如果读入的字符是)，且栈非空，则弹出栈顶元素；如果栈为空，则括号不匹配，返回false。(3)如果栈为空，则左右括号匹配，返回true；否则括号不匹配，返回false。3.2 队列1.队列的定义13队列的基本操作列的基本操作队列是限定只允许在一端进行插入操作，在另一端进行删除操作的线性表。u允许删除（出队）的一端叫做队头u允许插入（入队）的一端叫做队尾u入队和出队的顺序相同u先进先出（FIFO）a1 a2 a3 a
12、nfrontrear入队出队操作操作结果果int Length()返回队列长度bool Empty()如队列为空，则返回true，否则返回falsevoid Clear()清空队列bool OutQueue(T&e)删除队头元素，并用e返回其值bool GetHead(T&e)用e返回队头元素bool InQueue(T e)插入元素e为新的队尾3.2 队列2.循环队列队列的顺序表示和实现14队列的顺序表示就是用一组地址连续的存储单元依次存放从队头到队尾的元素。可以用数组elemmaxSize作为队列的顺序存储空间，maxSize为队列的容量，队头元素放在下标为0的一端由于队列的队头和队尾都是
13、活动的，因此需要附设两个整型变量front和rear分别指示队头元素和队尾元素的位置。初始化创建空队列时，令front=rear=0，插入新元素时，rear加1；删除元素时，front加1。因此，在非空队列中，front始终指向队头元素，而rear始终指向队尾元素的下一个位置。假设当前队列分配的最大空间为6，则当队列处于图3-10（d）所示的状态时不可再继续插入新的队尾元素，否则会出现溢出现象，即因数组越界而导致的非法操作错误。事实上，此时队列的实际可用空间并未占满，所以这种现象称为“假溢出假溢出”。这是由“队尾入队，队头出队”这种受限制的操作造成的。3.2 队列2.循环队列队列的顺序表示和实
14、现15解决假溢出的方法是将队列从逻辑上看成一个环循循环队列列循环队列的首尾相接，当队头front和队尾rear进入到maxSize-1时，再进一个位置就自动地移动到0，可用取模运算来实现。队头进1：front=(front+1)%maxSize队尾进1：rear=(rear+1)%maxSize对于循环队列不能以front和rear的值是否相等来判断队列空间是空还是满。在这种情况下，如何区分队满还是队空呢？n少用一个元素空少用一个元素空间队列空间大小为n时，有n-1个元素就认为是队满。队空的条件：front=rear队满的条件：(rear+1)%maxSize=frontn另另设一个一个标志位
15、以区志位以区别队列是空列是空还是是满3.2 队列2.循环队列队列的顺序表示和实现16template class SqQueuepravite:int front,rear;/指示队头和队尾的位置int maxSize;/队列的最大容量T*elem;/存储空间的基地址public:SqQueue(int size=MAXSIZE);/构造函数SqQueue(SqQueue&sq);/复制构造函数SqQueue();/析构函数int Length();/返回队列的长度bool Empty();/判断队列是否为空void Clear();/清空队列bool InQueue(T e);/入队bool
16、 OutQueue(T&e);/出队bool GetHead(T&e);/返回队头元素;3.2 队列2.循环队列队列的顺序表示和实现17/返回队列长度template int SqQueue:Length()return(rear-front+maxSize)%maxSize;/判断队列是否为空template bool SqQueue:Empty()return front=rear;/入队template bool SqQueue:InQueue(T e)if(rear+1)%maxSize=front)return false;elemrear=e;rear=(rear+1)%maxSi
17、ze;return true;/清空队列template void SqQueue:Clear()rear=front=0;/出队template bool SqQueue:OutQueue(T&e)if(rear=front)return false;e=elemfront;front=(front+1)%maxSize;return true;/返回队头元素template bool SqQueue:GetHead(T&e)if(rear=front)return false;e=elemfront;return true;3.2 队列3.链队队列的链式表示和实现18队列的链式存储结构称为
18、链队，通常用单链表表示。结点结构与单链表的结点结构相同。队头队尾 a1 a2 an 头指针front尾指针rear头结点非空非空链队列：列：空空链队列：列：头指针front尾指针rear头结点3.2 队列3.链队队列的链式表示和实现19template class LinkQueueprivate:QuNode *front,*rear;public:LinkQueue();/构造函数LinkQueue(LinkQueue&lq);/复制构造函数LinkQueue();/析构函数int Length();/返回队列长度bool Empty();/判断队列是否为空void Clear();/清空
19、队列bool InQueue(T e);/入队bool OutQueue(T&e);/出队bool GetHead(T&e);/获取队头元素;3.2 队列3.链队队列的链式表示和实现20/返回队列长度template int LinkQueue:Length()int len=0;QuNode*p=front-next;while(p!=NULL)len+;p=p-next;return len;/判断队列是否为空template bool LinkQueue:Empty()return front=rear;/清空队列template void LinkQueue:Clear()QuNode
20、*p=front-next;while(p!=NULL)/删除所有数据结点 front-next=p-next;delete p;p=front-next;rear=front;/rear指向头结点/返回队头元素template bool LinkQueue:GetHead(T&e)if(front=rear)return false;e=front-next-data;return true;3.2 队列3.链队队列的链式表示和实现21template bool LinkQueue:InQueue(T e)QuNode*p=new QuNode;/生成新结点if(p=NULL)/动态内存耗尽
21、return false;p-data=e;p-next=NULL;rear-next=p;/新结点链入队尾rear=p;/重新设置队尾指针return true;3.2 队列3.链队队列的链式表示和实现22template bool LinkQueue:OutQueue(T&e)if(front=rear)return false;QuNode*p=front-next;/p指向队头结点e=p-data;/保存出队元素的值front-next=p-next;/修改头结点的指针域if(rear=p)/若只有一个元素，出队后，变成空队列rear=front;delete p;/释放出队元素的结点
22、空间return true;3.2 队列4.队列的应用求解约瑟夫环问题23将n个人按照编号顺序排成一个队列，从队头自1开始报数，报到的数小于m的人站到队尾，报到m的人出列，然后继续从队头自1开始报数，如此下去，直到队列中只剩一个人为止。n=8，m=3时的选择过程：(1)建立数据元素为1，2，n的循环队列。(2)当队列的长度大于1时，重复执行下述操作：从队头开始，对前m-1个元素重复执行“出队再入队”的操作；将第m个元素出队，并输出其值；(3)输出队头元素的值，即优胜者的编号。本章小结(1)栈是限定仅在表的一端（栈顶）进行插入和删除操作的线性表，又称为后进先出的线性表。栈有两种存储表示：顺序表示
23、（顺序栈）和链式表示（链栈）。栈的主要操作是入栈和出栈。对于顺序栈的入栈操作需要判断栈是否已满，而链栈是动态分配空间，不会出现栈满的情况；进行出栈操作时不管是顺序栈还是链栈都需要判断栈是否为空。(2)队列是一种先进先出的线性表，它只允许在表的一端（队尾）进行插入操作，而在另一端（队头）进行删除操作。队列也有两种存储表示，顺序表示（循环队列）和链式表示（链队）。队列的主要操作是入队和出队。对于循环队列的入队操作要注意判断队满，而链队的入队操作不需要判断队满；循环队列和链队的出队操作都需要判断队空。(3)栈和队列是在程序设计中被广泛使用的两种数据结构，其具体的应用场景都是与其表示方法和运算规则相互联系的。
