目录
前言
我们之前实现了栈这个数据结构,今天我们就对队列这个数据结构进行讲解和实现.如果对栈这个结构还不是很了解的话,大家可以先去看--数据结构之栈的超详细讲解-CSDN博客,后面我会发布栈和队列的经典面试题,如果感兴趣的宝子们赶紧点赞关注收藏起来吧!
1.队列的概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头
这里与栈的区分:
栈的入栈和出栈只能在栈顶
队列的入队在队尾,出队在队头
栈:后进先出
队列:先进先出
2.队列的结构
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数 组头上出数据，效率会比较低。
我们的头节点为队头,方便数据的删除
我们的尾节点位队尾,方便数据的插入
3.队列的实现
3.1队列结构的实现
这里我们使用链表的结构实现队列
typedef int QDateType;
//节点结构体
typedef struct QueueNode
{
struct QueueNode* next;
QDateType val;
}QNode;这样会有些麻烦,因为在对链表进行插入删除操作时需要使用二级指针,详细讲解可以看我之前的单链表专题--单链表专题-CSDN博客,所以这里我么在额外定义一个结构体
两者对比如下:
//队尾插入 //void QueuePush(QNode** phead, QNode** ptail, QDateType x); //void QueuePop(QNode** phead, QNode** ptail); //队尾插入 void QueuePush(QNode* pq, QDateType x); //队头删除 void QueuePop(QNode* pq);
//避免使用二级指针
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;这里直接将我们头尾指针和队中元素个数size存储在结构体queue中
3.2队列操作函数的声明
下面是队列操作函数的声明:
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//队尾插入
//void QueuePush(QNode** phead, QNode** ptail, QDateType x);
//void QueuePop(QNode** phead, QNode** ptail);
//队尾插入
void QueuePush(QNode* pq, QDateType x);
//队头删除
void QueuePop(QNode* pq);
//取队头队尾的数据
QDateType QueueFront(Queue* pq);
QDateType QueueBack(Queue* pq);
//队中的元素个数
int QueueSize(Queue* pq);
//队是否为空
bool QueueEmpty(Queue* pq);3.3队列中方法的实现
3.3.1队列的初始化
不要忘了断言
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
3.3.2队列的销毁
这里将链表的头节点一个一个删除,不要忘了最后将头尾指针指为NULL,还有size也要赋值为0
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}3.3.3队列的尾插
要想插入数据,就得动态开辟空间,这与单链表,栈是一样的,用malloc动态开辟空间
开辟完空间后,先判断链表是否为空,为空的话,将头节点和尾节点等于我们新建的节点
如果不是,直接尾插
//队尾插入
void QueuePush(Queue* pq, QDateType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail!");
return;
}
newnode->next = NULL;
newnode->val = x;
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = pq->ptail->next;
}
pq->size++;
}3.3.4队列的头删
删除时注意需要多加一句断言:pq->size != 0
然后就是熟悉的两种情况:
1.只有一个节点时:(没有节点的情况我们断言已经排除掉了)
直接free当前节点
2.有多个节点
一个一个free
//从队头删除
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->size != 0);
//一个节点
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
else
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
pq->size--;
}
}3.3.5取队头的数据
因为我们定义了头指针和尾指针,所以这两个操作十分简单
QDateType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->phead);
return pq->phead->val;
}3.3.6取队尾的数据
QDateType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->ptail);
return pq->ptail->val;
}3.3.7队列中的元素个数
队列中元素的个数即为我们size的值
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}3.3.8队列是否为空
因为返回类型为布尔类型,所以我们返回size与0比较的布尔值
如果为空返回true
反之返回 false
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
}4.测试
我们测试将一些数据插入队列,并循环打印出队列中的数,观察队列的先进先出的性质
测试代码如下:
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
int main()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
printf("%d \n", QueueFront(&q));
QueuePush(&q, 3);
QueuePush(&q, 4);
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
QueueDestroy(&q);
return 0;
}结果如下:
5.总结
队列数据结构的实现其实并不难,随着栈和队列数据结构实现的完结,后面经典OJ例题可少不了,我会及时更新,感兴趣的的宝子们赶紧点赞关注收藏起来吧!
6.完整代码
Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int QDateType;
//节点结构体
typedef struct QueueNode
{
struct QueueNode* next;
QDateType val;
}QNode;
//避免使用二级指针
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//队尾插入
//void QueuePush(QNode** phead, QNode** ptail, QDateType x);
//void QueuePop(QNode** phead, QNode** ptail);
//队尾插入
void QueuePush(QNode* pq, QDateType x);
//队头删除
void QueuePop(QNode* pq);
//取队头队尾的数据
QDateType QueueFront(Queue* pq);
QDateType QueueBack(Queue* pq);
//队中的元素个数
int QueueSize(Queue* pq);
//队是否为空
bool QueueEmpty(Queue* pq);Queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
assert(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, QDateType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail!");
return;
}
newnode->next = NULL;
newnode->val = x;
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = pq->ptail->next;
}
pq->size++;
}
//从队头删除
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->size != 0);
//一个节点
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
else
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
pq->size--;
}
}
QDateType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->ptail);
return pq->ptail->val;
}
QDateType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->phead);
return pq->phead->val;
}
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
}text.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
int main()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
printf("%d \n", QueueFront(&q));
QueuePush(&q, 3);
QueuePush(&q, 4);
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
QueueDestroy(&q);
return 0;
}