C语言数据结构——队列（queue）

lunar_coder

540人浏览 · 2026-03-05 13:23:43

lunar_coder · 2026-03-05 13:23:43 发布

大家好，今天为大家带来C语言初阶数据结构中关于栈的相关知识

1.我们首先定义一个结构体变量来描述这个循环队列：

大家好，今天为大家带来C语言初阶数据结构中关于栈的相关知识

队列：是一种特殊的线性表结构，其结构允许在固定的一端进数据，在另一端出数据，队列中数据遵循先进先出的原则（FIFO）：

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

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

这和我们现实中的"队列"是一样的，先排队的先享受服务，后到的后享受服务

1.队列的实现方法

队列的实现方法和栈一样，也可以用数组或链表来实现，我们这里就用链表的形式来实现队列

1.1链表来实现队列的前瞻思路

链表的基本结构：每个链表单元是由数据（data）和指向下一个节点的地址指针（next）组成的

typedef int QDatatype;

typedef struct QListNode
{
	QDatatype data;
	struct QListNode* next;
}QListNode;

但是当我们每要增加数据时，都要遍历一遍数据，时间复杂度为O（n），这时我们就将他尾部的链表单元储存起来，这样当要增加元素时就能够直接调整，不再需要遍历

这时我们如果再将头部的节点也储存起来放在一个结构体内（也能再放入一个Size来储存数据个数），这样我们足以实现入队列和出队列的操作

typedef struct Queue//储存队头与队尾
{
	QListNode* head;
	QListNode* tail;
	int Size;
}Queue;

1.2数组来实现队列的前瞻思路

数组来实现队列要有一个变量（head）来储存它队头的位置，还要一个变量（tail）储存队尾的位置，入队：放入数据，tail++；出队：释放队头数据，head++；

typedef int QDatatype;

#define MAX_SIZE 5

typedef struct Queue
{
	QDatatype val[MAX_SIZE];
	int head;
	int tail;
};

注：数组实现队列时，一旦释放一个数据，前面的空间就无法再访问，因此，常常会出现假溢出的情况

虽然我们可以再多开一个空间让队列循环起来，但是空间有限，用数组一般处理循环队列问题，平常实现就用链表就行

2.队列的功能目录

//初始化与销毁
void QListInit(Queue* pq);
void QListDestroy(Queue* pq);

//队尾入队,队头出队
void QListPush(Queue* pq, QDatatype n);
void QListPop(Queue* pq);

//获取队头或队尾数据
QDatatype QListFront(Queue* pq);
QDatatype QListBack(Queue* pq);

//获取数据个数和判空
int QListSize(Queue* pq);
bool QListEmpty(Queue* pq);

3.队列的实现（链表式）

3.1定义队列

//定义队列,链表式（先进先出）
typedef int QDatatype;

typedef struct QListNode//队列元素
{
	QDatatype data;
	struct QListNode* next;
}QListNode;

typedef struct Queue//储存队头与队尾
{
	QListNode* head;
	QListNode* tail;
	int Size;
}Queue;

3.2初始化和销毁

//初始化与销毁
void QListInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->Size = 0;
}

void QListDestroy(Queue* pq)
{
	assert(pq);
	while (pq->head)
	{
		QListNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->head = pq->tail = NULL;
	pq->Size = 0;
}

3.3入队列

//队尾入队
void QListPush(Queue* pq, QDatatype n)
{
	assert(pq);
	QListNode* newnode = (QListNode*)malloc(sizeof(QListNode));
	if (newnode == NULL)
	{
		perror("malloc()::");
		exit(1);
	}
	newnode->data = n;
	newnode->next = NULL;
	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = pq->tail->next;
	}
	pq->Size++;
}

3.4出队列

//队头出数据
void QListPop(Queue* pq)
{
	assert(pq && pq->Size);
	if (pq->tail == pq->head)//一个节点
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QListNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->Size--;
}

3.5获取队头或队尾数据

//获取队头或队尾数据
QDatatype QListFront(Queue* pq)
{
	assert(pq && pq->Size);
	return pq->head->data;
}
QDatatype QListBack(Queue* pq)
{
	assert(pq && pq->Size);
	return pq->tail->data;
}

3.6判空及统计队中数据个数

//获取数据个数和判空
int QListSize(Queue* pq)
{
	assert(pq);
	return pq->Size;
}
bool QListEmpty(Queue* pq)//为空返回true
{
	return pq->Size == 0;
}

我们调试一下发现能够跑起来，其结果与预期结果相同

4.扩展了解：循环队列

循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值

简单来说，利用循环队列就能用有限的空间去循环的存放数据，就像图书馆占位一样，人满了就不能插入，但队头的人走了，下一个数据就能储存进来

622. 设计循环队列 - 力扣（LeetCode）

4.1数组法：

1.我们首先定义一个结构体变量来描述这个循环队列：

head：对头数据的下标

tail：队尾数据的下标 + 1(这里是因为我把 tail 初始化为0，如果初始化为-1，则对应的是队尾下标，但其它位置也要做出合理变动)

k：循环空间的可储存数据的大小（不是实际大小）

2.队列初始化：

这道题的要求是有返回值的：所以我们要动态开辟一个空间，大小为k + 1！！！

原因是如果不这样做，在判满和判空时就有歧义：条件都是obj->head == obj->tail

