《数据结构与stl_第3章_栈队列串》由会员分享，可在线阅读，更多相关《数据结构与stl_第3章_栈队列串（80页珍藏版）》请在金锄头文库上搜索。
1、第三章 栈、队列和串,数据结构与STL,数据结构与STL,2,第三章 栈、队列和串,学习内容：3.1 栈3.2 队列3.3 串 3.4 实例分析3.5 STL中的相关模板类,数据结构与STL,3,3.1 栈（stack）,栈：限定仅在表的一端进行插入和删除操作的线性表。,a1,a2,a3,不含任何数据元素 的栈称为空栈。,栈的特性：后进先出 LIFO,栈的基本操作： 入栈（进栈） 出栈（退栈）,3.1.1 栈的逻辑结构,数据结构与STL,4,假定有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？,注意：栈只是对表插入和删除操作的位置进行了限制，并没有限定
2、插入和删除操作进行的时间。,abc、acb、bac、bca、cba,日常生活还有哪些栈的例子？,数据结构与STL,5,栈的常见操作,1. 置空栈SetNull(S) 将栈S置成空栈。 2. 入栈Push (S, x) 将元素x插入到栈S的栈顶。 3. 出栈PoP(S) 删除栈S的栈顶元素。 4. 取栈顶元素GetTop (S) 返回栈S的栈顶元素，栈顶元素并不出栈。 5. 判栈空Empty(S) 判别栈S是否为空。,数据结构与STL,6,3.1.2 栈的顺序存储结构,栈的顺序存储结构顺序栈 使用数组实现,0 1 2 3 4 5 6 7 8,a1,a2,一般用数组的开始一端表示栈底，同时附设指针
3、top指示栈顶元素在数组中的位置。,数据结构与STL,7,栈的操作示意：,* 栈的上溢和下溢,数据结构与STL,8,顺序栈的C+类实现,const int StackSize = 1024; /定义栈的最大高度 template class SeqStack /定义顺序栈模板类 public:SeqStack()top = -1;/构造函数，初始化空栈void Push(T x); /入栈操作T Pop(); /出栈操作T GetTop(); /查找栈顶元素bool Empty(); /判别栈是否为空 private:T dataStackSize;/定义数组int top; /栈顶指针 ;,
4、顺序栈与顺序表的定义有何区别？,数据结构与STL,9,/出栈操作 template T SeqStack:Pop() if (Empty() throw “下溢“;top-; /栈顶指针下移return datatop+1; ,/入栈操作 template void SeqStack:Push(T x) if (top = StackSize-1) throw “上溢“;top+; /栈顶指针上移datatop = x; ,/查找栈顶元素 template T SeqStack:GetTop()if (Empty() throw “下溢“;return datatop; ,数据结构与STL,1
5、0,两栈共享同一存储空间,栈满的条件？栈1为空的条件？栈2为空的条件？栈1入栈的操作？栈2入栈的操作？,如何设计两栈共享空间的C+类？,数据结构与STL,11,3.1.3 栈的链式存储结构,template struct Node T data;struct Node * next; ; template class LinkStack /定义链栈模板类 public:LinkStack()top = NULL;/构造函数，初始化空栈LinkStack(); /析构函数void Push(T x); /入栈操作T Pop(); /出站操作T GetTop(); /查找栈顶元素bool Empt
6、y()return (NULL = top)?true:false;/判别栈是否为空 private:struct Node * top; /栈顶指针 ;,数据结构与STL,12,入栈操作,/入栈操作 template void LinkStack:Push(T x) struct Node * p = new Node;/p-data = x; /步骤p-next = top; /步骤top = p; /步骤 ,时间复杂度?,数据结构与STL,13,出栈操作,template T LinkStack:Pop()/出栈操作 if (Empty() throw “下溢“;T x = top-da
7、ta; /步骤struct Node * p = top; /步骤top = top-next; /步骤delete p; /步骤，释放原栈顶结点return x; ,时间复杂度?,数据结构与STL,14,第三章 栈、队列和串,学习内容：3.1 栈3.2 队列3.3 串 3.4 实例分析3.5 STL中的相关模板类,数据结构与STL,15,3.2 队列,3.2.1 队列的逻辑结构,队列：允许在一端进行插入、在另一端进行删除的 线性表。允许插入的一端称为队尾（rear）允许删除的一端称为队头（front）在队尾进行插入操作称为入队在队头进行删除操作称为出队不含任何数据元素的队称作空队列,先进先出
8、（FIFO）,数据结构与STL,16,队列的常见基本运算,1. 置空队SetNull(Q) 将队列Q置成空队列。 2. 入队EnQueue (Q, x) 将元素x插入到队列Q的队尾。 3. 出队DeQueue (Q) 删除队列Q的队头元素。 4. 取队头元素GetFront(Q) 返回队列Q的队头元素，队头元素并不出队。 5. 判队空Empty(Q) 判别队列Q是否为空。,队列的顺序存储结构 顺序队列运算时头、尾指针位置及变化情况：,入队 r=r+1； datar = x；,出队 f = f+1；,队列的长度：r - f （队列中元素的个数）,下溢(队空)：f = r；,假上溢 r = max
9、size-1,上溢(队满)：r - f = maxsize,f r,r,f,a,r,b,r,c,f,f,f r,f,r,d,r,e,数据结构与STL,18,3.2.2 循环队列队列的顺序存储结构,空队,a1,a2,a4,a3,a1a2a3a4依次入队,例:,每次出队涉及所有元素的移动，效率低,数据结构与STL,19,若让a5a6入队会出现什么情况？,a5,新的问题：,数据结构与STL,20,最终的方案,解决假溢出的方法是将存储队列的数组看成是头尾相接的循环结构。,a6,a4,a5,a3,a5a6依次入队,队列采用头尾相接的顺序存储结构称为循环队列 。,解决方案:,循环队列,0,1,2,3,4,
10、设： MAX_SIZE =13,12,11,f,5,6,7,8,9,10,r,*,*,*,*,循环队列指针修改方法:,尾指针：r = (r+1) % MAX_SIZE,头指针：f =（f+1）% MAX_SIZE,队列的各种状态,队空,a7,a2,a3,a4,a5,a6,队满,a3,front,a4,a5,一般情况,a2,如何判断循环队列队空、队满？,方法一: 附设一个存储队列中元素个数的变量num：当num=0时队空；当num=MAX_SIZE时为队满； 方法二: 浪费一个元素空间队满条件：(rear+1) % MAX_SIZE=front，空队条件：front=rear； 方法三: 设置一
11、个标志flag，初始时队列空，flag置0。当有元素入队时，队列非空，flag置1；而当出队时，队列不满，flag置0。当front=rear且flag=0时为队空，当front=rear且flag=1时为队满。,数据结构与STL,24,队空,a2,a3,a4,a5,a7,rear,队满,a3,front,a4,a5,一般情况,a2,a4,a5,a3,a7,0 1 2 3 4 5,front,rear,0 1 2 3 4 5,front,rear,a4,a5,a3,0 1 2 3 4 5,front,rear,数据结构与STL,25,满队列示意图,如何判别队列满？,队头 = (队尾+1) %
12、数组长度,数据结构与STL,26,循环队列的实现,循环队列类的声明,const int QueueSize = 1000; template class CircleQueue /循环队列模板类 public:CircleQueue()front = rear = 0; /构造函数void EnQueue(T x); /入队T DeQueue(); /出队T GetFront(); /查找队头元素int GetLength(); /求队列长度bool Empty()return front=rear?true:false; /判队空private:T dataQueueSize;int fro
13、nt; /队头指针int rear; /队尾指针 ;,数据结构与STL,27,入队操作,当有元素入队后，队尾指针移向“下”一个位置,template void CircleQueue:EnQueue(T x) /入队 if (rear+1)% QueueSize = front) throw“overflow“;rear = (rear+1)% QueueSize; /队尾指针移向“下”一个位置datarear = x; ,数据结构与STL,28,template T CircleQueue:DeQueue() /出队 if (rear = front) throw “underflow“;f
14、ront = (front+1)% QueueSize; /队头指针移向“下”一个位置return datafront; ,出队操作,当有元素出队后，队头指针移向“下”一个位置,数据结构与STL,29,读取队头元素操作,template T CircleQueue:GetFront()/查找队头元素 if (rear = front) throw “underflow“;return data(front+1)% QueueSize; ,数据结构与STL,30,求队列长度,队列长度=(rearfront + QueueSize) % QueueSize,数据结构与STL,31,3.2.3 链队
15、列,队列的链式存储结构,带头结点的单链表：front指向头结点front-next指向队头rear指向队尾,template class LinkQueue /链队列模板类 public:LinkQueue()front = rear = new Node ; front-next = NULL; /构造函数LinkQueue(); /析构函数void EnQueue(T x); /入队T DeQueue(); /出队T GetFront(); /查找队头元素bool Empty()return front= rear?true:false;/判队空 private:Node * front; /队头指针Node * rear; /队尾指针 ;,
