【版权声明：转载请保留出处：blog.csdn.net/algorithm_only。邮箱：liuy0711@foxmail.com】
队列是一种先进先出的线性表，也是一种操作受限的线性表，只允许在表的头部删除元素和尾部添加元素。队列有链式表示和顺序表示。队列的链式表示由于在表头和表尾操作，需要两个指针分别指向对头和队尾。空的链式队列判决条件为对头指针和队尾指针是否指向同一个结点（头节点）。
- 链式队列的存储结构
#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;
}
- 总结
链队列的操作即是单链表操作的特殊情况，只需修改头指针和尾指针即可。
- 源码实现