队列（Queue）是另一种基本的线性数据结构，它允许在一端进行插入操作，而在另一端进行删除操作。队列的特点是先进先出（First In First Out, FIFO），即最先进入队列的元素最先被取出。
队列可以用数组来实现，也可以用链表来实现。用数组实现的队列称为顺序队列，用链表实现的队列称为链式队列。
顺序队列的特点是：
- 存储空间连续。
- 提前分配固定大小的存储空间，可能会造成空间浪费，或者空间不足时需要动态扩容。
- 访问速度快，因为支持随机访问。
链式队列的特点是：
- 存储空间不连续。
- 动态分配空间，不会造成空间浪费，也不会出现空间不足的问题。
- 访问速度相对较慢，因为不支持随机访问。
队列的应用非常广泛，包括：
- 任务调度：在多任务操作系统中，队列用于管理等待执行的线程或进程。
- 缓冲处理：在网络通信中，队列用于临时存储数据包，以平滑网络拥塞。
- 异步数据传输：在消息队列中，生产者将消息放入队列，消费者从队列中取出消息，实现异步处理。
- 事件管理：在图形用户界面中，队列用于管理用户操作产生的事件。
队列是一种简单但重要的数据结构，它在管理需要按照特定顺序处理的元素集合时非常有用。
以下我讲以下顺序队列的基本使用方法。
1.循环队列结构体定义
#define N 10
typedef struct
{
int
data
[
N
];
int
front
;
//
队头，删除出队时用
front
当下标
int
rear
;
//
队尾，插入入队时用
rear
当下标
}
queue_t
;
循环队列操作
1. 创建一个空的队列 createEmptyQueue()
2.
判断队列是否为空，空返回值是
1
，未空是
0
isEmptyQueue
()
p
->
rear
==
p
->
front
3.
判断队列是否为满 满返回值是
1
，未满是
0
isFullQueue
()
4.
入队
inQueue
()
5.
出队
outQueue
()
6.
求队列的长度
getLengthQueue
()
2.创建一个空的队列
queue_t
*
createEmptyQueue
()
{
queue_t
*
p
=
malloc
(
sizeof
(
queue_t
));
if
(
p
==
NULL
)
{
printf
(
"createEmptyQueue malloc failed!!\n"
);
return
NULL
;
}
//只要
p->rear == p->front
就是空的队列
,
是几不重要
//但是
p->rear
和
p->front
的值
,
要在数组的下标范围内
0 ---- N-1
p
->
rear
=
p
->
front
=
3
;
//
将
3
赋值给
front,
在赋值给
rear,
让
rear
和
front
都得
3
return
p
;
}
3.判断队列是否为满 满返回1,未满返回0
int
isFullQueue
(
queue_t
*
p
)
{
//因为
p->rear == p->front
代表队列空
,
所以我们只能浪费一个存储位置来判断队列是否为满
,
//提前判断
p->reare+1
的位置是否
== p->front,
来判断是否是满队列
return
(
p
->
rear
+
1
)
%
N
==
p
->
front
?
1
:
0
;
}
4.入队,在队列尾巴进行插入操作
int
inQueue
(
queue_t
*
p
,
int
x
)
{
//0.容错判断
if
(
isFullQueue
(
p
))
{
printf
(
"isFullQueue!!\n"
);
return
-
1
;
}
//1.入队列
,
用
rear
当做下标
p
->
a
[
p
->
rear
]
=
x
;
//2.p->rear++,将入队的数据
x,
视为有效的元素
p
->
rear
=
(
p
->
rear
+
1
)
%
N
;
// %N
避免
p->rear+1
出现数组越界
//p->rear = (p->rear+1) % N;此行代码等价于
p->rear++; p->rear =p->rear % N;
return
0
;
}
5.判断队列是否为空,空返回1, 未空返回0
int
isEmptyQueue
(
queue_t
*
p
)
{
return
p
->
rear
==
p
->
front
?
1
:
0
;
}
6. 出队列,在队列的头进行删除操作
int
outQueue
(
queue_t
*
p
)
{
//0.容错判断
if
(
isEmptyQueue
(
p
))
{
printf
(
"isEmptyQueue!!\n"
);
return
-
1
;
}
//出队
,
用
front
当做数组的下标
//1.将即将出队的数据
,
临时存储到变量
x
中
//因为
front
永远指向队头的元素
int
x
=
p
->
a
[
p
->
front
];
//2.让出对的元素变为无效元素
p
->
front
=
(
p
->
front
+
1
)
%
N
;
//3.将出对元素的值返回
return
x
;
}
7.求队列的长度
int
getLengthQueue
(
queue_t
*
p
)
{
//按道理
,rear
值肯定大于
front
//方法一
if
(
p
->
rear
>=
p
->
front
)
return
p
->
rear
-
p
->
front
;
else
// rear < front
按道理
rear
肯定大于
front
为什么
rear < front,
因为
%N,
所以
+N,
还原
rear的值
return
(
p
->
rear
+
N
)
-
p
->
front
;
//方法二
//return (p->rear + N - p->front) % N;
}
结语
以上就是队列的基本使用，本次代码分享到此结束，后续还会分享数据结构知识。
最后的最后，还请大家点点赞，点点关注，谢谢大家！
