Question

C语言队列的一些问题~

现在有如下定义：
typedef struct node{
Item item;
struct node * next;
} Node;

typedef struct queue{
Node * front; /* pointer to front of queue */
Node * rear; /* pointer to rear of queue */
int items; /* number of items in queue */
} Queue;
然后加入队列的实现代码是这样的：
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;
if (QueueIsEmpty(pq))
pq->front = pnew; /* item goes to front */
else
pq->rear->next = pnew; /* link at end of queue */
pq->rear = pnew; /* record location of end */
pq->items++; /* one more item in queue */

return true;
}
然后我很想不通的地方是如果队列很长，每个借点的next是指向哪里的？还有怎么解释
pq->rear->next = pnew;
pq->rear = pnew;
pnew已经复制给next了，为什么还要给rear呢？

Answer 1

pq->rear->next = pnew这个代码从队列的尾部增加新节点，
然后pq->rear = pnew更新队列尾部指针。队列的数据结构形式就是由一个头front指针，一个尾rear指针来表征，items的设计是用空间换时间，涉及队列大小的操作会非常方便。
队列的特征是先进先出，你给出的链式实现，其实就跟一个链表一样，链表的添加删除如果能理解了，队列只是链表的元素增加/删除 按先进先出特点的一种实现。
但对于队列来说，实现方式不是重点，先进先出的性质才是重点，这在实际应用中很多，比如排队叫号。

Answer 2

你只需要记住一点：
rear始终指向最后一个元素，就像front始终指向头部一样，不能改变；next始终指向最近插入的一个元素。【这是仅仅只是我的理解。】

Answer 3

队列是先进先出，就这个思想，自己想办法吧

追问

这个我当然知道……

追答

• 不知道还问