|
????????实现队列可选用链表和数组，在这里选用的是链表（方便删除），且为了提高尾插效率，在队列结构体里加入了一个指向队尾的尾指针。
?Queue.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDatatype;
typedef struct QueueNode//定义队列结点结构体
{
QDatatype data;
struct QueueNode* next;
}QNode;
typedef struct Queue//队列结构体，用于记录头尾结点
{
QNode* head;
QNode* tail;
}Queue;
void QueueInit(Queue* pq);//初始化函数
void QueueDestroy(Queue* pq);//销毁函数
void QueuePush(Queue* pq, QDatatype x);//插入
void QueuePop(Queue* pq);//删除
QDatatype QueueFront(Queue* pq);//取出队头的数据
bool QueueEmpty(Queue* pq);//判断队列是否为空
int QueueSize(Queue* pq);//计算队列长度
?Queue.c
#include"Queue.h"
void QueueInit(Queue* pq)//初始化函数（用于初始化队列结构体）
{
assert(pq);//防御性检查，传入队列结构体不应为空
pq->head = pq->tail = NULL;
}
void QueueDestroy(Queue* pq)//销毁函数
{
assert(pq);//防御性检查，传入队列结构体不应为空
QNode* cur = pq->head;//记录当前要删除的结点
while (cur)//遍历队列链表中的每个结点，依次删除
{
QNode* next = cur->next;
free(cur);
cur = next;
}
//链表类型的数据结构销毁时一定要 遍历每个结点 ，依次free掉
pq->head = pq->tail = NULL;//置空，防止野指针
}
void QueuePush(Queue* pq, QDatatype x)//插入（尾插）
{
assert(pq);//防御性检查，传入队列结构体不应为空
//建立新的结点
QNode* newnode = (QNode*)malloc(sizeof(QNode));//注意sizeof()的大小,传入的如果是指针就只有8个字节
if (newnode == NULL)
{
printf("malloc fail!\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
//如果队列为空,更新头尾结点
if (pq->head == NULL)
{
pq->head = pq->tail = newnode;
}
else//如果队列不为空，尾插
{
pq->tail->next = newnode;//尾插
pq->tail = newnode;//更新尾结点
}
}
void QueuePop(Queue* pq)//删除(头删)
{
assert(pq);//防御性检查，传入队列结构体不应为空
assert(!QueueEmpty(pq));//队列为空，不支持删除
//当队列仅剩下一个结点时，删除后要，使头尾指针置空,以防止野指针
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else//当队列还有多个结点时，头删
{
QNode* next = pq->head->next; //保存第二个结点
free(pq->head);//释放头结点
pq->head = next;//更新头结点
}
}
QDatatype QueueFront(Queue* pq)//取出队头的数据
{
assert(pq);//防御性检查，传入队列结构体不应为空
assert(!QueueEmpty(pq));//队列为空，不支持取数据
return pq->head->data;
}
bool QueueEmpty(Queue* pq)//判断队列是否为空
{
assert(pq);//防御性检查，传入队列结构体不应为空
return pq->head == NULL;
}
int QueueSize(Queue* pq)//计算队列长度
{
assert(pq);//防御性检查，传入队列结构体不应为空
int size = 0;
//遍历队列链表中的每个结点，计算链表长度
QNode* cur = pq->head;
while (cur)
{
++size;
cur = cur->next;
}
return size;
}
QueueTest.c(测试用例)?
#include"Queue.h"
int main()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
printf("%d\n", QueueSize(&q));
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
putchar(10);
QueueDestroy(&q);
return 0;
}
|