🐱作者：傻响
🐱专栏：《数据结构与算法》
🔥格言：你只管努力，剩下的交给时间！
一、队列
1 队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头 。
栈符合 - 后进先出（First In First Out ）
2 队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数 组头上出数据，效率会比较低。
1.1 队列的各个接口
// 队列的链式访问结构
typedef int QDataType;
typedef struct QListNode
{
QDataType data;
struct QListNode* next;
}QListNode;
// 队列结构
typedef struct Queue
{
QListNode* head;
QListNode* tail;
size_t size;
}Queue;
/*
* - 接口实现
*/
// 队列初始化
void QueueInit(Queue* pQ);
// 队列内存销毁
void QueueDestroy(Queue* pQ);
// 队尾入队列
void QueuePush(Queue* pQ, QDataType data);
// 队头出队列
void QueuePop(Queue* pQ);
// 获取队列头部元素
QDataType QueueFront(Queue* pQ);
// 获取队列尾部元素
QDataType QueueBack(Queue* pQ);
// 获取队列中有效元素个数
int QueueSize(Queue* pQ);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* pQ);1.2 队列的初始化
// 初始化队列函数实现
void QueueInit(Queue* pQ)
{
// 断言：保护形参的指针。
assert(pQ);
// 初始化
pQ->head = pQ->tail = NULL;
}1.3 栈的释放
// 队列内存销毁
void QueueDestroy(Queue* pQ)
{
// 断言：保护形参的指针。
assert(pQ);
// 销毁所有的节点
QListNode* pCurrent = pQ->head;
while (pCurrent != NULL)
{
QListNode* pDelete = pCurrent;
pCurrent = pCurrent -> next;
// 销毁
free(pDelete);
pDelete = NULL;
}
// 初始化
pQ->head = pQ->tail = NULL;
}1.3 队尾入队列
入队:因为是基于没有头的链表-》会出现两种情况：
// 队尾入队列
void QueuePush(Queue* pQ, QDataType data)
{
// 断言：保护形参的指针。
assert(pQ);
// 开辟新节点
QListNode* newNode = (QListNode*)malloc(sizeof(QListNode));
if (newNode == NULL)
{
perror("QueuePush malloc fail!");
exit(-1);
}
else // 开辟成功
{
newNode->data = data;
newNode->next = NULL;
}
// 开辟新节点成功
if (pQ->tail == NULL)
{
pQ->head = pQ->tail = NULL;
}
else // 链接
{
pQ->tail->next = newNode;
pQ->tail = pQ->tail->next;
}
}1.4 队头出队列
// 队头出队列
void QueuePop(Queue* pQ)
{
// 断言：保护形参的指针。
assert(pQ);
// 如果是最后一个节点
if (pQ->head->next == NULL)
{
free(pQ->head);
pQ->head = pQ->tail = NULL;
}
else // 如果不是最后一个节点
{
QListNode* pDelete = pQ->head;
pQ->head = pQ->head->next;
free(pDelete);
pDelete = NULL;
}
}1.5 获取队列头部元素
// 获取队列头部元素
QDataType QueueFront(Queue* pQ)
{
// 断言：保护形参的指针。
// 断言：判断队列不为空。
assert(pQ);
assert(!QueueEmpty(pQ));
return pQ->head->data;
}1.6 获取队列尾部元素
// 获取队列尾部元素
QDataType QueueBack(Queue* pQ)
{
// 断言：保护形参的指针。
// 断言：判断队列不为空。
assert(pQ);
assert(!QueueEmpty(pQ));
return pQ->tail->data;
}1.7 获取队列中有效元素个数
// 获取队列中有效元素个数
int QueueSize(Queue* pQ)
{
// 断言：保护形参的指针。
assert(pQ);
遍历计数
//QListNode* pCurrent = pQ->head;
//int count = 0;
//while (pCurrent != NULL)
//{
// ++count;
// pCurrent = pCurrent->next;
//}
// 返回计数。
return pQ->size;
}1.8 检测队列是否为空
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* pQ)
{
// 断言：保护形参的指针。
assert(pQ);
return pQ->head == NULL && pQ->tail == NULL;
}1.9 队列测试
void TestQueue()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
printf("\n");
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePush(&q, 5);
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
QueueDestroy(&q);
}2.0运行效果
