C语言实现队列

🕗 发布于 2024-07-09 23:51 c语言 开发语言 数据结构

1.队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out).

入队列：进行插入操作的一端称为队尾。

出队列：进行删除操作的一端称为队头。

2.队列的实现

队列也可以用数组和链表的结构实现，使用链表的结构更优一点，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

2.1队列的结构

// 链式结构：表示队列中每个节点的结构
typedef struct QListNode
{ 
    struct QListNode* _pNext; 
    QDataType _data; 
}QNode;

// 队列的结构，用两个指针来维护一个队列
typedef struct Queue
{ 
    QNode* _front; 
    QNode* _rear; 
}Queue;

2.2头文件Queue.h

//Queue.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int QDataType;

// 链式结构：表示队列中每个节点的结构
typedef struct QListNode
{
    struct QListNode* _pNext;
    QDataType _data;
}QNode;

// 队列的结构，用两个指针来维护一个队列
typedef struct Queue
{
    QNode* _front;
    QNode* _rear;
}Queue;

void QPrint(Queue* q);

// 初始化队列
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);
// 检测队列是否为空
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);

2.3函数实现文件Queue.c

2.3.1初始化和销毁

2.3.1.1初始化

函数实现：

// 初始化队列
void QueueInit(Queue* q)
{
assert(q);

q->_front = q->_rear = NULL;
}

2.3.1.2销毁

函数实现：

// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);

QNode* cur = q->_front;
while (cur)
{
QNode* next = cur->_pNext;
free(cur);
cur = next;
}

q->_front = q->_rear = NULL;
}

2.3.2入队列和出队列

2.3.2.1队尾入队列

函数实现：

// 队尾入队列
void QueuePush(Queue* q, QDataType x)
{
assert(q);

//创建一个节点
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail!\n");
exit(1);
}

newnode->_data = x;
newnode->_pNext = NULL;

if (q->_front == NULL)
{
q->_front = q->_rear = newnode;
}
else
{
q->_rear->_pNext = newnode;
q->_rear = newnode;
}
}

打印函数：

//打印
void QPrint(Queue* q)
{
QNode* cur = q->_front;
while (cur)
{
printf("%d ", cur->_data);
cur = cur->_pNext;
}
printf("\n");
}

测试代码：

#include "Queue.h"

void test()
{
Queue q;

QueueInit(&q);

QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);

QPrint(&q);

QueueDestroy(&q);
}

int main()
{

test();
return 0;
}

2.3.2.2队头出队列

函数实现：

// 队头出队列
void QueuePop(Queue* q)
{
assert(q && q->_front);


//只有一个节点,删除后尾节点需要修改为NULL
if (q->_front->_pNext == NULL)
{
free(q->_front);
q->_front = q->_rear = NULL;
}
else
{
QNode* newphead = q->_front->_pNext;
free(q->_front);
q->_front = newphead;
}
}

测试代码：

#include "Queue.h"

void test()
{
Queue q;

QueueInit(&q);

QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);


QueuePop(&q);
QueuePop(&q);

QPrint(&q);

QueueDestroy(&q);
}

int main()
{

test();
return 0;
}

2.3.3获取队列头部尾部元素

2.3.3.1获取队列头部元素

函数实现：

// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q && q->_front); //断言首元素不能为空

return q->_front->_data;
}

2.3.3.2获取队列尾部元素

函数实现：

// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q && q->_rear); //断言尾元素不能为空

return q->_rear->_data;
}

测试代码：

#include "Queue.h"

void test()
{
Queue q;

QueueInit(&q);

QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);

QPrint(&q);


printf("%d\n",QueueFront(&q));
printf("%d\n", QueueBack(&q));

QueueDestroy(&q);
}

int main()
{

test();
return 0;
}

2.3.4 获取队列中有效元素个数

函数实现：

// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
QNode* cur = q->_front;
int count = 0;
while (cur)
{
count++;
cur = cur->_pNext;
}

return count;
}

测试代码：

#include "Queue.h"

