您现在的位置是:首页 >技术交流 >C语言实现队列--数据结构网站首页技术交流
C语言实现队列--数据结构
??️Take your time ! ??️
?个人主页:???大魔王???
?代码仓库:??魔王修炼之路??
?所属专栏:?魔王的修炼之路–数据结构?
如果你觉得这篇文章对你有帮助,请在文章结尾处留下你的点赞?和关注?,支持一下博主。同时记得收藏✨这篇文章,方便以后重新阅读。
文章目录
前言
队列介绍:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进后出FIFQ(First In First Out)入队列:进行插入操作的一端称为队尾。出队列:进行删除操作的一端称为队头。
代码实现
1、创建结构体
对于队列,需要创建两个结构体,第一个为结点的结构体,第二个是记录队列头、尾及元素个数的结构体,因为队列在入队时相当于尾插,如果不记录尾结点,需要一直遍历,这样效率低,所以在操作后直接记录尾结点,记录个数是因为方便其他函数操作,比如需要个数时,直接访问这个成员就行了,不需要再遍历一遍看看有几个,对于队列是否为空,也不需要判断指针是否为空,直接判断个数就行了。
代码实现:
#pragma once
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;//目的:要个数时,不需要遍历一遍,直接就能知道有几个。
}Queue;
2、初始化结构体
刚开始时怎样创建?是创建一个结构体指针然后接收在函数里开辟一块空间返回的结构体指针还是直接创建一个结构体,我们这里选择直接创建一个结构体,因为这个不像单链表一样,如果单链表没有元素,那么就是空,就没有结点一说,这个直接就一定不是空,因为我们操作的不是结点的结构体,而是记录队列的结构体,所以它永远不会是空,就不需要弄一个结构体指针再接收之类的操作了。
void QInit(Queue* q)
{
assert(q);
q->head = q->tail = NULL;
q->size = NULL;
}
3、销毁
用完就需要销毁,防止内存泄漏。
void QDestroy(Queue* q)
{
assert(q);
while (q->head)
{
Queue* next = q->head->next;
free(q->head);
q->head = next;
}
q->tail = NULL;//防止野指针
q->size = 0;
}
4、创建新结点
入队列时需要创建新结点。
QNode* BuyNewnode(QDataType x)
{
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)//检测是否开辟成功
{
perror("malloc error");
assert(newnode);
}
newnode->data = x;
newnode->next = NULL;
}
5、入队列
就像最开始的那个图一样,入队列相当于尾插。
//从后面进入,算是尾插。
void QPush(Queue* q, QDataType x)
{
assert(q);
QNode* newnode = BuyNewnode(x);
if (q->head == NULL)//如果本来没有元素,需要让首尾指针都赋上这个结点;如果有元素,就管尾指针就行。
{
assert(q->head == q->tail);
q->head = q->tail = newnode;
}
else
{
q->tail->next = newnode;
q->tail = newnode;
}
q->size++;
}
6、出队列
相当于头删。
//从前面出,算是头删。
void QPop(Queue* q)
{
assert(q);
assert(q->head && q->tail);//出队列时队列不能为空,如果不为空,那么首尾指针肯定都不为空。
if (q->head->next == NULL)判断是否只有一个结点,如果只有一个,尾指针也要指向空,不然就会变成野指针。
{
assert()q->head==q->tail);//如果只有一个结点,那么首尾结点肯定相等。
free(q->head);
q->head = q->tail = NULL;
}
else
{
QNode* newhead = q->head->next;
free(q->head);
q->head = newhead;
}
q->size--;
}
7、队列成员个数
直接返回结构体里的size就行。
int QSize(Queue* q)
{
assert(q);
//int size = 0;
//QNode* cur = q->head;
//while (cur)
//{
// cur = cur->next;
// size++;
//}
//return size;
return q->size;
}
8、队列是否为空
直接判断size就行。
bool QEmpty(Queue* q)
{
assert(q);
return q->size == 0;
}
9、队列最前面的元素数据
需要判断是否为空。如果为空就不能访问,不然越界。
QDataType QFront(Queue* q)
{
assert(q);
assert(q->head);
return q->head->data;
}
10、队列最后面的元素数据
需要判断队列是否为空,如果为空就不能访问,不然越界。
QDataType QBack(Queue* q)
{
assert(q);
assert(q->tail);
return q->tail->data;
}
总代码
Queue.h
Queue.h
#pragma once
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;//目的:要个数时,不需要遍历一遍,直接就能知道有几个。
}Queue;
void QInit(Queue* q);
void QDestroy(Queue* q);
void QPush(Queue* q,QDataType x);
void QPop(Queue* q);
int QSize(Queue* q);
bool QEmpty(Queue* q);
QDataType QFront(Queue* q);
QDataType QBack(Queue* q);
Queue.c
Queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
void QInit(Queue* q)
{
assert(q);
q->head = q->tail = NULL;
q->size = NULL;
}
void QDestroy(Queue* q)
{
assert(q);
while (q->head)
{
Queue* next = q->head->next;
free(q->head);
q->head = next;
}
q->tail = NULL;//防止野指针
q->size = 0;
}
QNode* BuyNewnode(QDataType x)
{
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)//检测是否开辟成功
{
perror("malloc error");
assert(newnode);
}
newnode->data = x;
newnode->next = NULL;
}
//从后面进入,算是尾插。
void QPush(Queue* q, QDataType x)
{
assert(q);
QNode* newnode = BuyNewnode(x);
if (q->head == NULL)//如果本来没有元素,需要让首尾指针都赋上这个结点;如果有元素,就管尾指针就行。
{
assert(q->head == q->tail);
q->head = q->tail = newnode;
}
else
{
q->tail->next = newnode;
q->tail = newnode;
}
q->size++;
}
//从前面出,算是头删。
void QPop(Queue* q)
{
assert(q);
assert(q->head && q->tail);//出队列时队列不能为空,如果不为空,那么首尾指针肯定都不为空。
if (q->head->next == NULL)//判断是否只有一个结点,如果只有一个,尾指针也要指向空,不然就会变成野指针。
{
assert(q->head == q->tail);//如果只有一个结点,那么首尾结点肯定相等。
free(q->head);
q->head = q->tail = NULL;
}
else
{
QNode* newhead = q->head->next;
free(q->head);
q->head = newhead;
}
q->size--;
}
int QSize(Queue* q)
{
assert(q);
//int size = 0;
//QNode* cur = q->head;
//while (cur)
//{
// cur = cur->next;
// size++;
//}
//return size;
return q->size;
}
bool QEmpty(Queue* q)
{
assert(q);
return q->size == 0;
}
QDataType QFront(Queue* q)
{
assert(q);
assert(q->head);
return q->head->data;
}
QDataType QBack(Queue* q)
{
assert(q);
assert(q->tail);
return q->tail->data;
}
Test.c
//测试队列
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
void print(Queue* q)
{
while (!QEmpty(q))
{
printf("%d ", QFront(q));
QPop(q);
}
}
int main()
{
Queue q;
QInit(&q);
QPush(&q, 0);
QPush(&q, 1);
QPush(&q, 2);
QPush(&q, 3);
QPush(&q, 4);
QPush(&q, 5);
QPop(&q);
QPop(&q);
print(&q);
QDestroy(&q);
return 0;
}
总结
结尾
- 博主长期更新,博主的目标是不断提升阅读体验和内容质量,如果你喜欢博主的文章,请点个赞或者关注博主支持一波,我会更加努力的为你呈现精彩的内容。
?专栏推荐
?魔王的修炼之路–C语言
?魔王的修炼之路–数据结构初阶
?魔王的修炼之路–C++
?魔王的修炼之路–Linux
更新不易,希望得到友友的三连支持一波。收藏这篇文章,意味着你将永久拥有它,无论何时何地,都可以立即找到重新阅读;关注博主,意味着无论何时何地,博主将永久和你一起学习进步,为你带来有价值的内容。