链式队列的实现细节与运行机制

1、链式队列的实现细节与运行机制【实现方法】数据结构：队列要求只能从对尾进从对头出，对头不动typedef struct tQueueNode 队列结构pBITREE ptree;/存储树节点指针tQueueNode* next;QueueNode,*pQueueNode;typedef struct tQueuepQueueNode rear; /队尾pQueueNode head;对头LinkListQue;几个基本的重要函数Status InitQue(LinkListQue &que) 队头和队尾地址相同que.rear = que.head = (pQueueNode)malloc(si

2、zeof(QueueNode);if(que.rear=NULL II que.head=NULL) return ERROR;que.head-next = NULL;que.head-ptree = NULL;que.rear-next = NULL;que.rear-ptree = NULL;return OK;节点入队Status ENQue(LinkListQue &que,pBITREE pNode) pQueueNode p = (pQueueNode)malloc(sizeof(QueueNode);if(p = NULL)return ERROR;对p进行初始化p-next

3、= NULL;p-ptree = NULL;/入队que.rear-ptree = pNode;que.rear-next = p;que.rear = p;return OK;/将节点从头部出队pQueueNode DeQue(LinkListQue &que)if(que.head = que.rear)return NULL; 空队列，无法出队pQueueNode q;q = que.head;que.head = q-next;return q;从这段代码中，我们很难看出链表队列各个节点是如何联系起来的，现在我用debug工具追踪它运彳丁的每一步：(初始化省去)int main()Li

4、nkListQue listQue;pBITREE tree;InitBiTree(tree,a);pBITREE treel;InitBiTree(tree1,b);InitQue(listQue);ENQue(listQue,tree);ENQue(listQue,tree1);DDueueNode 口 = DMuef listDue):这是测试调用，我设断点单步追踪Status ENQue(LinkListQue &que,pBITREE pNode)pQueueNode p = (pQueueNodeJmalloctsizeofCQueueNode); iF(p = NULL) ret

5、urn ERROR;刚进入入队函数时，链表队列的首尾指针的地址值为均为：0 x020a38d0也就是说，他们指向的是同一个地址当尾节点插入下一个节点时，首尾指针所指向的地址均为：0 x020a3908用一也就是说，不仅首尾指针所指向同一地址，连他们的下一个节点同样指向同一个地址， 副图来说就是：Rear和head完全相同再运行一步：此时p被赋给que.rear，会发生什么变化呢?并运从红色地址可以看到，rear的地址变为与head-next的地址，同样，在调用这个函数， 行到这里的时候，我们再看看追踪结果：此时我们可以看到，链表队列的尾指针rear指向的是head-next-next，也就是说

6、它始终是 一个空节点，始终指向链表head的尾节点，如此说来就是，这个队列只是一个空壳，一个 控制器，负责控制head这个单链表而已。让我们继续，看看如何出队。return NULL; 773IpQueueNode q;q = que.head;0 que.head = q-next;return q;此时追踪结果为:再运行一步的结果为：即将q的next指针赋给que.head，因为我们要将头指针指向的地址 取出来，让它本来指针的下一个节点指针变成新的head从此时可以看到，存储a的节点出队，尾节点不变，首节点指向bInitQue(listQue);ENQue(listQue.tree);EN

7、Que(listQue,tree1);pQueueNode q = DeQue(listQue);iF(q *= NULL)printF(cn,q-ptree-data)free(q)；return O;看看测试结果:a即为出队的数据【总结】1，队列其实就是一个链表，之所以是队列，是因为队列对链表实施入队时只能操作队尾， 出队时只能操作队首的规则。2，在为空队列的时候，加入一个节点，先将首节点指向它（通过que.rear-next = p;），尾 节点指向p，这就实现了首节点的下一个节点指向rear节点的操作。如果再加入一个节 点，那么首节点的最后一个节点指向rear。故：rear节点起到一个装载工得作用3，出队就是将首节点赋给