欢迎光临
我们一直在努力
        找回密码
当前位置：171主机测评 > 服务器技术 > 正文

C语言实现队列

2026-10-01 分类：服务器技术 阅读(7) 评论(0)

文章目录

        • 队列
        • 介绍队列
        • 队列的操作
        • 队列工作的逻辑视图
        • 数组实现队列
          • 循环数组
        • 单链表实现
          • test.c
          • queue.c
          • queue.h
队列

接下来将讨论队列这种数据结构，还是把它作为一种抽象数据类型讨论，现讨论它的特性和操作，后面再来讨论它的实现。

介绍队列

队列这样的数据结构就像生活中排队一样，比如班级的同学在走廊排好队走出教学楼，那么排在第一位的同学肯定是先走出来的，这样家长就可以一眼就可以看到你啦~☺️

之前学习过了栈这种数据结构，它的特性或者说它的规则是：*后进先出，栈这种数据结构的插入和操作都是从一端（栈顶）进行的。*那么队列的特性或者说规则又是什么呢？

在队列里，插入必须从队尾进行，删除必须从另外一端进行。（另外一端称为：头部或队首）。

队列抽象数据类型的定义：队列是一个列表或集合。它的限制：插入必须从队尾进行，删除必须从队首进行

队列的操作

队列和栈一样，有两个基本的操作：插入和删除。插入被称为入队操作（Enqueue）删除则被称为出队操作（Dequeue）。当然还有其它操作

一般情况下，会保留第三个操作front用来查看队首的元素，和栈中的top操作一样只是返回队列头部的元素。

第四个操作和栈的IsEmpty用来检查队列是否为空，如果队列有一定的大小第五个操作IsFull检查队列是否已满

因此队列除了两个基本的插入和删除操作还有刚才说的那几个，来整理一下：

  • Enqueue插入操作
  • Dequeue删除操作
  • Front返回队首元素
  • IsEmpty检查队列是否为空
  • IsFull检查队列是否已满

这些操作的时间复杂度都是O(1)

在一些语言提供的库函数，函数的接口名字可能不一样。比如在C++中入队操作可能叫Push

队列工作的逻辑视图

我们把队列想象成是一两段都剪开的瓶子，现在要往队列中插入一个元素3，前面说过队列只能从队尾插入，我这里就假设左边是队尾，右边是队首。如图所示，此时队列中只有一个元素3，队尾和队首的元素是一样的。

image-20260929170428930

再来插入两个元素，如图所示，此时队列中有3个元素。队尾是7，队首是3。

image-20260929170849458

来执行一下删除操作，当我们执行删除操作后，此时队列中就剩下两个元素，元素5成为新的队首。如图所示

image-20260929171140314

来执行front操作，也就是返回队首元素。如下图所示，front仅仅是返回队首的元素不会做任何的修改。

image-20260929181908637

再来执行IsEmpty操作，查看队列是否为空。如果为空返回true，否则返回false

image-20260929181925080

看到这里的小伙伴应该清楚了队列是怎么工作的。但是队列是在什么场景下用呢？什么时候该使用它？

比如，有一台网络共享打印机。网络中的任何一台机器都可以向这个台打印机发出打印请求。但是，打印每次都只能服务一个请求，一次只能打印一个文件。比方说现在这个打印机正在打印文件，然后我向它发出打印请求的时候它告诉我，“我很忙，你一会再来”（像极了男朋友或女朋友，调皮一下😛）但是实际上打印机不能这样，因为这样太冷暴力了。那么该怎么做呢？

实际上控制打印机的程序会把请求加入到一个队列中，只要队列中有内容，打印机每次都会从队首拿出任务来打印。

总的来说，队列可以用来模拟需要等待的场景。

数组实现队列

比如我先需要一个整形元素的队列，首先要先来创建一个数组，这个数组大小我就给10好了。用这个数组来存储队列，数组的一部分从front标记的下标开始一直到rear标记的下标位置，如下图所示image-20260929190548529

说一下，这个数组front和rear标记的下标位置和前面那个瓶子的例子是反着的，这不重要。任意一边都可以是front或rear。但是，要插入元素必须从rear这一端插入，删除从front这端删除。从front到rear所标记的下标就是我们的队列啦。数组中剩下的位置是空闲的空间。现在来给队列填入一些值看看，如图所示现在这个队列就满了。

image-20260929203147564

