把项添加到队列中,包括以下几个步骤:
- 创建一个新节点;
- 把项拷贝到节点中;
- 设置节点的next指针为NULL,表明该节点是最后一个节点;
- 设置当前尾节点的next指针指向新节点,把新节点链接到队列中;
- 把rear指针指向新节点,以便找到最后的节点;
- 项数加1。
函数还要处理两种特殊情况:
- 如果队列为空,应该把front指针攻置为指问新节点。因为如果队列中只有一个节点,那么这个节点既是首节点也是尾节点。
- 如果函数不能为节点分配所需内存,则必须执行一些动作。因为大多数情况下我们都使用小型队列,这种情况很少发生。所以,如果程序运行的内存不足,我们只是通过函数终止程序。
/**/
bool EnQueue(Item item, Queue * pq)
{
Node * pnew;//创建一个新节点
if (QueueIsFull(pq))
return false;
pnew = (Node *) malloc( sizeof(Node));//创建一个新节点,为新节点分配空间
if (pnew == NULL)
{
fprintf(stderr,"Unable to allocate memory!\n");
exit(1);
}
CopyToNode(item, pnew);//把项拷贝到节点中
pnew->next = NULL;//设置节点的next指针为NULL,表明该节点是最后一个节点
if (QueueIsEmpty(pq))
pq->front = pnew; /* 项位于队列顶端*/
else
//设置当前尾节点的next指针指向新节点,把新节点链接到队列中
pq->rear->next = pnew;
//把rear指针指向新节点,以便找到最后的节点
pq->rear = pnew; /* 记录队列尾端的位置 */
pq->items++; /* 队列项数+1 */
return true;
}
- 问:在该代码中,为什么执行了else中的pq->rear->next = pnew; 之后,又执行pq->rear = pnew;这两条代码不矛盾吗?
- 答:这两条语句并不矛盾,而是为了确保队列的 rear 指针始终指向队列的最后一个节点。在添加新节点后,我们需要更新 rear 指针,以便指向新的队列尾部。这样在下一次入队操作时,可以直接在队列尾部添加节点,而不需要遍历整个队列来找到尾部节点。