数据结构——队列
好了，前面我们已经了解了栈的实现后，现在让我们来了解一下与它相关的队列的实现吧！
队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
它的结构图：
现在，我们先来与栈进行对比区别：
我们浅浅来回顾一下栈的内容
1.栈是一种后进先出的数据结构，队列是先进先出的
2.栈只能在栈顶进行输入的插入和删除操作
3.栈是有入栈和出栈操作，出栈就是从栈中删除一个元素
4.顺序表和链表都可以用来实现栈，不过一般都使用顺序表，因为栈想当于是阉割版的顺序表，只用到了顺序表的尾插和尾删操作，顺序表的尾插和尾删不需要搬移元素效率非常高，故一般都是使用顺序表实现
如果是链栈，一般需要进行头插或者头删操作，而顺序栈一般进行尾插和尾删操作，链表的操作比顺序表复杂，因此使用顺序结构实现栈更简单
至此，那么在队列中更适合用那种形式呢？
队列适合使用链表实现，使用顺序结构(即固定的连续空间)实现时会出现假溢出的问题，因此大佬们设计出了循环队列，循环队列就是为了解决顺序结构实现队列假溢出问题的（这个后面会写）
为了解决后面的疑惑，我们先来分清下面的问题
有人会问， 为什么之前写的链表和栈有时候用指针，有时候用结构体？
答：单链表用指针：不管是带哨兵位还是不带，总是有一个指针指向第一个节点。要么指向头节点，要么某一个节点
而栈用结构体：如果也搞成一个栈的指针可不可以？没必要。
如果搞成那样，就会出现恶心的事情：这个栈的init得去malloc
如果给你一个指针，你去malloc怎么办，init这里是不是就得用二级指针（麻烦）
把结构体malloc出来。那现在为啥不要呢？这本身就是一个结构体，不需要malloc了
所以，你要改变结构体，你就用结构体的指针就够了啊。
但是，如果你想外面定义一个指针，里面再去malloc也是可以的，要么用二级指针/返回值
在栈初始化那里，malloc后给给ps->a。，那么有人又问了，为啥这里又没有用二级呢？因为
在这个地方，改变的是结构体的成员，要改变结构体，结构体的指针够不够？之前说过要改变int，用int*。里面传指针，必须要有解引用。回到那里，你是不是要改变结构体，那ps是结构体的指针，结构体的指针，那么这个->是不是就相当于解引用这种东西
好了，有了上面的了解，我们开始下一步了。
现在我们来实现一下队列。
首先，我们明白：队列是先进先出
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低
即下面图：
首先，我们来定好框架：
typedef char QDatatype;
链式结构：表示队列
typedef struct QueueNode
{
struct QueueNode* next;
QDatatype data;
}QNode;
队列的结构
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;解释：为了更加方面，我们采用的是两个结构体的方式， 目的是可以让队列可以在一端进行插入数据，在另一端进行删除，所以我们再定义一个结构，里面含有两个指针，指向队列的头和尾
初始化部分
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}这里想一想为什么要断言？
因为队列可以为空，但是指向头指针和尾指针的结构体不能为空，所以一开始就要断言。
然后把头尾指针置空，size为0.即完成了初始化啦。
接着，我们有了初始化，必定会有销毁的函数，
销毁部分
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
解释：
1.同样，不能为空，我们得断言。
2.如下图：依次释放，最后再把head和tail置为空，size置0.
插入部分
void QueuePush(Queue* pq, QDatatype x)
{
创建新节点
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
放数据
newnode->data = x;
newnode->next = NULL;
if (pq->head == NULL)
{
assert(pq->tail == NULL);
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
解释：
因为队列（先入先出）只能尾那边插。
1.创建新节点，即malloc一个。
2.过程
这里一开始就空的话，得断言一下此时的tail也是和head一样都是空的。
3.最后，你插入了一个数据，size的大小必然也是变的，得更新一下。
删除部分
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head != NULL);
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;
}
pq->size--;
}1.队列中的删除部分在头那边删
2.指向头指针和尾指针的结构体不能为空，一开始同样断言。
3.此外，你要删除，一开始肯定是得有数据的，不然也没意义删了，因此也要保证你的头指针不能为空。也要断言。
4. 
那么，怎么判断只有一个数据的时候呢？
答：即判断head的下一个是否为空
4.多个数据的时候，先定义一个next指针，指向head的下一个，再释放就可以了。
5.最后，再更新size--就完成了。
得出size大小
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}判断是否空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
}返回头数据
QDatatype QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
返回尾巴数据
QDatatype QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}由于这几个部分都比较简单，就不再一一解释了。
最后，附上总代码。
Queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void QInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
void QDestory(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
void QueuePush(Queue* pq, QDatatype x)
{
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->data = x;
newnode->next = NULL;
if (pq->head == NULL)
{
assert(pq->tail == NULL);
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
void QueuePop(Queue* pq)
{
assert(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;
}
pq->size--;
}
int Size(Queue* pq)
{
assert(pq);
return pq->size;
}
bool QEmpty(Queue* pq)
{
assert(pq);
return pq->size==0;
}
QDatatype QueueFront(Queue* pq)
{
assert(pq);
assert(!QEmpty(pq));
return pq->head->data;
}
QDatatype QueueBack(Queue* pq)
{
assert(pq);
assert(!QEmpty(pq));
return pq->tail->data;
}Queue.h
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
typedef char QDatatype;
typedef struct Queuenode
{
struct Queuenode* next;
QDatatype data;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;
void QInit(Queue* pq);
void QDestory(Queue* pq);
void QueuePush(Queue* pq,QDatatype x);
void QueuePop(Queue* pq);
int Size(Queue* pq);
bool QEmpty(Queue* pq);
QDatatype QueueFront(Queue* pq);
QDatatype QueueBack(Queue* pq);test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
int main()
{
Queue st;
QInit(&st);
QueuePush(&st,1);
QueuePush(&st, 2);
QueuePush(&st, 3);
QueuePush(&st, 4);
QueuePush(&st, 5);
QueuePush(&st, 6);
while (!QEmpty(&st))
{
printf("%d ", QueueFront(&st));
QueuePop(&st);
}
QDestory(&st);
return 0;
}最后，到了本次鸡汤环节：
孤独让你强大，让你成为更好的人！
原文地址：https://blog.csdn.net/go_bai/article/details/145194006
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！