文章目录
一、队列是什么？
队列也是一种线性表，特性为“先进先出”。就像是我们生活中的排队，排队早的人就会早轮到。
队列只能在队头弹出和队尾插入。
二、代码实现
1.存储结构
队列的存储可以使用数组或者链表，由于使用数组在队头弹出时要把整个队列往前整，并不方便，因此本文这里选择的以链表的结构来实现这个队列。
节点设置与链表一样，一个数据域存数据，一个指针域存储下一个节点地址。另外为了尾插方便，定义一个结构体包括了头尾两个指针成员变量。
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
}Queue;
2.常见接口函数
2.1初始化和销毁
初始化和销毁与链表类似比较简单。销毁时需要注意设置一个next指针记录下一个节点，以免释放当前节点后，找不到下一个节点。
void QueueInit(Queue* q)
{
assert(q);
q->head = q->tail = NULL;
}
void QueueDestroy(Queue* q)
{
assert(q);
QNode* cur = q->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
q->head = q->tail = NULL;
}2.2 插入和弹出
进队就像链表的尾插，但由于多了一个尾指针，所以可以节省找尾操作，直接在尾部插入。同时由于没有头节点，所以当链表为空时，要作为一个特殊情况处理。
出队只要把释放头指针，再往后移一个节点。但是这里面有个比较坑的就是。但队中只剩一个节点时，继续pop。头指针与尾指针位置相同，头指针free完后，移向节点的next域为空。但这时tail指针仍然指向刚刚释放的节点位置，形成野指针的问题。因此我们可以在头指针为空时，将尾指针也设置为空。
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* newNode = (QNode*)malloc(sizeof(QNode));
if (!newNode)
{
printf("malloc fail");
exit(-1);
}
newNode->data = data;
newNode->next = NULL;
if (q->head == NULL)
{
q->head = q->tail = newNode;
}
else
{
q->tail->next = newNode;
q->tail = newNode;
}
}
// 队头出队列
void QueuePop(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
QNode* next = q->head->next;
free(q->head);
q->head = next;
if (q->head == NULL)
{
q->tail == NULL;
}
}2.3其他接口
其他的接口就比较简单了，大多一两句代码就可以实现。
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->head->data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->tail->data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
assert(q);
int count = 0;
QNode* cur = q->head;
while (cur)
{
count++;
cur = cur->next;
}
return count;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q)
{
assert(q);
return q->head == NULL;
}
总结
总体来说，队列的链表实现比较容易。可以在一些特定的场合利用队列“先进先出”的特性。