数据结构与算法应用教程 教学配套课件 高佳琴 第4章完 栈与队列.pdfVIP

数据结构与算法实用教程 主编高佳琴 第4章 栈与队列 本章要点：　 1)栈的定义和结构特点，栈的存储方式(顺序存储与链接存储)和 基本操作的实现算法。　 2) 队列的定义和结构特点，队列的存储方式和基本操作的实现算 法。　 3)栈和队列的应用。　 本章难点：　 1)栈的特性，栈的存储结构，栈的基本操作实现算法。　 2) 队列基本操作的实现算法。　 3)栈和队列的应用。 　　 4.1 栈 4.1.1 栈的基本概念 4.1.2 栈的存储方式和基本操作的实现算法 4.1.1 栈的基本概念 栈(stack)是限定在表的一端进行插入或删除操作的线性表。插入 元素操作称为入栈，删除元素操作称为出栈。 1)顺序栈为空，这是初始化栈后的结果。 2)元素A入栈，此时top=0 。 3)元素B 、C、D入栈，此时top=3 。 4)执行两次出栈操作，元素D 、C 出栈，此时top=1 。 5)再执行两次出栈操作后，栈回到初始状态，top=-1 。 4.1.1 栈的基本概念 图4-1 栈的示意图 4.1.1 栈的基本概念 图4-2 栈顶指针和栈中元素之间的关系 4.1.2 栈的存储方式和基本操作的实现算法 (1)初始化栈 InitStack(S) 。 (2) 入栈 PushStack(S,x) 。 (3) 出栈 PopStack(S) 。 (4) 获取栈顶元素内容 GetTopStack(S) 。 (5) 判断栈是否为空 IsNullStack (S) 。 1.栈的顺序存储 2.栈的链式存储 1.栈的顺序存储 图4-3 顺序栈 (1)栈空 (2)栈满 (3)入栈操作 (4)出栈操作 1.栈的顺序存储 图4-4 入栈操作算法流程 1.栈的顺序存储 图4-5 出栈操作算法流程 2.栈的链式存储 图4-6 栈的链式存储结构 图4-7 链栈的操作 a)含有两个元素的栈 b)插入元素后的栈 c)删除两个元素后的栈 2.栈的链式存储 (1)空栈 (2)栈满 (3)入栈操作 (4) 出栈操作 图4-8 出栈操作算法流程 4.2 队列 4.2.1 队列的基本概念 4.2.2 队列的基本操作 4.2.3 队列的存储方式和基本操作的实现算法 4.2.1 队列的基本概念 队列(queue)是一种特殊的线性表。它的特点是插入操作限定 在表的一端进行，而删除操作则限定在表的另一端进行。允许 删除操作的一端称为队头(front)，允许插入操作的一端称为队 尾( rear)， 图4-9 队列示意图 4.2.2 队列的基本操作 (1) 初始化队列 InitQueue(q) 。 (2) 入队 EnterQueue(q,x) 。 (3) 出队 DelQueue(q,x) 当队列中有元素存在时，删除队头元素，返回队头元 素的值，且其后继为新的队头元素，队列减少一个元素。 (4) 获取队头元素内容 getfirstQueue