所以就再多开辟一个空间（或者再在结构体中再定义一个成员，来记录队列中的数据个数）

3.入循环队列（假设队列空间是4）

这里由于多开辟了一个空间，所以判满就是：obj->tail + 1 == obj->head

但是我们发现如果是下图这种情况就不成立了

我们发现obj->tail + 1 != obj->head ,但是空间已经满了，这时我们发现obj->tail == 4,obj->k == 5，所以我们可以进行+1再取模的操作，即(obj->tail + 1) % obj->k == obj->head(注意符号优先级)

同理：如果将数据成功放到队列中，也要让(obj->tail + 1 )% obj->k

4.出队列

同上：obj->head = (obj->head + 1) % obj->k

如果obj->head == obj->tail 就为空

5.返回队头数据

即为: return obj->arr[obj->head];

若为空返回-1（EOF）

6.返回队尾数据

是不是和上面的一样（ return obj->arr[obj->tail - 1]; ）？

其实是错的！

当我们是上面这种情况的话：就为非法访问了

这里我提供两种解法：

a. 用三木操作符：return obj->tail == 0? obj->arr[obj->k - 1] : obj->arr[obj->tail - 1];

b. return obj->arr[(obj->tail - 1 + obj->k) % obj->k];

当然：要先判空!

完整代码：

typedef struct {
    int* arr;
    int head;//队头元素
    int tail;//队尾元素下标+1
    int k;//空间大小
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->arr = (int*)malloc(sizeof(int) * (k + 1));
    obj->k = k + 1;
    obj->head = obj->tail = 0;
    return obj;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if ((obj->tail + 1) % obj->k == obj->head)
        return false;
    obj->arr[obj->tail] = value; 
    obj->tail = (obj->tail + 1) % obj->k;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (obj->head == obj->tail)
        return false;
    obj->head = (obj->head + 1) % obj->k;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if (obj->head == obj->tail)
        return EOF;
    return obj->arr[obj->head];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if (obj->head == obj->tail)
        return EOF;
    return obj->arr[(obj->tail - 1 + obj->k) % obj->k];
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->head == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail + 1) % obj->k == obj->head;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->arr);
    free(obj);
}

4.2链表法（循环链表的设计）

这里有循环链表的构建方法 ->

C语言数据结构——链表_链表数据结构c语言-CSDN博客

这里就留给读者自行研究

代码献上：

typedef struct qlistnode
{
    int val;
    struct qlistnode* next;
}qlistnode;


typedef struct {
    qlistnode* head;
    qlistnode* tail;
    int k;
    int Size;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->head = obj->tail = NULL;
    obj->k = k;
    obj->Size = 0;
    return obj;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (obj->Size == obj->k)
        return false;
    qlistnode* newnode = (qlistnode*)malloc(sizeof(qlistnode));
    newnode->next = NULL;
    newnode->val = value;
    if (obj->head == NULL)
    {
        obj->head = obj->tail = newnode;
        obj->head->next = obj->tail;
    }
    else
    {
        newnode->next = obj->head;
        obj->tail->next = newnode;
        obj->tail = newnode;
    }
    obj->Size++;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (obj->Size == 0)
        return false;
    if (obj->Size == 1)
    {
        free(obj->head);
        obj->head = obj->tail = NULL;
    }
    else
    {
        qlistnode* next = obj->head->next;
        free(obj->head);
        obj->head = next;
    }
    obj->Size--;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if (obj->Size == 0)
        return EOF;
    return obj->head->val;
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if (obj->Size == 0)
        return EOF;
    return obj->tail->val;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if (obj->Size == 0)
        return true;
    return false;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if (obj->Size == obj->k)
        return true;
    return false;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    while (!myCircularQueueIsEmpty(obj))
    {
        myCircularQueueDeQueue(obj);
    }
    free(obj);
}

感谢阅读，希望能够帮到你，也欢迎大家指错及补充

天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

deck.gl TripsLayer 出租车轨迹动画示例实战：从示例运行到着色器原理

TripsLayer 是 deck.gl 中用于渲染**随时间流动的轨迹动画**（如出租车行程、物流路径、迁徙路线）的核心图层。本文以仓库中的最小独立示例 [examples/website/trips](https://link.gitcode.com/i/1442af8f442f4cff39ff546e050fceb5) 为骨架，带你完成从安装依赖、启动应用、理解曼哈顿出租车数据格式，到深入

天工造物局

Foundry Anvil 中 eth_simulateV1 的 Blob 交易与 Blob Gas 字段规范化：原理、实现与测试验证

本篇技术指南以 [anvil-simulate-blob-transactions.md](https://link.gitcode.com/i/3d2ebe227262de169335eb290af80da8) 这条 changelog 条目为起点，深入剖析 Foundry Anvil 对 `eth_simulateV1` RPC 返回结果中 blob（EIP-4844）交易与 blob gas

天工造物局

LMCache CLI 实战：用 `lmcache kvcache clear` 管理运行中服务的 KV Cache 状态

本文是一份针对 LMCache 官方 CLI 命令 `lmcache kvcache` 的完整技术指南。该命令用于在**运行中的 LMCache 服务（MP HTTP server）**上管理 KV cache 状态，当前提供 `clear` 子命令，用于清空 L1（CPU 内存）层中缓存的全部 KV 数据。读完本文，你将掌握该命令的完整参数体系、退出码语义、终端/JSON/静默三种输出模式，并能