当前位置:网站首页>队列的实现
队列的实现
2022-07-06 10:04:00 【qzt__l0ve】
目录
1.队列的概念及结构
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出
FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾
出队列:进行删除操作的一端称为队头
2.队列的实现
队列也可以用数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。
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);
初始化队列
void QueueInit(Queue* q);//无论什么结构,我们都需要先进行初始化。
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
队尾入队列
void QueuePush(Queue* q, QDataType data);//由于队列是先进先出,所以只能从尾部进行插入
void QueuePush(Queue* pq, QDataType x)//插入,在队尾插入;先进先出
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));//每插入一个数据就开辟一个空间
if (newnode == NULL)//判断是否开辟失败
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->tail == NULL)//第一次插入没数据时
{
pq->head = pq->tail = newnode;
}
else//有数据后
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
// 队头出队列
void QueuePop(Queue* q);//出队列,最先出的是队头那个数据,要保证是先进先出。
void QueuePop(Queue* pq)//等于是删队头数据
{
assert(pq);
assert(!QueueEmpty(pq));//判断队列是否为空
//一个节点
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
//多个节点
else
{
Queue* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
// 获取队列头部元素
QDataType QueueFront(Queue* q);//先判断队列的容量,再返回队头元素
QDataType QueueFront(Queue* pq)//取对头数据
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q);//先判断队列容量,再返回队尾数据
QDataType QueueBack(Queue* pq)//取队尾数据
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q);//创建一个当前指针,挨个往后遍历,size为大小统计数量。
int QueueSize(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;//创建一个当前元素指针
int size = 0;//用于统计元素数量
while (cur)
{
++size;
cur = cur->next;
}
return size;
}
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0
int QueueEmpty(Queue* q);//这里return是先判断pq->head是否等于空,等就返回真,不等就返回假。
bool QueueEmpty(Queue* pq)//判断容量;
{
assert(pq);
return pq->head == NULL;
}
// 销毁队列
void QueueDestroy(Queue* q);由于我们开辟了空间,所以我们在最后也要挨个释放。
void Queuestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)//挨个释放空间
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}
扩展:
实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现,也可以使用循环链表实现。
边栏推荐
- Nodejs developer roadmap 2022 zero foundation Learning Guide
- 1700C - Helping the Nature
- EasyCVR授权到期页面无法登录,该如何解决?
- 一体化实时 HTAP 数据库 StoneDB,如何替换 MySQL 并实现近百倍性能提升
- node の SQLite
- 《ASP.NET Core 6框架揭秘》样章发布[200页/5章]
- 78 岁华科教授逐梦 40 载,国产数据库达梦冲刺 IPO
- Codeforces Round #803 (Div. 2)
- 8位MCU跑RTOS有没有意义?
- Today in history: the mother of Google was born; Two Turing Award pioneers born on the same day
猜你喜欢
传统家装有落差,VR全景家装让你体验新房落成效果
SQL statement optimization, order by desc speed optimization
[ASM] introduction and use of bytecode operation classwriter class
RB157-ASEMI整流桥RB157
Is it meaningful for 8-bit MCU to run RTOS?
[getting started with MySQL] fourth, explore operators in MySQL with Kiko
Stealing others' vulnerability reports and selling them into sidelines, and the vulnerability reward platform gives rise to "insiders"
There is a gap in traditional home decoration. VR panoramic home decoration allows you to experience the completion effect of your new house
The solution that flutterweb browser cannot be rolled back after refreshing
OliveTin能在网页上安全运行shell命令(上)
随机推荐
VR全景婚礼,帮助新人记录浪漫且美好的场景
Heavy! Ant open source trusted privacy computing framework "argot", flexible assembly of mainstream technologies, developer friendly layered design
In terms of byte measurement with an annual salary of 30W, automated testing can be learned in this way
[elastic] elastic lacks xpack and cannot create template unknown setting index lifecycle. name index. lifecycle. rollover_ alias
Distributed (consistency protocol) leader election (dotnext.net.cluster implements raft election)
The easycvr platform reports an error "ID cannot be empty" through the interface editing channel. What is the reason?
How to output special symbols in shell
Today in history: the mother of Google was born; Two Turing Award pioneers born on the same day
The art of Engineering (2): the transformation from general type to specific type needs to be tested for legitimacy
The art of Engineering (1): try to package things that do not need to be exposed
Jielizhi obtains the currently used dial information [chapter]
Awk command exercise
Hongmeng introduction and development environment construction
The easycvr authorization expiration page cannot be logged in. How to solve it?
带你穿越古罗马,元宇宙巴士来啦 #Invisible Cities
EasyCVR接入设备开启音频后,视频无法正常播放是什么原因?
Shell input a string of numbers to determine whether it is a mobile phone number
C # nanoframework lighting and key esp32
IP, subnet mask, gateway, default gateway
微信小程序获取手机号