[经济学]第3章 栈和队列.pptVIP

第3章 栈和队列 [内容提要] 1.栈和队列的概念 2.栈和队列的存储结构及它们的应用 3.栈和队列与线性表的联系 栈的示例图 栈的顺序存储结构(顺序栈) 顺序栈:是利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素，通常用一维数组存放栈的元素。设“指针”top指示栈顶元素的当前位置或后一空位置(下标)。 顺序栈的几种情况 表达式的表示法及计算——不带括号 1.建立操作数和运算符堆栈，初始为空 2.当表达式尚未读取完时：(从左到右） 读取一个运算单元 （1）若是操作数，则将其存入操作数堆栈 （2）若是运算符： 1＋2×4－9/3 操作数栈 运算符栈 栈与递归 定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表 队尾(rear)——允许插入的一端 队头(front)——允许删除的一端 队列特点：先进先出(FIFO)或后进后出(LILO) 队列的顺序存储结构 定义：队列的顺序存储结构，简称顺序队列，它是由一个存放队列中元素的一维数组，及分别指示队头和队尾的“指针”所组成。 顺序队列的几种状态 循环队列的引入 顺序队列存在的问题 设数组维数为M，则： 当front=-1,rear=M-1时，再有元素入队发生溢出——真溢出 当front?-1,rear=M-1时，再有元素入队发生溢出——假溢出 解决方案——循环队列 基本思想：把队列设想成环形，让sq[0]接在sq[M-1] 之后，若rear+1==M,则令rear=0; 实现：利用“模”运算 入队： rear=(rear+1)%M; sq[rear]=x; 出队： front=(front+1)%M; x=sq[front]; 新问题：队满、队空判定条件 解决方法：规定当数组只剩下一个单元时就认为队满，此时，队尾指针只差一步追上队头指针，即：(rear+1)%M==front。 在循环队列上实现的操作 初始化操作的实现 判队空函数 判队满 入队列操作 出队列操作 队列的链式存储结构 定义:队列的链式存储结构，简称链队列,它实际上是一个同时带有头指针和尾指针的单链表，头指针指向头结点，尾指针指向队尾结点 在链队列上实现的操作 初始化操作的实现 判队空函数 入队列操作 出队列操作 队列的应用--求迷宫的最短路径 迷宫示例 解决迷宫的算法 学习要点 １、掌握栈和队列这两种数据结构的特点，了解在什么问题中应该使用哪种结构。 ２、熟悉栈（队列）和线性表的关系；顺序栈（顺序队列）和顺序表的关系；链栈（链队列）和链表的关系。 ３、重点掌握在顺序栈和链栈上实现的栈的基本运算，特别注意栈满和栈空的条件及它们的描述。 ４、重点掌握在循环队列和链队列上实现的基本运算，特别注意队满和队空的描述方法。 ５、熟悉栈和队列的下溢和上溢的概念；顺序队列中产生假上溢的原因；循环队列消除假上溢的方法。 迷宫问题是指在一个m*n的矩阵中，其中“0”代表可以行走的区域，“1”代表不可行走的区域，当你处在迷宫的任何一个位置，可以往上、下、左、右、左上、右下、左下、右上八个方向行走来找寻迷宫出口。 入口 1 2 3 4 5 6 7 8 0 1 1 0 0 1 1 0 6 0 0 0 1 1 0 0 1 5 1 1 0 0 1 1 1 0 4 1 1 1 1 0 0 1 0 3 0 1 0 1 0 1 0 1 2 1 1 1 0 1 1 1 0 1 出口 算法的基本思想为：从迷宫入口点（1,1）出发，向四周有哪些信誉好的足球投注网站，记下所有一步能到达的坐标点；然后依次再从这些点出发，再记下所有一步能到达的坐标点，…，依此类推，直到到达迷宫的出口点(m,n)为止，然后从出口点沿有哪些信誉好的足球投注网站路径回溯直至入口。这样就找到了一条迷宫的路径，否则迷宫无路径。 ? 15 15 13 11 10 9 9 8 7 7 6 5 4 3 2 2 1 1 0 -1 pre ? 8 8 4 5 7 1 3 6 6 6 2 5 5 1 4 4 1 3 2 1 y ? 6 5 6 6 5 6 5 2 5 4 5 1 4 4 2 3 3 3 2 1 x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18