前言:
准备工作:本人习惯将文件放在test.c、SeqList.c、SeqList.h三个文件中来实现,其中test.c用来放主函数,SeqList.c用来放调用的函数,SeqList.h用来放头文件和函数声明
目录
什么是队列?
队列中的数据是按照先进先出的顺序的,也就是说先进去的数字也先出来
队列的节点结构
队列采用的单链表的结构,所以与单链表差异不大
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
但是我们在操作中,因为队列是要先进先出,其实也就是尾部进数据,头部出数据,所以我们要定义一个头指针和一个尾指针指向头尾两个数据,这样有利于我们后面增加或者删除数据,我们可以再定义一个结构体来存放这两个指针
typedef struct Queue
{
QNode* phead; //头指针
QNode* ptail; //尾指针
int size; //队列中的元素个数
}Queue;
队列的基本操作
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//增加
void QueuePush(Queue* pq,QDataType x);
//删除
void QueuePop(Queue* pq);
//取队头
QDataType QueueFront(Queue* pq);
//取队尾
QDataType QueueBack(Queue* pq);
//取长度
QDataType QueueSize(Queue* pq);
//判断是否为空
bool QueueEmpty(Queue* pq);
看上面的函数声明部分我们就可以看到我们每一步要实现的内容,接下来,我们就来一步一步进行实现
1、初始化
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
参数全是一个结构体指针,而且肯定不能为空,所以我们下面的函数基本都要对pq进行断言
2、销毁
//销毁
void QueueDestroy(Queue* pq)
{
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
3、增加(插入数据)
//插入
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
newnode->data = x;
newnode->next = NULL;
//判断头部是否为空
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
用单链表插入数据必须要考虑头部为空和不为空两种情况
4、删除
栈和队列都有一个特点就是,数据只会输出一遍,也就是数据一经输出就会销毁删除
如下:
1在输出之后就会被删除,删除的代码如下:
//删除
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
//1、一个节点
//2、多个节点
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
QNode* ptr = pq->phead->next;
free(pq->phead);
pq->phead = ptr;
}
}
这里面又分为两种情况,难度不大,根据注释自行体会即可
5、取队头、取队尾、取长度、判断头指针是否为空
取队头
//取队头
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->phead->data;
}
取队尾
//取队尾
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
取长度
//取长度
QDataType QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
判断头指针是否为空(这个函数应用上可以在下面的完整案列上体会一下)
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL;
}
完整的队列实例
test.c
//队列
void TestQNode()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
printf("%d\n", QueueSize(&q));
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
QueueDestroy(&q);
}
int main()
{
TestQNode();
return 0;
}
SeqList.h
//队列
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//增加
void QueuePush(Queue* pq,QDataType x);
//删除
void QueuePop(Queue* pq);
//取队头
QDataType QueueFront(Queue* pq);
//取队尾
QDataType QueueBack(Queue* pq);
//取长度
QDataType QueueSize(Queue* pq);
//判断是否为空
bool QueueEmpty(Queue* pq);
SeqList.c
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
//销毁
void QueueDestroy(Queue* pq)
{
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
//插入
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
newnode->data = x;
newnode->next = NULL;
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
//删除
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
//1、一个节点
//2、多个节点
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
QNode* ptr = pq->phead->next;
free(pq->phead);
pq->phead = ptr;
}
}
//取队头
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->phead->data;
}
//取队尾
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
//取长度
QDataType QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL;
}
运行后结果:
总结
创作不易,还请各位大佬点赞支持一下!!!