关于链式队列是否需要头结点
发布时间：2010/6/29 15:55:41 来源：城市学习网 编辑：ziteng
队列是一种特殊的线性表，它只允许在表头进行删除操作，而在表尾进行插入操作，是一种先进先出的数据结构。
队列可以采用数组存储，也可以采用链式存储。关于链式存储常见的又有两种：带头结点和不带头结点。我们建议采用带头结点的实现方式，因为，这样可以大大简化对队列的处理。
下面以入队操作为例，对本文观点进行了进一步的阐述。假设基本结构的定义为：
typedef int datatype;
typedef struct node
{
datatype data;
struct node* next;
}listnode, *linknode;
typedef struct
{
linknode front;
linknode rear;
}linkqueue;
带头结点的链队入队实现：
void enqueue(linkqueue* q, datatype x){
linknode p = (linknode)malloc(sizeof(listnode));
p->data = x;
p->next = NULL;
q->rear->next = p;
q->rear = p;
}
不带头结点的链队入队实现：
void enqueue(linkqueue* q, datatype x){
linknode p = (linknode)malloc(sizeof(listnode));
p->data = x;
p->next = NULL;
if(q->front == NULL){
q->front = p;
q->rear = p;
return;
}
q->rear->next = p;
q->rear = p;
}
比较上面两段程序，带头结点的链队的入队操作，只要把新生成的结点加到尾结点后即可。而不带头结点的操作则还要注意到边界操作，假如是第一次入队，需修改队头指针。同样的道理，对于出队操作，假如是最后一个结点出队，需要注意修改队尾指针。由此，我们建议链式队列最好采用带头结点的实现方式。
