03栈与队列2

3-6第三章栈与队列第三节队列一、逻辑结构只能在一端(队尾rear)插入，在另一端(队头front)删除的线性表。先进先出表FIFO(FirstInFirstOut)现实原形：排队模型。基本操作：进/出队列判别队列满/空二、链式存储结构TypedefstructQueueNode//队列中的结点类型{ElemTypedata;structNode*link;}QUEUENODE;typedefstruct//队列类型{QUEUENODE*front,*rear;}LINKQUEUE;LINKQUEUEQ;初始化空队列：Q.front==NULLQ.rear==NULL1、入队列StatusLINKQUEUE_Enter(LINKQUEUE&Q,ElemTypee){QUEUENODE*p;p=(QUEUENODE*)malloc(sizeof(QUEUENODE));if(!p)return(OVERFLOW);p-data=e;p-link=NULL;3-7if(Q.front==NULL)Q.front=Q.rear=p;else{Q.rear-link=p;Q.rear=p;}return(OK);}2、出队列StatusLINKQUEUE_Leave(LINKQUEUE&Q,ElemType&e){QUEUENODE*p;if(Q.front==NULL)return(UNDERFLOW);p=Q.front;Q.front=p-link;if(Q.rear==p)Q.rear=NULL;e=p-data;free(p);return(OK);}三、顺序存储结构初始化建空队列时,令front=rear=0,每当插入新的队尾元素时,“尾指针加1”;每当删除队头元素时,“头指针加1”。因而，非空队列中，头指针始终指向队列头元素，而尾指针始终指向队尾元素的下一个位置。当队列处于D状态时，不可再继续插入新的队尾元素，又不宜进行存储再分配扩大数组空间，因为队列的实际可用空间未占满。这时我们解决的方法是将顺序队列臆造为一个环状的空间，称之为循环队列。循环队列的存储结构：#defineQUEUE_SIZE100//初始化时分配的空间typedefstruct{ElemType*base;//存储空间的起始地址intfront,rear;}SqQueue;SqQueueQ;//定义一个队列结构3-81、初始化队列StatusSqQueue_Init(SqQueue&Q){Q.base=malloc(QUEUE_SIZE*sizeof(ElemType));if(!Q.base)return(OVERFLOW);Q.front=Q.rear=0;return(OK);}队列空：Q.front==Q.rear进队列：*(Q.base+Q.rear)=e;Q.rear++;出队列：e=*(Q.base+Q.front);Q.front++;队列满：Q.rear==QUEUE_SIZE=》假溢出改进：进队列：Q.rear=(Q.rear+1)%QUEUE_SIZE出队列：Q.front=(Q.front+1)%QUEUE_SIZE队列空：Q.front==Q.rear当队列中有QUEUE_SIZE个元素时：Q.front==Q.rear=》必须浪费一个结点空间队列满：(Q.rear+1)%QUEUE_SIZE==Q.front2、入队列StatusSqQueue_Enter(SqQueue&Q,ElemTypee){if((Q.rear+1)%QUEUE_SIZE==Q.front)return(OVERFLOW);*(Q.base+Q.rear)=e;Q.rear=(Q.rear+1)%QUEUE_SIZE;return(OK);}3-93、出队列StatusSqQueue_Leave(SqQueue&Q,ElemType&e){if(Q.rear==Q.front)return(UNDERFLOW);e=*(Q.base+Q.front);Q.front=(Q.front+1)%QUEUE_SIZE;return(OK);}4、元素计数(Q.rear-Q.front+QUEUE_SIZE)%QUEUE_SIZE值的范围0……QUEUE_SIZE-1思考：一定要浪费一个结点空间？利用一个标志变量Q.flag(0:非满，1:非空)。typedefstruct{ElemTypedata[M];intfront,rear;intflag;}SqQueue;intEmpty(SqQueueQ){if(Q.front==Q.rear&&Q.flag==0)return(1);return(0);}intFull(SqQueueQ){if(Q.front==Q.rear&&Q.flag==1)return(1);return(0);}1、初始化队列StatusSqQueue_Init(SqQueue&Q)3-10{Q.front=Q.rear=0;Q.flag=0;}2、入队列StatusSqQueue_Enter(SqQueue&Q,ElemTypee){if(Full(Q))return(OVERFLOW);…………Q.flag=1;//非空return(OK);}3、出队列StatusSqQueue_Leave(SqQueue&Q,ElemType&e){if(Empty(Q))return(UNDERFLOW);…………;Q.flag=0;//非满return(OK);}第五节队列的实例：离散事件的模拟一、排队问题银行营业所应设置几个柜台？1、设置N柜台时，计算顾客的平均等待时间；2、选择合适的N值。加油站的故事：一个加油站只有一台加油机,平均为每辆车加油需要5分钟,假定一个小时内,有20辆车随机进入加油站加油,计算每辆车的平均等待时间.1、代数方法:SERVER_TIME=5分钟/加油，N=20辆车，DURATION=603-11分钟，一个加油口，求平均等待时间？到达时间序列：T1,T2,T3,.....,TN设第i辆车的等待时间为Wi,则W1=0，当Ti+Wi+SERVER_TIMETi+1时：Wi+1=Ti+Wi+SERVER_TIME-Ti+1否则：Wi+1=02、队列方法ok_time：加油机为第i辆汽车服务完毕的时刻arrive_time：第i辆汽车到达加油站的时刻wait_time：所有汽车等待服务的时间总和#defineN20#defineDURATION60#defineSERVER_TIME5typedefstruct{floattime[N];intfront,rear;//队列指针}TimeQueue;main(){TimeQueuequeue;inti;floatok_time,arrive_time,wait_time;init(queue);//初始化到达时间队列ok_time=wait_time=0;//队列不空，循环while(!empty(queue)){arrive_time=arrive(queue)if(ok_timearrive_time)wait_time+=ok_time-arrive_time;/*需要等待*/elseok_time=arrive_time;/*不需等待*/ok_time+=SERVER_TIME;//当前汽车加油完毕的时刻}3-12printf(Complishedtime:%f\n,ok_time);printf(AverageTime:%f\n,wait_time/N);}//初始化到达时间队列voidinit(TimeQueue*queue){inti;for(i=0;iN;i++)queue-time[i]=random(DURATION);sort(queue-time,N);queue-front=0;queue-rear=N;}//取一个进站事件，即出队列floatarrive(TimeQueuequeue){floattime1;time1=queue.time[front];queue.front++;return(time1);}//是否队列空intempty(TimeQueuequeue){if(queue.rear==queue.front)return(1);elsereturn(0);}思考二台加油机？K台加油机？ok_time[K]二、多用户的磁盘I/O在多用户/多任务的操作系统中，每个任务可能随机提出磁盘的I/O要求，那么系统按怎样的次序来处理这些请3-13求呢？I/O排序问题：DiskSchedulingPolicy(DSP)TI/O=Tseek+Trotation+TtransmissionTI/O≈C1(Ttarget-Tinitial)+C2(C1、C2为常数)DSP的策略：1、FIFO：公平？何谓公平？最小的平均等待时间。2、ShortSeekTimeFirst(SSFT)：带优先权的队列每个请求的优先权=abs(Ttarget-Tcurrent)权最高者出队列。重大缺陷：可能长期忽略某些服务请求3、改进SSFT：保持磁头前进的方向，里外循环变化。三、逐行打印二项展开式(a+b)n的系数杨辉三角形：voidYANGVI(intn,intcoef[]){Queueq;inti,j,e1,e2;q.MakeEmpty();//队列初始化q.EnQueue(1);q.EnQueue(1);q.EnQueue(0);//第0行for(i=1;i=n;i++)//逐行计算{q.EnQueue(0);e1=q.DeQueue();e2=q.DeQueue();for(j=1;j=i+1;j++){q.EnQueue(e1+e2);e1=e2;e2=q.DeQueue();}3-14}q=coef}四、优先级队列(PriorityQueue)不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。