如果我还想要插入数字8，那么就需要递增rear也就是rear要向前一个位置。当然，这必须是数组还有剩余的空间，如图所示：

image-20260929203443553

现在入队清楚了，来看看出队该怎么做。前面有说过，入队从队列的尾部进入，出队从队列的队首出来。现在要出队的话，2先从队列中出来，如图所示： image-20260929203754476

这里只需要把front往前一个位置，不需要对原来下标2的元素做任何处理。因为，任何时候队列都是从front到rear所标记的下标位置才是队列。

刚才我们讨论的是有队列中有元素的情况，那么如果这个队列为空我们该怎么表示呢？我们知道front标记的下标位置到rear标记的下标位置才是我们的队列。而数组的下标是从0开始的增长的，那么空队列的话就可以把front和rear都标记为-1，因为-1不属于数组的下标。 image-20260929204655380

来写点伪代码看看：

// 创建数组
int arr[10] = {0};
int front = –1;
int rear = –1;

// 检查队列是否为空
int IsEmpty()
{
if(–1 == front && –1 == rear)
return 1;
else
return 0;
}

// 检查队列是否已满
int IsFull()
{
if(rear == 10–1)
return 1;
else
return 0;
}

Enqueue(int val)
{

if(IsFull())
return;
else if(IsEmpty())
{
front = 0;
rear = 0;
arr[rear] = val;
}
else
{
rear += 1;
arr[rear] = val;
}

}

来试试插入一个值看看伪代码能不能工作吧。入队Enqueue(2)但是现在front=-1 rear=-1表示该队列为空。执行else if(IsEmpty())这条语句，此时队列就有数组0下标位置的就是我的队列。最后arr[rear] = val;这样就可以插入2啦😚 注：这里的入队arr[rear]arr的下标必须是rear不能是front因为前面讨论过，队列是从尾部插入。

如图所示，现在队列中就有一个元素了。

image-20260929212403544

再来插入一个元素看看会发生什么😝。入队Enqueue(5)此时的front=0 rear=0表示该队列不为空，执行else语句，rear就变成了1，也就是数组下标0到1是我的队列。如下图：

image-20260929212747872

到这里插入就没什么大问题了。再来写一个Dequeue还知道是什么操作吧，从队首移除元素。来看看伪代码：

Dequeue()
{
if(IsEmpty())
return;
else if(front == rear)
{
front = –1;
rear = –1;
}
else
{
front += 1;
}
}

来解释一下Dequeue的几种情况：

  • 要从队列移出元素，那么这个队列就不能是空的，所以一开始就判断IsEmpty的返回是否为真
  • 队列只有一个元素的情况下，front和rear是相等的情况。为了让队列为空，还需要把它们重置为-1
    • 这里是可以直接判断if(front == rear)的，因为前面-1已经的判断过来才会回来到这里
  • 最后一种情况就是前面讨论的那样子啦

现在来执行一下这个Dequeue操作，当前队列只有两个元素队吧，再来入队一个元素Enqueue(7)。来执行一次Dequeue()看看，此时会执行else语句，front就变成了1。那么原来的下标0的元素需不需要做什么呢？其实不用的，因为此时下标0已经不属于队列了。如图所示：

image-20260929223336449

再来入队几个元素Enqueue(1),Enqueue(4),Enqueue(9),Enqueue(6),Enqueue(8),Enqueue(3)。此时队列的元素如下图所示：

image-20260929223651463

来执行一下Dequeue()此时front就变成了2，也就是下标为1的元素不属于队列了。如下图所示： image-20260929224126234

然后再入队一个元素的话就队列就满了，因为rear已经来到了数组的最大下标位置。Enqueue(2)： image-20260929224324961

此时就不能再往队列执行插入操作了。因为已经满了。但是，现在左边空出来了两个没有使用的单元，按照刚才的逻辑这两个单元就会被浪费掉，因为永远都不会再用上了。该怎么办呢？我们可以使用循环数组。

循环数组

可以把数组想象成没有结尾，从0到1、1到2最后到达数组最大下标。其实也就是和生活中星期一样啦，星期一到星期二，星期日到星期一。

我们访问第i个元素的时候，就不单单是i+1了，而是(i+1)%n。来套一下，i+1=10 10%10=0。对于星期也是一样的，当day=7 (7+1)%7=1。

