前言:

在学习完数据结构顺序表和链表之后,其实我们就可以做很多事情了,后面的栈和队列,其实就是对前面的顺序表和链表的灵活运用,今天我们就来学习一下队列的原理和应用。

准备工作:本人习惯将文件放在test.c、SeqList.c、SeqList.h三个文件中来实现,其中test.c用来放主函数,SeqList.c用来放调用的函数,SeqList.h用来放头文件和函数声明

目录

什么是队列?

队列的节点结构

队列的基本操作

1、初始化

2、销毁

3、增加(插入数据)

4、删除

5、取队头、取队尾、取长度、判断头指针是否为空

完整的队列实例

总结

什么是队列?

队列中的数据是按照先进先出的顺序的,也就是说先进去的数字也先出来

因为队列的这种性质,所以队列我们用链表来实现比顺序表方便很多,因为用顺序表每插入一个数或者删除一个数都需要遍历整个数组,这样就会很容易出错且不够方便,我们一般采用单链表来实现队列

队列的节点结构

队列采用的单链表的结构,所以与单链表差异不大

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;

}

运行后结果:

总结

总之,其实队列就是对链表的应用,熟练栈和队列,对我们巩固顺序表和链表帮助很大,当然,队列在一些场景下很实用,后面我会出一个专门的习题讲解篇章,讲数据结构的一些经典题型,感兴趣的可以点赞关注一下

创作不易,还请各位大佬点赞支持一下!!!

推荐文章

评论可见,请评论后查看内容,谢谢!!!
 您阅读本篇文章共花了: