链式队列的实现

队列是一种先进先出的线性表，也是一种操作受限的线性表，只允许在表的头部删除元素和尾部添加元素。队列有链式表示和顺序表示。队列的链式表示由于在表头和表尾操作，需要两个指针分别指向对头和队尾。空的链式队列判决条件为对头指针和队尾指针是否指向同一个结点（头节点）。

• 链式队列的存储结构

#define OK           1
#define NULL_QUEUE       0
#define ERROR           -1

typedef struct qnode{
    elemtype        data;
    struct qnode        *next;
}lqnode, *linkq;

typedef struct {
    linkq       front;
    linkq       rear;
}linkqueue;

• 初始化链式队列

int init_linkqueue(linkqueue *lq)
{
    lq->front = (linkq)malloc(sizeof(lqnode));
    if (!lq->front)
        return ERROR;

    lq->rear = lq->front;
    lq->front->next = NULL;

    return OK;
}

申请一个头结点，将地址赋给头指针和尾指针，next域置空，类似于链表初始化。

• 元素进队列

int in_linkqueue(linkqueue *lq, elemtype e)
{
    linkq       p;

    p = (linkq)malloc(sizeof(lqnode));
    if (!p)
        return ERROR;

    p->data = e;
    p->next = NULL;
    lq->rear->next = p;
    lq->rear = p;

    return OK;
}

链队列元素进队将元素添加在队列的尾部，类似于线性表尾插法添加元素。

• 元素出队列

int out_linkqueue(linkqueue *lq, elemtype *e)
{
    linkq       p;

    if (lq->front == lq->rear)
        return NULL_QUEUE;

    p = lq->front->next;
    *e = p->data;
    lq->front->next = p->next;
    if (lq->rear == p)
        lq->rear = lq->front;
    free(p);

    return OK;
}

链队列元素出队列将队首元素删除，此时需注意一点，在删除最后一元素是队尾指针也被删除了，应当重新为队尾指针赋值。

• 取得队列长度

int get_queue_len(linkqueue lq)
{
    int     i = 0;
    linkq       p = lq.front;

    while (p != lq.rear) {
        ++i;
        p = p->next;
    }

    return i;
}

• 总结

链队列的操作即是单链表操作的特殊情况，只需修改头指针和尾指针即可。