void test()
{
Queue q;

QueueInit(&q);

QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);

QPrint(&q);

printf("%d\n", QueueSize(&q));

QueueDestroy(&q);
}

int main()
{

test();
return 0;
}

2.3.5检测队列是否为空

函数实现：

// 检测队列是否为空
int QueueEmpty(Queue* q)
{
assert(q);

if (q->_front == NULL)
{
return 0;
}
else
{
return -1;
}

}

测试代码：

#include "Queue.h"

void test()
{
Queue q;

QueueInit(&q);

QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);


QPrint(&q);


int i = QueueEmpty(&q);
if (i == 0)
{
printf("队列为空!\n");
}
else
{
printf("队列不为空!\n");
}

QueueDestroy(&q);
}

int main()
{

test();
return 0;
}

2.4 参考代码

//Queue.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int QDataType;

// 链式结构：表示队列中每个节点的结构
typedef struct QListNode
{
    struct QListNode* _pNext;
    QDataType _data;
}QNode;

// 队列的结构，用两个指针来维护一个队列
typedef struct Queue
{
    QNode* _front;
    QNode* _rear;
}Queue;

void QPrint(Queue* q);

// 初始化队列
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);
// 检测队列是否为空
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);

//Queue.c

#include "Queue.h"

//打印
void QPrint(Queue* q)
{
QNode* cur = q->_front;
while (cur)
{
printf("%d ", cur->_data);
cur = cur->_pNext;
}
printf("\n");
}

// 初始化队列
void QueueInit(Queue* q)
{
assert(q);

q->_front = q->_rear = NULL;
}

// 队尾入队列
void QueuePush(Queue* q, QDataType x)
{
assert(q);

//创建一个节点
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail!\n");
exit(1);
}

newnode->_data = x;
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 && q->_front);


//只有一个节点,尾节点需要修改
if (q->_front->_pNext == NULL)
{
free(q->_front);
q->_front = q->_rear = NULL;
}
else
{
QNode* newphead = q->_front->_pNext;
free(q->_front);
q->_front = newphead;
}
}

// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q && q->_front);

return q->_front->_data;
}

// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q && q->_rear);

return q->_rear->_data;
}

// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
QNode* cur = q->_front;
int count = 0;
while (cur)
{
count++;
cur = cur->_pNext;
}

return count;
}

// 检测队列是否为空
int QueueEmpty(Queue* q)
{
assert(q);

if (q->_front == NULL)
{
return 0;
}
else
{
return -1;
}

}

// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);

QNode* cur = q->_front;
while (cur)
{
QNode* next = cur->_pNext;
free(cur);
cur = next;
}

q->_front = q->_rear = NULL;
}

//test.c

#include "Queue.h"

void test()
{
Queue q;

QueueInit(&q);

QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);


//QueuePop(&q);
//QueuePop(&q);

QPrint(&q);


//printf("%d\n",QueueFront(&q));
//printf("%d\n", QueueBack(&q));

//printf("%d\n", QueueSize(&q));

int i = QueueEmpty(&q);
if (i == 0)
{
printf("队列为空!\n");
}
else
{
printf("队列不为空!\n");
}

QueueDestroy(&q);
}

int main()
{

test();
return 0;
}

原文地址：https://blog.csdn.net/CSQCSQCC/article/details/140292445

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：C++基础
下一篇：Cesium自定义着色器构件三角面片【闪烁】问题，但是一移动视角就闪烁

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20

C语言实现队列

1.队列的概念及结构

2.队列的实现

2.1队列的结构

2.2头文件Queue.h

2.3函数实现文件Queue.c

2.3.1初始化和销毁

2.3.1.1初始化

2.3.1.2销毁

2.3.2入队列和出队列

2.3.2.1队尾入队列

2.3.2.2队头出队列

2.3.3获取队列头部尾部元素

2.3.3.1获取队列头部元素

2.3.3.2获取队列尾部元素

2.3.4 获取队列中有效元素个数

2.3.5检测队列是否为空

2.4 参考代码

相关文章