《第章栈与队列ppt课件》由会员分享，可在线阅读，更多相关《第章栈与队列ppt课件（32页珍藏版）》请在金锄头文库上搜索。
1、数据结构数据结构 第三章第三章 栈和队列栈和队列 数据结构数据结构 第三章第三章 栈和队列栈和队列 1、栈和和队列的定列的定义及特点；及特点； 2、栈的的顺序存序存储表示；表示； 3、队列的列的顺序存序存储表示；表示；队列的列的链接存接存储表示；表示； 4、栈和和队列的运用列的运用举例。例。 教学内容教学内容 数据结构数据结构 第三章第三章 栈和队列栈和队列 限定限定仅在表尾在表尾进展插入或展插入或删除操作。除操作。 3.1 栈栈 3.1.1 笼统数据类型栈的定义笼统数据类型栈的定义 栈的定义栈的定义 a1 a2 an-1 an 栈顶(top) 栈底底(bottom)出出栈 进栈 栈底元素底元
2、素 栈顶元素元素 栈栈(stack)(stack)：线线性表性表性表性表 后后进先出先出 (LIFO构造构造)。 栈顶(top)数据结构数据结构 第三章第三章 栈和队列栈和队列 栈简称称为S，是一个二元，是一个二元组 S=D,R) 其中：其中：D 是数据元素的有限集合是数据元素的有限集合 D ai | ai ElemSet, i = 1, 2, ., n, n0 R 是数据元素之是数据元素之间关系的有限集合关系的有限集合 数据关系：数据关系：R1 | ai-1, aiD, i = 2, ., n 商定商定an 端端为栈顶，a1 端端为栈底。底。 数据数据对象象栈的方式化定义栈的方式化定义 a1
3、 ， a2 ， a3 ，.， ai-1 ， ai ， ai +1， an数据结构数据结构 第三章第三章 栈和队列栈和队列 栈的接口的定义栈的接口的定义 Public interface IStack int GetLength( ); / 求求栈的的长度度 bool IsEmpty( ); / 判判别栈能否能否为空空 void Clear ( ); / 清空操作清空操作 void Push (T item ); /入入栈操作操作 T Pop ( ); / 出出栈操作操作 T GetTop；/取取栈顶元素元素 数据结构数据结构 第三章第三章 栈和队列栈和队列 3.1.2 栈的存的存储和运算和运算
4、实现 顺序序栈 利用一利用一组地址延地址延续的的 存存储单元元依次存放自依次存放自栈底到底到栈顶的的 数据元素，数据元素，同同时附附设指指针 top 指示指示栈顶元素在元素在顺序序栈中的位置。中的位置。 top A top B top C top D top E top 空空栈 假假设再再进展元展元 素素“出出栈操操 作，将作，将产生生 “下溢。下溢。 top 栈满 假假设再再进展元展元 素素“入入栈操操 作，将作，将产生生 “上溢。上溢。 top-1顺序序栈类SeqStack的的实现阐明：明：public class SeqStack: IStack private int maxsize
5、; / 顺序序栈的容量的容量 private T data ; / 数数组，用于存，用于存储顺序序栈中的数据元素中的数据元素 private int top; /指示指示顺序序栈的的栈顶根本操作：根本操作：数据结构数据结构 第三章第三章 栈和队列栈和队列 顺序栈的根本操作：顺序栈的根本操作： int GetLength( ); / 求求栈的的长度度 bool IsEmpty( ); / 判判别栈能否能否为空空 void Clear ( ); / 清空操作清空操作 void Push (T item ); /入入栈操作操作 T Pop ( ); / 出出栈操作操作 T GetTop；/取取栈顶元
6、素元素 数据结构数据结构 第三章第三章 栈和队列栈和队列 3.2 栈的运用举例栈的运用举例 3.2.1 数制转换数制转换 十十进制数制数 N 和其他和其他 d 进制数制数 M 的的转换是是计算机算机实现计算算 的根本的根本问题，其，其处理方法很多，其中一个理方法很多，其中一个简单算法是逐次除以算法是逐次除以 基数基数 d 取余法，它基于以下原理：取余法，它基于以下原理： N = (N div d )*d + N mod d 详细作法作法为：首先用：首先用 N 除以除以 d，得到的余数是，得到的余数是 d 进制数制数 M 的最低位的最低位 M0，接着以前一步得到的商作，接着以前一步得到的商作为被
7、除数，再除以被除数，再除以 d， 得到的余数是得到的余数是 d 进制数制数 M 的次最低位的次最低位 M1，依次，依次类推，直到商推，直到商 为 0 时得到的余数是得到的余数是 M 的最高位的最高位 Ms假定假定 M 共有共有 s +1 位。位。 数据结构数据结构 第三章第三章 栈和队列栈和队列 例：例： (1348)10=(2504)8，其运算过程如下：，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 对应的的 8 8 1348 余数余数 进制数位制数位 8 168 4 M0 8 21 0 M1 8 2 5 M2 8 0
8、 2 M3 数据结构数据结构 第三章第三章 栈和队列栈和队列 例：要求：输入一个非负十进制整数，输出等值的八进制数。例：要求：输入一个非负十进制整数，输出等值的八进制数。 top 4 0 5 2 top 1348 168 21 top 2 top 0 top 2504 算法算法实现：public void Conversion (int n) SeqStack s=new SeqStack ( ); while (n0) s.push(n%8); n=n/8; while (!s.IsEmpty( ) n=s.Pop( ); console.WriteLine(“0，n); 1348数据结构数
9、据结构 第三章第三章 栈和队列栈和队列 3.2.4 迷宫求解迷宫求解 出口出口 入入 口口 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 11 12 22 32 33 34 24 25 26 16 15 14 31 41 51 52 53 63 64 65 75 85 86 87 88 88 穷举穷举求解求解求解求解 求迷求迷宫途径算法的根本思想：途径算法的根本思想： 假假设当前位置当前位置“可通，那么可通，那么纳入途径，入途径，继续前前进； 假假设当前位置当前位置“不可通，那么后退，不可通，那么后退，换方向按方向按东南南西北西北 的的顺序序继续探求；探求；
10、假假设周周围“均无通路，那么将当前位置从途径中均无通路，那么将当前位置从途径中删除除出去。出去。 数据结构数据结构 第三章第三章 栈和队列栈和队列 限定在表的一端插入、另一端限定在表的一端插入、另一端删除。除。 3.3 队列队列 3.3.1 笼统数据类型队列的定义笼统数据类型队列的定义 队列的定义队列的定义 队队列列列列(queue)(queue)：线线性表性表性表性表 先先进先出先出 (FIFO构造构造)。 队队尾尾尾尾 队头 以下以下图是是队列的表示列的表示图： a1a2an 出队出队 入队入队 队头队头 队尾队尾 当当队列中没有元素列中没有元素时称称为空空队列。列。 数据结构数据结构 第
11、三章第三章 栈和队列栈和队列 双端队列双端队列 限定插入和限定插入和删除在表的两端除在表的两端进展。展。 双端双端双端双端队队列列列列(deque)(deque)：线线性表性表性表性表 (double-ended queue)(double-ended queue)先先进先出先出 (FIFO构造构造)。 端点端点 1 端点端点 2 以下以下图是双端是双端队列的表示列的表示图： a1a2an 出队出队 入队入队 端点端点 1 端点端点 2 出队出队 入队入队 输输出受限的双端出受限的双端出受限的双端出受限的双端队队列：一个端点可插入和列：一个端点可插入和列：一个端点可插入和列：一个端点可插入和删
12、删除，除，除，除， 另一个端点另一个端点另一个端点另一个端点仅仅可插入。可插入。可插入。可插入。 输输入受限的双端入受限的双端入受限的双端入受限的双端队队列：一个端点可插入和列：一个端点可插入和列：一个端点可插入和列：一个端点可插入和删删除，除，除，除， 另一个端点另一个端点另一个端点另一个端点仅仅可可可可删删除。除。除。除。 数据结构数据结构 第三章第三章 栈和队列栈和队列 队列列简称称为Q，是一个二元，是一个二元组 Q=D,R) 其中：其中：D 是数据元素的有限集合是数据元素的有限集合 D ai | ai ElemSet, i = 1, 2, ., n, n0 R 是数据元素之是数据元素之
13、间关系的有限集合关系的有限集合 数据关系：数据关系：R1 | ai-1, aiD, i = 2, ., n 商定商定an 端端为队尾，尾，a1 端端为队头。 数据数据对象象队列的方式化定义队列的方式化定义 a1 ， a2 ， a3 ，.， ai-1 ， ai ， ai +1， an数据结构数据结构 第三章第三章 栈和队列栈和队列 队列的接口的定义队列的接口的定义 Public interface IQueue int GetLength( ); / 求求队列的列的长度度 bool IsEmpty( ); / 判判别队列能否列能否为空空 void Clear ( ); / 清空操作清空操作 vo
14、id In (T item ); /入入队列操作列操作 T Out ( ); / 出出队列操作列操作 T GetFront；/取取队头元素元素 数据结构数据结构 第三章第三章 栈和队列栈和队列 3.4.2 链队列列队列的列的链式表示和式表示和实现 链队链队列：用列：用列：用列：用链链表表示的表表示的表表示的表表示的队队列列列列队队列的列的列的列的链链式存式存式存式存储储构造。构造。构造。构造。 是限制是限制仅在表在表头删除和表尾插入的除和表尾插入的单链表。表。 显然然仅有有单链表的表的头指指针不便于在表尾做插入操作，不便于在表尾做插入操作，为此再此再 添加一个尾指添加一个尾指针，指向，指向链表
15、的最后一个表的最后一个结点。于是，一个点。于是，一个链队列列 由一个由一个头指指针和一个尾指和一个尾指针独一确定。独一确定。 为了操作的方便，同了操作的方便，同线性性链表一表一样，也，也给链队列添加一个列添加一个头 结点，并点，并设定定头指指针指向指向头结点。因此，空点。因此，空队列的断定条件就成列的断定条件就成 为头指指针和尾指和尾指针都指向都指向头结点。点。frontrearrearfront图图3-12 链队列表示图链队列表示图队头队头 队尾队尾 数据结构数据结构 第三章第三章 栈和队列栈和队列 用用 C #言言语定定义链队列列结点构造如下：点构造如下： public class Nod
16、e private T data; /数据域数据域 private Node next; /援用域援用域 P97 datanext结点的构造点的构造: :数据结构数据结构 第三章第三章 栈和队列栈和队列 链队列的根本操作链队列的根本操作public class LinkQueue:IQueue private Nodefront; / 队列列头指示器指示器 private Noderear; / 队列尾指示器列尾指示器 private int num; / 队列列结点个数点个数 int GetLength( ); / 求求链队列的列的长度度 bool IsEmpty( ); / 判判别链队列能
17、否列能否为空空 void Clear ( ); / 清空操作清空操作 void In (T item ); /入入链队列操作列操作 T Out ( ); / 出出链队列操作列操作 T GetFront；/取取链队头元素元素 数据结构数据结构 第三章第三章 栈和队列栈和队列 rearfrontxy 插入操作在链队列中的实现插入操作在链队列中的实现 p p 思想：思想：1、判、判别链队列能否列能否为空空 : front=rear,假假设为空，那么空，那么修正修正rear的的值，指向插入的，指向插入的结点点:rear=p;2、假、假设不不为空表，那么插入的空表，那么插入的结点只能插入到表尾：点只能插
18、入到表尾： rear.next=p; rear=p.?数据结构数据结构 第三章第三章 栈和队列栈和队列 删除操作在链队列中的实现删除操作在链队列中的实现 思想：思想：1、判、判别链队列能否列能否为空空 : IsEmpty ,假假设为空，那么空，那么给出一出一个空表的信息，表示不能个空表的信息，表示不能删除；除；2、假、假设不不为空表，要完成空表，要完成删除操作有两中情况：除操作有两中情况： 当当队列中数据元素列中数据元素 1 个元素个元素时，只修正，只修正front的的值： front.next=front.next.next; 当当队列中数据元素列中数据元素 = 1 个元素个元素时,既要修正
19、既要修正front的的值，也要，也要修正修正rear的的值：front.next=front.next.next;rear=front;?frontrearyxp p 数据结构数据结构 第三章第三章 栈和队列栈和队列 填空题部分填空题部分 1、栈的特点是、栈的特点是 ，队列的特点是，队列的特点是 。 2、线性表、栈和队列都是、线性表、栈和队列都是 构造，可以在线性表的构造，可以在线性表的 位置插入和删除元素，栈只能在位置插入和删除元素，栈只能在 插入和删除元素，插入和删除元素， 队列只能在队列只能在 插入元素和插入元素和 删除元素。删除元素。 3、设栈、设栈 S 和队列和队列 Q 的初始形状皆
20、为空，元素的初始形状皆为空，元素a1, a2, a3, a4, a5 和和 a6 依次经过一个栈，一个元素出栈后即进入队列依次经过一个栈，一个元素出栈后即进入队列 Q，假设，假设 6 个元素出队列的顺序是个元素出队列的顺序是 a3, a5, a4, a6, a2, a1 那么栈那么栈 S 至少应至少应 该包容该包容 ( ) 个元素。个元素。 4、假设队列的入队序列是、假设队列的入队序列是 1, 2, 3, 4，那么出队序列是。，那么出队序列是。 A4,3,2,1B1,2,3,4C1,4,3,2D3,2,4,1习题：习题： 数据结构数据结构 第三章第三章 栈和队列栈和队列 3.4.3 循循环队列
21、列队列的列的顺序表示和序表示和实现 是限制是限制仅在表在表头删除和表尾插入的除和表尾插入的顺序表。序表。 头尾尾 指指针 利用一利用一组地址延地址延续的存的存储单元依次存放元依次存放队列中的数据元素。列中的数据元素。 rear front rear front J1 J2 J3 头、尾指、尾指针和和队列元素之列元素之间的关系的关系 rear front J3 rear front 在非空在非空队列里，列里，头指指针一直指向一直指向队头元素元素尾指尾指针一直指向一直指向队尾元素的下一位置。尾元素的下一位置。 由于：由于：队头和和队尾的位置是尾的位置是变化的，所以：化的，所以：设头、尾指、尾指针。
22、 初始化初始化时的初始的初始值均均应置置为 0。 入入队，尾指，尾指针增增 1 出出队，头指指针增增 1 头头尾指尾指尾指尾指针针相等相等相等相等时队时队列列列列为为空空空空 数据结构数据结构 第三章第三章 栈和队列栈和队列 在在顺序序队列中，当列中，当队尾指尾指针曾曾经指向了指向了队列的最后一个位置列的最后一个位置 的下一个位置的下一个位置时，假，假设再有元素入再有元素入队，就会，就会发生生“溢出。溢出。 “假溢出假溢出队列的存列的存储空空间未未满，却，却发生了溢出。生了溢出。 rear front J1 J2 J3 J4 rear front J3 J4 (1)、平移元素：把一切元素平移到
23、、平移元素：把一切元素平移到队列的首部。效率低。列的首部。效率低。 处理理“假溢出的假溢出的问题有两种可行的方法：有两种可行的方法： (2)、将、将顺序序队列的存列的存储区假想区假想为一个一个环状的空状的空间，当，当发生假生假 溢出溢出时，将新元素插入到第一个位置上，将新元素插入到第一个位置上，这样做，做，虽然物理上然物理上队 尾在尾在队首之前，但首之前，但逻辑上上队首依然在前。入列和出列仍按首依然在前。入列和出列仍按“先先进先先 出的原那么出的原那么进展，展，这就是循就是循环队列。操作效率、空列。操作效率、空间利用率高。利用率高。 rear front J3 J4 front rear J3
24、 J4 数据结构数据结构 第三章第三章 栈和队列栈和队列 循环队列的三种形状：循环队列的三种形状： 0 1 2 3 4 5 front rear 0 1 2 3 4 5 J5 J4 J3 front rear 0 1 2 3 4 5 J5 J4 J3 J6 J7 J8 front front rear rear 注：注：注：注：仅仅凭凭凭凭 front = rear front = rear 不能断定不能断定不能断定不能断定队队列是空列是空列是空列是空还还是是是是满满。 处理方法：理方法： (1)、另、另设一个布一个布尔变量以区量以区别队列的空和列的空和满；(2)、少用一个元素的空、少用一个元
25、素的空间，商定入，商定入队前，前，测试尾指尾指针在循在循环意意 义下加下加 1 后能否等于后能否等于头指指针，假，假设相等那么以相等那么以为队满： rear+1%maxsize=front； (3)、假、假设front=rear，那么，那么为空空队列。列。 数据结构数据结构 第三章第三章 栈和队列栈和队列 循环意义下的加循环意义下的加 1 操作可以描画为：操作可以描画为： if (rear + 1 MAXQSIZE) rear = 0; else rear +; 0 1 2 3 4 5 J5 J4 J3 rear front 利用模运算可利用模运算可简化化为： rear = (rear + 1
26、)% MAXQSIZE front = (front+ 1)% MAXQSIZE 数据结构数据结构 第三章第三章 栈和队列栈和队列 public class CSeqQueue:IQueue private int maxsize; / 循循环顺序序队列的容量列的容量 private T data; / 数数组，用于存，用于存储循循环顺序序队列中的数据元素列中的数据元素 private int front; / 头指指针，假，假设队列不空，指向列不空，指向队列列头元素元素 private int rear; / 尾指尾指针，假，假设队列不空，指向列不空，指向队列尾元素的下列尾元素的下 一个位置
27、一个位置 根本操作成根本操作成员方法方法 循环队列的顺序存储构造：循环队列的顺序存储构造： 数据结构数据结构 第三章第三章 栈和队列栈和队列 队列的根本操作在循环队列中的实现：队列的根本操作在循环队列中的实现： int GetLength( ); / 求顺序队列的长度求顺序队列的长度 bool IsEmpty( ); / 判别顺序队列能否为空判别顺序队列能否为空 void Clear ( ); / 清空操作清空操作 void In (T item ); /入顺序队列操作入顺序队列操作 T Out ( ); / 出顺序队列操作出顺序队列操作 T GetFront；/取顺序队头元素取顺序队头元素数
28、据结构数据结构 第三章第三章 栈和队列栈和队列 public int GetLength( ); / 前往前往队列列 Q 的元素个数的元素个数 return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE; 求循环队列的长度求循环队列的长度 思索到循环队列思索到循环队列 front rear J3 J4 front rear J3 J1 J2 数据结构数据结构 第三章第三章 栈和队列栈和队列 public void In (T item) / 插入元素插入元素 item 为 Q 的新的的新的队尾元素尾元素 if (IsFull() console.WriteL
29、ine(“Queue is full); return ; / 队列列满 datarear=item; rear = (rear + 1) % MAXSIZE; return OK; 插入操作在循环队列中的实现插入操作在循环队列中的实现 front rear J3 J4 J5 rear 3210数据结构数据结构 第三章第三章 栈和队列栈和队列 public T Out ( ) / 假假设队列不空，那么列不空，那么删除除 Q 的的队头元素，元素， / 用用tmp 前往其前往其值，并前往，并前往 OK; T tmp=default(T); if (IsEmpty() console.WriteLi
30、ne(“Queue is empty); return tmp; tmp=datafront; front=(front+1)%maxsize; return tmp; 删除操作在循环队列中的实现删除操作在循环队列中的实现 rear front front rear J3 J1 J2 front 数据结构数据结构 第三章第三章 栈和队列栈和队列 1. 掌握掌握栈和和队列列类型的特点，并能在相型的特点，并能在相应的运用的运用问题中正确中正确 选用它用它们。 2. 熟熟练掌握掌握栈的的顺序存序存储构造以及根本操作在构造以及根本操作在顺序序栈上的上的实 现算法，特算法，特别应留意留意栈满和和栈空的条
31、件及其描画方法。空的条件及其描画方法。 3. 熟熟练掌握循掌握循环队列和列和链队列以及根本操作在列以及根本操作在这两种存两种存储结 构上的构上的实现算法，特算法，特别应留意留意队满和和队空的条件及其描画空的条件及其描画 方法。方法。 教学要求教学要求 数据结构数据结构 第三章第三章 栈和队列栈和队列 选择题部分部分 1、循、循环队列用数列用数组 A0, m-1 存放其元素存放其元素值，知其，知其头尾指尾指 针分分别是是 front 和和 rear 那么当前那么当前队列中的元素个数是。列中的元素个数是。 (A) (rear-front+m)%m (B) rear-front+1 (C) rear-front-1 (D) rear-front 2、以数、以数组 Q0 m1 存放循存放循环队列中的元素，列中的元素，变量量 rear 和和 qulen 分分别指示循指示循环队列中列中队尾元素的尾元素的实践位置和当前践位置和当前 队列中元素的个数，列中元素的个数，队列第一个元素的列第一个元素的实践位置是。践位置是。 (A) rearqulen (B) rearqulenm (C) mqulen (D) ( 1rearmqulen) % m
