第3栈和队列精要.ppt

* 北京林业大学信息学院 typedef struct QNode{ QElemType data; struct Qnode *next; }Qnode, *QueuePtr; typedef struct { QueuePtr front; //队头指针 QueuePtr rear; //队尾指针 }LinkQueue; 链队列 * 北京林业大学信息学院 (a) 空队列 (b) 元素x入队列 (d) 元素x出队列 (c) 元素y入队列 链队列 * 北京林业大学信息学院 Status InitQueue (LinkQueue Q){ Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode)); if(!Q.front) exit(OVERFLOW); Q.front-next=NULL; return OK; } 链队列初始化 * 北京林业大学信息学院 Status DestroyQueue (LinkQueue Q){ while(Q.front){ Q.rear=Q.front-next; free(Q.front); Q.front=Q.rear; } return OK; } 销毁链队列 * 北京林业大学信息学院 Status QueueEmpty (LinkQueue Q){ return (Q.front==Q.rear); } 判断链队列是否为空 * 北京林业大学信息学院 Status GetHead (LinkQueue Q, QElemType e){ if(Q.front==Q.rear) return ERROR; e=Q.front-next-data; return OK; } 求链队列的队头元素 * 北京林业大学信息学院 Status EnQueue(LinkQueue Q,QElemType e){ p=(QueuePtr)malloc(sizeof(QNode)); if(!p) exit(OVERFLOW); p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK; } 链队列入队 p * 北京林业大学信息学院 Status DeQueue (LinkQueue Q,QElemType e){ if(Q.front==Q.rear) return ERROR; p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear==p) Q.rear=Q.front; free(p); return OK; } 链队列出队 p * 北京林业大学信息学院 【例】汽车加油站随着城市里汽车数量的急速增长，汽车加油站也渐渐多了起来。通常汽车加油站的结构基本上是：入口和出口为单行道，加油车道可能有若干条。每辆车加油都要经过三段路程，第一段是在入口处排队等候进入加油车道；第二段是在加油车道排队等候加油；第三段是进入出口处排队等候离开。实际上，这三段都是队列结构。若用算法模拟这个过程，就需要设置加油车道数加2个队列。　 3.5 　队列的应用 * 北京林业大学信息学院 【例】模拟打印机缓冲区在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样会降低主机的使用效率。为此人们设想了一种办法：为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的正确性，又提高了