新手数据结构精通——队列
1队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。
理解：可以想象成一根吸管
2队列的设计
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
最初设置一个链表节点当然都是NULL，再把节点作为一个元素放到另一个结构体内，设置front和rear都指向这个节点。
插入一个节点，front指向这个节点的地址，rear指向这个节点的NEXT。
再插入一个元素，front就不用改动，改动的都是rear，每增加一个数据节点，rear就会往后移动并指向新节点。
增加多个节点之后的样子
重点注释
这里的增删需要解释一下，因为队列是先入先出的结构，那么我们要增加一个数字应用在链表上就是：头插尾删。明白这一点十分重要。
代码实现
先设计一个单链表的结构体（忘记了请翻看之前讲解的内容单链表精讲），然后再用链表节点构造出队列。
// 链式结构：表示队列
typedef int QDataType;
typedef struct QListNode
{
struct QListNode* _pNext;
QDataType _data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* _front;
QNode* _rear;
}Queue;
初始化
其实就是和图像一致。第一步先将front和rear都置为NULL。
先做出一个队列 q。
// 初始化队列
void QueueInit(Queue* q)
{
q->_front = q->_rear = NULL;
}
插入
这里的插入和我之前说过的一样，就是链表尾插。但是要做好对队列的判断。比如：空指针，没定义，空队列。
//头出尾入，front出 rear 入
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* Newnode = (QNode*)malloc(sizeof(QNode));
Newnode->_data = data;
Newnode->_pNext = NULL;
if (q->_front == NULL)
{
q->_front = q->_rear = Newnode;
}
else
{
q->_rear->_pNext = Newnode;
q->_rear = Newnode;
}
}
重点：头出尾入，front出 rear 入
出队
// 队头出队列
void QueuePop(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));//检验是否为空
Queue* gone = q->_front;
q->_front = q->_front->_pNext;
free(gone);
gone = NULL;
if (q->_front == NULL)
{
q->_rear = NULL;
}
}
一定要记得检验是否为空，所以我们还要设计一个检验空的函数。
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q)
{
assert(q);
return q->_front == NULL;
}
这里返回值用bool也可以的，但是因为效果一样我就不改了。如果用bool记得增加bool头函数。
查
查找有很多种方式。比如：头部数据、尾部数据、有多少元素。我们都实现以下。
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->_front->_data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->_rear->_data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
int count = 0;
QNode* cur = q->_front;
while (cur)
{
cur = cur->_pNext;
++count;
}
}
每个函数都要检验一下是否为空，因为有时候我们会写出野指针的。
销毁
学了数据结构一定要记得最后要销毁，否则一直占用堆，会影响性能，也不严谨。
// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
QNode* cur = q->_front;
while (cur != NULL)
{
QNode* next = cur->_pNext;
free(cur);
cur = next;
}
q->_front=q->_rear = NULL;
}
代码汇总
头文件
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
// 链式结构：表示队列
typedef int QDataType;
typedef struct QListNode
{
struct QListNode* _pNext;
QDataType _data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* _front;
QNode* _rear;
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
程序函数.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
// 初始化队列
void QueueInit(Queue* q)
{
q->_front = q->_rear = NULL;
}
//头出尾入，front出 rear 入
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* Newnode = (QNode*)malloc(sizeof(QNode));
Newnode->_data = data;
Newnode->_pNext = NULL;
if (q->_front == NULL)
{
q->_front = q->_rear = Newnode;
}
else
{
q->_rear->_pNext = Newnode;
q->_rear = Newnode;
}
}
// 队头出队列
void QueuePop(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));//检验是否为空
Queue* gone = q->_front;
q->_front = q->_front->_pNext;
free(gone);
gone = NULL;
if (q->_front == NULL)
{
q->_rear = NULL;
}
}
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->_front->_data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->_rear->_data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
int count = 0;
QNode* cur = q->_front;
while (cur)
{
cur = cur->_pNext;
++count;
}
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q)
{
assert(q);
return q->_front == NULL;
}
// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
QNode* cur = q->_front;
while (cur != NULL)
{
QNode* next = cur->_pNext;
free(cur);
cur = next;
}
q->_front=q->_rear = NULL;
}
主函数和测试函数
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void TestFunc()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
//QueuePop(&q);
/*QueuePop(&q);
QueuePop(&q);
QueuePop(&q);*/
//QueuePop(&q);
/*printf("%d ", QueueSize(&q));
printf("%d ", QueueFront(&q));
printf("%d ", QueueBack(&q));*/
while (!QueueEmpty(&q))
{
QDataType front = QueueFront(&q);
printf("%d ", front);
QueuePop(&q);
}
printf("\n");
}
int main()
{
TestFunc();
return 0;
}
测试结果