也就是说我们对rear的下一个位置对n取模。于是有下面的场景：当rear=1 front=2的时候，此时rear后面的位置是front，整个数组已经被用完了，这种情况下队列也就满了

image-20260930145016339

来修改一下伪代码：

Enqueue(int val)
{

if((rear+1)%n == front) // 修改
return;
else if(IsEmpty())
{
front = 0;
rear = 0;
arr[rear] = val;
}
else
{
// rear += 1;
rear = (rear + 1 )%n; // 修改
arr[rear] = val;
}

}

假设现在的队列没有满rear=9 front=2，现在来入队一个元素看看，Enqueue(1)如下图所示。调用Enqueue(1)进入该函数后，if条件10%10=0条件不成立，else if语句也不成立。执行else语句，rear=(rear+1)%10执行这个条语句后rear=0。这样前面讨论的front左边的空间就不会被浪费了。

image-20260930150141329

现在Dequeue也要修改一下，以循环数组的方式来做。

Dequeue()
{
if(IsEmpty())
return;
else if(front == rear)
{
front = –1;
rear = –1;
}
else
{
front = (front+1)%n; // 修改
}
}

来执行一下Dequeue()看看。进入Dequeue()函数if和else if语句都不成立，执行else语句，(2+1)%10=3那么front来到下标3位置，之前下标2不再属于队列。如果以后插入的时候rear来到2下标会把之前的值给覆盖掉。

最后来看看代码：

queue.h

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

#define SIZE 10

typedef int QueueType;

// 封装成结构体，可以简洁点
typedef struct
{
QueueType arr[SIZE];
int front;
int rear;
}Queue;

// 入队
void Enqueue(Queue* queue, QueueType val);

// 出队
void Dequeue(Queue* queue);

// 返回队首元素
QueueType* Front(Queue* queue);

// 检查队列是否为空
int IsEmpty(Queue* queue);

// 检查队列是否已满
int IsFull(Queue* queue);

queue.c

#include "queue.h"

// 检查队列是否为空
// 如果为空返回真，否则返回假
int IsEmpty(Queue* queue)
{
if(–1 == queue->front && –1 == queue->rear)
return 1;
else
return 0;
}

// 检查队列是否已满
// 如果满了返回真，否则返回假
int IsFull(Queue* queue)
{
if((queue->rear+1) % SIZE == queue->front)
return 1;
else
return 0;
}

// 入队
void Enqueue(Queue* queue, QueueType val)
{
assert(queue);
// 检查队列是否为空
if(IsEmpty(queue))
{
queue->front = 0;
queue->rear = 0;

}
// 如果rear下个位置是front 说明队列已满
else if(IsFull(queue)) // 检查队列是否已满
{
printf("队列已满%d无加入队列\\n", val);
return;
}
else // 队列中有元素
{
queue->rear = ((queue->rear) + 1) % SIZE;
}
queue->arr[queue->rear] = val;

}

// 出队
void Dequeue(Queue* queue)
{
assert(queue);

// 检查队列是否为空
if(IsEmpty(queue))
{
printf("队列中没有任何元素!\\n");
return;
}
else if(queue->front == queue->rear) // 特殊情况：只有一个元素的时候front和rear相等
{
queue->front = –1;
queue->rear = –1;
}
else
{
queue->front = (queue->front+1) % SIZE;
}
}

// 返回队首元素
QueueType* Front(Queue* queue)
{
assert(queue);
// 检查队列是否为空
if(IsEmpty(queue))
{
printf("队列为空!\\n");
return NULL;
}

return (queue->arr) + (queue->front);
}

test.c

#include "queue.h"

void Print(Queue* queue)
{

if(–1 == queue->front && –1 == queue->rear)
{
printf("队列为空!\\n");
return;
}

printf("当前队列: ");
for(int i = queue->front; ; i = (i+1) % SIZE)
{
printf("%d ", queue->arr[i]); // 打印到队尾
if(i == queue->rear)
break;
}
printf("\\n");
}

