第3章栈和队列 3.4链队列《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

第三章：栈和队列 3.4.3 链队列 队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由头指针和尾指针唯一确定。 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级 null *q q.front q.rear 非空队列 q.front q.rear null 空队列 *q 链队列示意图 和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型LinkQueue定义为一个结构类型： [请注意这种封装方式，第一个结构体是结点，第二个结构体是头尾指针] typedef struct queuenode{ ElemType data; struct queuenode *next; }QueueNode; typedef struct{ QueueNode *front; QueueNode *rear; }LinkQueue; 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级 下面给出链队列上实现的基本运算： 构造一个空队列： void InitQueue(LinkQueue &Q) { Q.front=Q.rear=(queuenode *)malloc(sizeof(queuenode )); Q.front->next=Q.rear->next=NULL; } 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级 q.front q.rear null 置队空 *q 队列的判空： int QueueEmpty(LinkQueue Q) { return (Q.front->next= =NULL && Q.rear->next= =NULL); } void EnQueue(LinkQueue &Q,ElemType e) { QueueNode *p; p=(QueueNode * )malloc(sizeof(QueueNode)); p–>data=x; p–>next=NULL; Q.rear–>next=p; Q.rear=p; } 入队操作 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级 null *q q.front q.rear 入队 x null p 出队操作： DeQueue(linkqueue *Q) { linkqueue *s; if(EMPTY(Q)) return NULL; s=Q.front->next; Q.front->next=s–>next; if(Q.rear = =s) Q.rear=Q.front; free(s); } 出队 null *q q.rear x null q.front p 存储池 队列的应用 队列在日常生活中和计算机程序设计中，有着非常重要的作用，在此，仅举出两个方面例子来说明它，本教材的应用在主要是图的广度优先遍历，在后面章节中将会遇到。 第一个例子就是CPU资源的竞争问题。在具有多个终端的计算机系统中，有多个用户需要使用CPU各自运行自己的程序，它们分别通过各自终端向操作系统提出使用CPU的请求，操作系统按照每个请求在时间上的先后顺序，将其排成一个队列，每次把CPU分配给队头用户使用，当相应的程序运行结束，则令其出队，再把CPU分配给新的队头用户，直到所有用户任务处理完毕。 第二个例子就是主机与外部设备之间速度不匹配的问题。以主机和打印机为例来说明，主机输出数据给打印机打印，主机输出数据的速度比打印机打印的速度要快得多，若直接把输出的数据送给打印机打印，由于速度不匹配，显然是不行的。所以解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依此写如到这个缓冲区中，写满后就暂停输出，继而去做其它的事情，打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求，主机接到请求后再向缓冲区写入打印数据，这样利用队列既保证了打印数据的正确，又使主机提高了效率。 讨论（本章小结） 线性表、栈与队的异同点 相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。 不同点： ① 运算规则不同，线性表为随机