DS03-栈和队列解读.ppt

第三章 栈和队列 栈（Stack） 栈的应用 队列(Queue) 队列的应用 定义： 栈的示意图 栈的基本操作 ClearStack(S)：栈S已经存在，清除栈S中的所有元素 将S置成空栈。 InitStack( )： 初始化，构造一个空栈S StackEmpty(S)：判断栈S是否为空，若为空，则返回 true；否则返回false GetTop(S) ： 返回S的栈顶元素，但不移动栈顶指针 也不改变栈顶元素的值 Push(S, x) ：在S的顶部插入(亦称压入)元素x；若S栈未满，将x插入栈顶位置，若栈已满，则返回FALSE，表示操作失败，否则返回TRUE。 （入栈操作) Pop(S) ： 删除S的栈顶元素并返回其值（出栈操作） 顺序栈的基本操作 顺序栈的入栈操作——例如用堆栈存放（A，B，C，D） 顺序栈出栈操作——例如从栈中取出‘B’ 3.2 栈的应用举例 3.3 队 列 队 列 的 实 现 队列的实现方式是本节重点，关键是掌握入队和出队操作。具体实现依存储结构（链队或顺序队）的不同而不同。 链队列 栈与递归 for(j=1;jn;j++) /*利用循环队列输出前n-1行的值*/ {for(i=1;in-j;i++) /*在输出第j行的首元素之间输出n-j个空格*/ printf( ); EnQueue(q,0); /*行分隔符0入队*/ do /*输出第j行并计算第j+1行*/ {s=DeQueue(q); /*删除队头元素并赋给s*/ t=GetHead(q); /*取队头元素给t*/ if(t) printf(%5 d,t); /*若不到行分隔符0，则输出t，再输出一个空格*/ else printf(\n); /*否则输出一个换行符*/ EnQueue(q,s+t); /*将第j+1行的对应元素s+t入队*/ }while(t!=0); } DeQueue(q); /* 删除行分隔符 */ printf(%3d,DeQueue(q)); /* 输出第n行的第一个元素 */ while(!QueueEmpty(q)) /* 输出第n行的其余元素 */ {t=DeQueue(q); printf(“%5 d,t); } } 队列不空，则出队 输出杨辉三角形的最后一行（）第n行 1．什么是递归 递归定义： 简单地说，一个用自己定义自己的概念,称为递归定义。 例 n!= 1* 2* …* (n-1)*n 用(n-1)!定义n! 应用栈处理数据具有后进先出的特性，可利用栈来实现数据处理过程。可以用栈来实现递归。 n!= 1 当 n=0时 n!= n (n-1)! 当n 0时 n! 队列 (Queue)是另一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以队列具有先进先出(Fist In Fist Out， 缩写为FIFO)的特性。 队列的定义 在队列中，允许插入的一端叫做队尾(rear)，允许删除的一端则称为队头(front)。 假设队列为q=(a1，a2，…，an)，那么a1就是队头元素，an则是队尾元素。队列中的元素是按照a1，a2，…，an的顺序进入的， 退出队列也必须按照同样的次序依次出队，也就是说，只有在a1，a2，…，an-1都离开队列之后，an才能退出队列。 问：为什么要设计队列？它有什么独特用途？ 离散事件的模拟（模拟事件发生的先后顺序,例如 CPU芯片中的指令译码队列）； 操作系统中的作业调度（一个CPU执行多个作业）； 与线性表相同，仍为一对一关系。 顺序队或链队，以循环顺序队更常见。 只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。 关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。 存储结构 运算规则 实现方式 逻辑结构 基本操作：入队或出队，建空队列，判队空或队满等操作。 1. 链队列 （1）InitQueue ( )： 构造一个空队列Q （2）QueueEmpty (Q)： 判断队列是否为空 （3）QueueLength (Q)： 求队列的长度 （4）GetHead (Q)： 返回Q的队头元素，不改变队列状态 （5）E