static void test02()
{
Queue q = { 0 }; // 创建结构体变量
q.front = –1;
q.rear = –1;

Enqueue(&q, 2);
Print(&q);

Dequeue(&q);
Print(&q);

Enqueue(&q, 2);
Enqueue(&q, 5);
Enqueue(&q, 3);
Enqueue(&q, 9);
Print(&q);

Dequeue(&q);
Dequeue(&q);

Print(&q); // 3 9

QueueType* ret = Front(&q);
if(ret)
printf("当前队列中队首的值为: %d\\n", *ret); // 3

// printf("front%d, rear=%d\\n", q.front, q.rear); // 测试当前front和rear在哪个位置
// 入队
Enqueue(&q, 2);
Enqueue(&q, 5);
Enqueue(&q, 6);
Enqueue(&q, 8);
Enqueue(&q, 1);
Enqueue(&q, 4);
Print(&q);

ret = Front(&q);
if(ret)
printf("当前队列中队首的值为: %d\\n", *ret); // 3

// 当前队列已经满了来看看rear的位置是不是SIZE-1的位置
printf("front=%d, rear=%d\\n", q.front, q.rear); // 2, 9

// 再次入队会发生什么？
Enqueue(&q, 7); // 队列已满7无加入队列

// 但是front=2 也就是说arr[0],arr[1]这两个位置浪费掉了，该怎么办？
// 于是就有了循环数组或说叫循环队列

// 循环数组就是到达了数组最大下标的位置，然后又回到下标0 就像星期日到星期一
}

static void test03()
{
Queue q = { 0 };

// 空队列
q.front = –1;
q.rear = –1;

// 入队
Enqueue(&q, 2);
Enqueue(&q, 4);
Enqueue(&q, 6);
Enqueue(&q, 8);
Enqueue(&q, 10);
Enqueue(&q, 3);
Enqueue(&q, 5);
Enqueue(&q, 7);
Enqueue(&q, 9);
Enqueue(&q, 0);
Print(&q);

// 出队
Dequeue(&q);
Dequeue(&q);
// printf("front=%d, rear=%d\\n", q.front, q.rear);
Print(&q);
QueueType* ret = Front(&q);
if(ret)
printf("当前队列中队首的值为: %d\\n", *ret); // 6

// printf("front=%d, rear=%d\\n", q.front, q.rear);

// // 再来插入
Enqueue(&q, 1);
Enqueue(&q, 2);

Print(&q);
printf("front=%d, rear=%d\\n", q.front, q.rear);

Enqueue(&q, 20); // 队列已经满

// Dequeue(NULL); // 测试为空
}

int main()
{
// test01();

// test02(); // 测试封装成结构体

test03(); // 循环数组

return 0;
}

// 用结构体封装后，每个函数的参数都变得简洁了
// 注：Print函数不属于队列的操作，这里是为了方便我查看队列的每个操作是否正确

// 这里使用的是循环数组，解决了front左边的空间浪费问题

当然也可以不用这个结构体，我这里用结构体是为了简化函数的参数，不然每个函数都需要传递front&rear

单链表实现

其实用数组来实现队列这个数据结构并不是很好，原因很简单。虽然可以把前面说的数组改成动态数组的方式来实现，当这个队列满了扩大2倍，就像之前顺序表那样。但是还要把原来数组的内容拷贝到这个2倍大的数组里，那么时间复杂是O(n)而队列的所有操作都是O(1)。还有另一个原因，当数组已经足够大了但是队列里面就只有一个数据那么剩下的空间也会浪费掉。

结合以上的两个原因，我们可以用单链表来实现。单链表就可以解决这个两个问题。我们知道单链表的头插操作是O(1)，而尾插是O(n)呀。如果用单链表来做的话是不是也好？因为队列的操作都是O(1)而且队列的特性是：先进先出。如图所示我画了一个单链表还记得吧。

image-20261001004636903

head指向链表的头节点，每个节点由两部分组成：数据域、指针域。这个链表有3个节点。链表可以从头部插入也可以从尾部插入，这刚好符合队列的特性，我只需要规定链表的哪边执行或者说是管理入队操作Enqueue哪一边执行出队操作Dequeue就好了。但是，无论是哪边都需要考虑所有的操作都是O(1)。前面说过，链表的头插是O(1)而尾插是O(n) 也就是说无论我们选择哪边作为Enqueue或Dequeue其中有个操作都是O(n)，那么该怎么来解决这个问题？

image-20261001010020138

如图所示，如果要插入只能从头节点开始遍历一直到最后一个节点；然后修改该节点的next字段让它指向待插入节点。每次插入节点都必须要到达最后一个节点然后建立链接。那么该怎么来避免这个遍历呢？可以像第一个节点那样，用一个指针变量来存储尾节点的地址。如下图所示：

image-20261001010614867

