当前位置：首页 > web >正文

【数据结构初阶】--栈和队列(二)

web 2025/7/23 10:09:48

🔥个人主页：@草莓熊Lotso

🎬作者简介：C++研发方向学习者

📖个人专栏： 《C语言》《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》

⭐️人生格言：生活是默默的坚持，毅力是永久的享受。

前言：在上篇博客中我们简单完成了栈这个数据结构的实现，那么这次我们要实现的是队列，队列这个数据结构实现起来也不会很难，还是和之前一样，先部分实现，最后展现全部的代码

一.队列的概念与结构

二. 队列的入队和出队

入队：

出队：

三.队列取队首数据和队尾数据

取队首数据：

取队尾数据：

四.队列的有效数据个数和队列的销毁

队列的有效数据个数：

销毁队列：

五.代码展现

Queue.h：

Queue.c：

test.c：

一.队列的概念与结构

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

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

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

队列底层结构选型：

队列可以用数组和链表的结构实现，使用链表的结构实现更优一点，如果使用数组的结构，出队列在数组头部出数据，时间复杂度高。虽然使用链表在入队尾插的时候，时间复杂度也高，但我们可以额外定义一个尾结点，这样就可以优化了

结构定义：

typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;typedef struct Queue
{QueueNode* phead;QueueNode* ptail;//int size;//队中有效数据个数
}Queue;

二. 队列的入队和出队

--我们实现队列的入队是在队尾操作的，所以我们可以参考链表的尾插，但是这里我们已经定义了一个尾节点了，所以会更简单点

入队：

//入队
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//申请新节点QueueNode* newcode = (QueueNode*)malloc(sizeof(QueueNode));if (newcode == NULL){perror("malloc fail!");exit(1);}newcode->data = x;newcode->next = NULL;//如果队列为空if (pq->phead == NULL){pq->phead = pq->ptail = newcode;//pq->size++;}else{pq->ptail->next = newcode;pq->ptail = pq->ptail->next;//pq->size++;}
}

我们入队之前，需要申请一个新的节点，操作起来和链表里面的一样，申请完后先判断链表是不是为空，为空和不为空需要分类讨论，如果为空就直接令头节点和尾节点都为newcode，如果不为空就是在尾节点后链接上新节点，然后尾节点往前走。

--在实现出队之前，我们需要考虑到一个队列为空的问题，如果队列为空是不是就不能删了呢，所以我们这里来实现一个判断链表是否为空的接口吧，这个实现起来很简单，就不多说了

//队列判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}

出队：

//出队
void QueuePop(Queue* pq)
{assert(!QueueEmpty(pq));//如果队伍中只有一个节点if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;//pq->size--||pq->size=0}else{QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;//pq->size--;}
}

我们需要注意的是断言结束后，如果队伍只有一个节点，我们直接释放掉后使置为空就行了，如果不止一个节点我们需要先记录下一个节点，再释放，然后让头节点来到下一个节点的位置。

三.队列取队首数据和队尾数据

取队首数据：

//取队首数据
QDataType QueueHead(Queue* pq)
{assert(!QueueEmpty(pq));return pq->phead->data;
}

队首数据不就是头节点的数据吗，直接返回就好了

取队尾数据：

//取队尾数据
QDataType QueueTail(Queue* pq)
{assert(!QueueEmpty(pq));return pq->ptail->data;
}

队尾数据不就是头节点的数据吗，直接返回就好了

--实现完前面的接口之后我们可以测试一下看看

test.c：

#include"Queue.h"void test1()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);printf("队首是:%d\n",QueueHead(&q));printf("队尾是:%d\n",QueueTail(&q));
}int main()
{test1();
}

--测试完成，打印出了队尾和队首数据，退出码为0