数据结构之栈对列串课件(编辑修改稿)

数据结构之栈对列串课件(编辑修改稿)内容摘要：

空。 其中的判断条件是不科学的。 实际上，当 =maxsize1,时，对列未必满，出现了 “假溢出”现象。 采用循环对列可以解决这一问题。 循环队列 循环队列就是把顺序队列的头和尾相连，构成一个闭环。 （见图） 当尾指针 =max1 时，若要插入 (删除）一个元素， 则要插入到第 0个位置， 即 [(max1)+1] % max=0 （取余数）。 若 max=8 时，要插入一个元素，应插入到第 0个位置，即 (+1) % max=(7+1) % 8=0 如何判断循环队列的“空”和“满”呢。 先看一个例子。 例：一循环队列 max =6，队列中已有 3个元素，研究其插入 3个元素后和删除 3个元素后的状态。 可以看出，不管队列是“满”还是“空”，都有front=rear。 那么，如何判断是“空”还是“满”呢。 解决方法： 1. 另设一标记，以区分队列是“空”还是“满”； 2. 不设标记，把 尾指针加 1后等于头指针 作为队 满的条件。 这样 , 队满的条件： (+1)%max= 队空的条件： = 循环队列入队函数 Int insert(Quetype Q, elementtype x) { if (( +1)%maxsize==) { printf(“队列溢出 ” )。 return(1)。 } =(+1)%maxsize。 []=x。 return(0)。 } 循环队列出队函数 { if (==) { printf (“是空队列。 \n”)。 return(1)。 } =(+1)%maxsize。 Return([]。 } 队列的应用 对于各种具有“先进先出”需排队处理的问题，都可以应用队列来解决。 例如，操作系统在管理和分配系统资源时，大量的应用了队列这种数据结构。 1) 队列在输入 /输出管理中的应用 2) 对 CPU的分配管理 返回 例 对于循环队列，试写出求队列长度的算法。 解 1：设队列的最大元素个数为 n，设一个计数器，将其初始值设为 0。 从队头开始，沿着队列顺序搜索，每搜索一个元素，计数器加 1，直到队尾，计数器的最终值即为队列的长度。 解 2：利用队头指针与队尾指针也可求出队列的长度： 当 r≥f 时， length=rf 当 rf 时， length=n(fr) 例3.2算法1 int Que_Length (Queue,int f,r,n) { int length,k。 length=0。 k=f。 while (k!=r) { length++。 k=(k+1)%n } return(length)。 } 例 2 int Que_lenrth(Queue,f,r,n) { int length=0。 if (r=f) length=rf。 else length=n(fr)。 return(length)。 } 返回 队列的链式存储结构 增设两个指针，分别指向队列的头和尾， Head …… rear 队列空时 : head rear ^ ^ 结点的定义 Typedef struct node { elementtype data。 Struct node *next。 }Qlnode。 插入结点： P head rear rear ^ x ^ 删除结点： Head rear ^ 插入算法 Int insertque(head,rear,x) { p=malloc(sizeof(Qlnode))。 If (p=null) { printf(“队列溢出” )。 Return(1)。 } Pdata=x。 pnext=null。 rearnext=p。 rear=p。 Return(0)。 } 删除算法 Deleteque (head,rear) { if (headnext=null) { prin。