如果现在再来插入一个节点，只需要修改rear指针指向的节点的next字段。然后更新rear指针指向插入进来的节点。 我这里就不画图了。

来看看代码：

test.c

#include "queue.h"

static void Print(Queue* front)
{
if(NULL == front)
{
printf("队列为空!\\n");
return;
}

printf("队列中元素: ");
for(; front != NULL; front = front->next)
printf("%d ", front->data);
printf("\\n");
}

static void test01()
{
Queue* front = NULL;
Queue* rear = NULL;

// 入队
// Enqueue(&front, &rear, 2);
// Enqueue(&front, &rear, 4);
// Enqueue(&front, &rear, 7);

// printf("front=%u, rear=%u\\n", (unsigned int)front, (unsigned int)rear); // rear = 0

// 出队
// Dequeue(&front, &rear);

// Print(front);

// 入队
Enqueue(&front, &rear, 2);
Enqueue(&front, &rear, 4);
Enqueue(&front, &rear, 5);
Enqueue(&front, &rear, 8);

Enqueue(&front, &rear, 6);
Enqueue(&front, &rear, 1);
Enqueue(&front, &rear, 3);
Enqueue(&front, &rear, 7);
Enqueue(&front, &rear, 9);
Print(front);

// 出队
Dequeue(&front, &rear);
Print(front);
// 返回队首元素
Queue* ret = Front(front);
if(ret)
{
printf("队首是: %d", ret->data);
}

}

int main()
{
test01();
return 0;
}

queue.c

#include "queue.h"

// 入队
void Enqueue(Queue** front, Queue** rear, QueueType val)
{
Queue* newNode = (Queue*)malloc(sizeof(Queue));
if(NULL == newNode)
{
perror("malloc");
return;
}
newNode->data = val;
newNode->next = NULL;

// 队列为空
if(NULL == *front && NULL == *rear)
{
*front = *rear = newNode;
return;
}
(*rear)->next = newNode;
(*rear) = newNode;
}

// 出队
void Dequeue(Queue** front, Queue** rear)
{
Queue* temp = *front;
if(NULL == *front)
{
printf("队列中没有值可删!\\n");
return;
}
else if(*front == *rear) // 队列只有一个值
{
*front = *rear = NULL;
}
else
{
*front = (*front)->next;
}
free(temp);
}

// 返回队首元素
Queue* Front(Queue* front)
{
if(NULL == front)
{
printf("没有队首\\n");
}
return front;
}

queue.h

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

typedef int QueueType;

// 声明节点
typedef struct Node
{
QueueType data;
struct Node* next;
}Queue;

// 入队
void Enqueue(Queue** front, Queue** rear, QueueType val);

// 出队
void Dequeue(Queue** front, Queue** rear);

// 返回队首元素
Queue* Front(Queue* front);

可能会有小伙伴问有以下的问题：

  • 为什么Enqueue&Dequeue不用返回值？

    • 答：front是头节点对吧。要想访问所有节点那么需要从头节点开始，当返回front这没问题。但是，我们需要rear指针指向链表的尾节点（最后一个节点）。所以，是需要改变front和rear的指向，而不单单是修改front的指向

  • 为什么Front的返回值要设置成Queue*？不能设置为QueueType（int）吗？

    • 可以的，因为是在vscode上写的C代码，编译器是gcc。如果我设置为int那么front == NULL的时候，不知道返回啥。返回负数也不合理，因为队列中可能也有负数呀。如果单单写return;编译不通过。所以这里就设为了Queue*。
    • 在IDE VS上是允许这么书写的，当然这会有一些警告。

祝大家国庆快乐🫡🫡🫡🫡

赞(0)
未经允许不得转载：171主机测评 » C语言实现队列
分享到： 更多 (0)
标签：

相关推荐

评论 抢沙发

取消

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

热门标签

#人工智能(64260)#python(21424)#开发语言(17825)#java(16402)#运维(16171)#linux(15651)#大数据(15319)#服务器(13663)#算法(12291)#前端(11646)#ai(10255)#网络(9906)#数据库(9506)#c++(8642)#学习(7166)#课程设计(7031)#机器学习(7006)#区块链(6059)#后端(5533)#OpenClaw(5414)#spring boot(5295)#深度学习(5271)#c语言(4550)#安全(4486)#毕业设计(4397)#数据结构(4338)#架构(4170)#docker(4114)#javascript(3979)#大模型(3915)

热门文章

最新文章

归档

分类