队列--C语言实现数据结构

news/2024/11/18 2:20:36/

在这里插入图片描述

本期带大家一起用C语言实现队列🌈🌈🌈

文章目录

    • 1、队列的概念
    • 2、队列的操作流程
    • 3 、队列的结构
    • 4、队列的实现
      • 4.1 队列的结构设计
      • 4.2 队列的初始化
      • 4.3 入队
      • 4.4 判断队列是否为空
      • 4.5 出队
      • 4.6 获取队头数据
      • 4.7 获取队尾数据
      • 4.8 获取队列当中数据的个数
      • 4.9 队列的销毁
    • 5、栈和队列OJ题
      • 5.1 [队列模拟栈](https://leetcode.cn/problems/implement-stack-using-queues/)
      • 5.2 栈模拟队列
      • 5.3 循环队列
    • 6、感谢与交流✅

1、队列的概念

队列是一种线性数据结构，它按照先进先出（FIFO）的原则进行操作。可以把队列想象成排队买票或者排队上公交车的队伍。

顺序队列由一个连续的内存区域组成，可以存储多个元素。队列有两个指针，分别指向队头（Front）和队尾（Rear）。
链式队列由一系列节点构成，每个节点包含存储的元素值和指向下一个节点的指针
队列的基本操作包括：

  1. 入队（Enqueue）：将新元素插入到队尾，如果队列已满则无法插入。
  2. 出队（Dequeue）：移除队头元素，并返回该元素，如果队列为空则无法执行。
  3. 获取队头元素（Front）：获取队头元素的值，但不对队列进行修改。
  4. 判断队列是否为空（isEmpty）：判断队列中是否没有任何元素。
  5. 判断队列是否已满（isFull）：判断队列是否已经达到了最大容量。

队列的操作遵循先进先出的原则，即先入队的元素先出队。在队列中，新元素被插入到队列的末尾，而出队操作始终从队列的头部进行。

队列常用于需要顺序处理任务或数据的场景，例如处理请求、消息传递、广度优先搜索等算法实现。此外，队列还可以通过循环队列的方式来实现，使得已经出队的元素可以再次被插入到队列的末尾，有效地利用内存空间。

2、队列的操作流程

在这里插入图片描述

3 、队列的结构

队列通常使用数组或链表来实现。以下是两种常见的队列结构：

  1. 基于数组的队列（顺序队列）：

    • 使用一个固定大小的数组来保存队列元素。
    • 需要维护队头和队尾的索引，分别指向队列的第一个元素和最后一个元素。
    • 入队操作将元素添加到队尾，并更新队尾索引。
    • 出队操作将队头元素移除，并更新队头索引。
    • 注意，入队操作可能导致队列满（队尾索引达到数组末尾）的情况，需要进行特殊处理。

  2. 基于链表的队列（链式队列）：

    • 使用链表来动态存储队列元素。
    • 需要维护队头和队尾节点指针，分别指向队列的第一个节点和最后一个节点。
    • 入队操作创建一个新节点，并将其链接到链表末尾，更新队尾指针。
    • 出队操作移除队头节点，并更新队头指针。
    • 注意，链式队列没有固定的大小限制，可以根据需要动态调整。

无论是基于数组还是链表的队列，其核心思想都是维护队头和队尾指针，并通过头部和尾部的插入和删除操作实现先进先出的特性。根据具体的应用场景和需求，选择适合的队列实现方式

在这里我们使用链表来实现队列，避免了用数组队列更新队头数据的遍历，时间复杂度低

4、队列的实现

4.1 队列的结构设计

Queue结构体，它表示整个队列。该结构体包含两个指针成员head和tail，分别指向队列的头部节点和尾部节点
QNode的结构体，它表示队列中的节点。该结构体包含一个指向下一个节点的指针next，以及一个数据data

typedef int QDataTYpe;typedef struct QueueNode
{struct QueueNode* next;QDataTYpe data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;

4.2 队列的初始化

现在主函数当中创建了一个Queue q
然后传入q的地址，进行初始化
将队列的头部指针和尾部指针设为NULL，并将队列的大小初始化为0

void QueueInit(Queue* pq)
{pq->head = NULL;pq->tail = NULL;pq->size = 0;
}

4.3 入队

在函数内部，首先进行断言assert(pq)来确保指针pq不为空。

然后，通过动态内存分配malloc来创建一个新的节点newnode，并将其类型转换为QNode*。

接下来，检查是否成功分配内存，如果分配失败，则输出错误信息并返回。

然后，将新节点的数据成员data赋值为传入的参数x，同时将新节点的下一个指针next设置为NULL，新节点表示当前节点是队列的尾部节点。

接着，根据队列是否为空，有两种情况处理：

  • 如果队列为空，即头部指针head为NULL，表示当前队列没有任何节点，此时将头部指针和尾部指针都指向新节点newnode。
  • 如果队列不为空，即头部指针head不为NULL，表示当前队列已存在节点，此时将队列尾部节点的下一个指针next指向新节点newnode，然后将尾部指针tail更新为新节点newnode
  • 最后，将队列的大小size加1，表示新增了一个节点。
void QueuePush(Queue* pq,QDataTYpe x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));;if (newnode == NULL){perror("malloc:fail");return;}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;}

4.4 判断队列是否为空

判断队列是否为空的话，相对来说是比较简单的
有两种判断方法
根据队列的头指针是否为空判断
根据队列当中的数据个数size判断

bool QueueEmpty(Queue* pq)
{return pq->head == NULL;//return pq->size==0;
}

4.5 出队

出队列的话我们需要先判断当前队列是否为空
队列为空的话那我们就直接返回
队列不为空的话又分两种情况
1、队头指针==队尾指针

2、队头指针！=队尾指针

void QueuePop(Queue* pq)
{assert(pq);if (QueueEmpty(pq)){printf("队列为空\n");return;}if (pq->head == pq->tail){free(pq->head);pq->head = NULL;pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}

4.6 获取队头数据

获取队头数据的话，需要先判断队列是否为空，为空的话就直接返回
队列不为空，返回队头数据

QDataTYpe QueueFront(Queue* pq)
{assert(pq);if (QueueEmpty(pq)){printf("队列为空\n");return;}elsereturn pq->head->data;
}

4.7 获取队尾数据

获取队尾数据的话，同样需要判断队列是否为空，为空的话也就直接返回
队列不为空的话，返回队尾数据

QDataTYpe QueueBack(Queue* pq)
{assert(pq);if (QueueEmpty(pq)){printf("队列为空\n");return;}elsereturn pq->tail->data;
}

4.8 获取队列当中数据的个数

获取队列数据的个数，直接返回pq->size

int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

4.9 队列的销毁

使用循环遍历队列中的所有节点，直到遍历到最后一个节点，即当前节点为NULL


void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur != NULL){QNode* next = cur->next;free(cur);cur = next;}pq->head = NULL;pq->tail = NULL;pq->size = 0;}

5、栈和队列OJ题

5.1 队列模拟栈

在这里插入图片描述

使用两个队列来实现栈的重点在于以下几点：

  1. 始终保持一个队列为空，另一个队列非空。
  2. 入数据时，将元素入队到不为空的队列中。
  3. 出数据时，将非空队列中的元素转移到空队列中，直到队列中只剩下一个元素。
  4. 出队原先非空队列的数据，原先非空队列变为空，即可实现栈的后进先出操作。

通过将元素入队到非空队列、转移到空队列以及出队的操作，可以模拟栈的后进先出特性

在这里插入图片描述

typedef int QDataTYpe;typedef struct QueueNode
{struct QueueNode* next;QDataTYpe data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QueueInit(Queue* pq);void QueueDestroy(Queue* pq);void QueuePush(Queue* pq,QDataTYpe x);void QueuePop(Queue* pq);bool QueueEmpty(Queue* pq);QDataTYpe QueueFront(Queue* pq);QDataTYpe QueueBack(Queue* pq);int QueueSize(Queue* pq);
void QueueInit(Queue* pq)
{pq->head = NULL;pq->tail = NULL;pq->size = 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur != NULL){QNode* next = cur->next;free(cur);cur = next;}pq->head = NULL;pq->tail = NULL;pq->size = 0;}bool QueueEmpty(Queue* pq)
{return pq->head == NULL;//return pq->size==0;
}void QueuePush(Queue* pq,QDataTYpe x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));;if (newnode == NULL){perror("malloc:fail");return;}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;}void QueuePop(Queue* pq)
{assert(pq);if (QueueEmpty(pq)){printf("队列为空\n");return;}if (pq->head == pq->tail){free(pq->head);pq->head = NULL;pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = NULL;pq->head = next;}pq->size--;
}QDataTYpe QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataTYpe QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}typedef struct {Queue q;Queue p;
} MyStack;MyStack* myStackCreate() {MyStack*obj=(MyStack*)malloc(sizeof(MyStack));if(obj==NULL){return NULL;}QueueInit(&obj->p);QueueInit(&obj->q);return obj;
}void myStackPush(MyStack* obj, int x) {if(QueueEmpty(&obj->p)){QueuePush(&obj->q,x);}else{QueuePush(&obj->p,x);}
}int myStackPop(MyStack* obj) {Queue*Empty=&obj->q;Queue*NoEmpty=&obj->p;if(QueueEmpty(&obj->p)){Empty=&obj->p;NoEmpty=&obj->q;}while(QueueSize(NoEmpty)>1){QueuePush(Empty,QueueFront(NoEmpty));QueuePop(NoEmpty);}int top=QueueFront(NoEmpty);QueuePop(NoEmpty);return top;
}int myStackTop(MyStack* obj) {if(QueueEmpty(&obj->p)){return QueueBack(&obj->q);}elsereturn QueueBack(&obj->p);
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q)&&QueueEmpty(&obj->p);
}void myStackFree(MyStack* obj) {QueueDestroy(&obj->q);QueueDestroy(&obj->p);free(obj);
}

5.2 栈模拟队列

栈模拟队列
在这里插入图片描述
栈模拟队列的话，可以想象成一个连通器
在这里插入图片描述

在这里插入图片描述

typedef int STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;//初始化
void STInit(ST* ps);//销毁
void STDestroy(ST* ps);//压栈void STPush(ST* ps,STDataType x);//出栈void STPop(ST* ps);//判空bool STEmpty(ST* ps);//栈顶STDataType STTop(ST* ps);//个数int STSize(ST* ps);void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;}void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}void STPush(ST* ps,STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity*sizeof(STDataType));if (tmp == NULL){perror("realloc :fail");return;}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top++] = x;}bool STEmpty(ST* ps)
{return ps->top == 0;
}void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}STDataType STTop(ST* ps)
{assert(ps);return ps->a[ps->top - 1];}int STSize(ST* ps)
{assert(ps);return  ps->top;}typedef struct {ST pushst;ST popst;
} MyQueue;MyQueue* myQueueCreate() {MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));STInit(&obj->pushst);STInit(&obj->popst);return obj;}void myQueuePush(MyQueue* obj, int x) {STPush(&obj->pushst,x);}int myQueuePop(MyQueue* obj) {int ret=myQueuePeek(obj);STPop(&obj->popst);return ret;}int myQueuePeek(MyQueue* obj) {if(STEmpty(&obj->popst)){while(!(STEmpty(&obj->pushst))){STPush(&obj->popst,STTop(&obj->pushst));STPop(&obj->pushst);}}return STTop(&obj->popst);
}bool myQueueEmpty(MyQueue* obj) {return STEmpty(&obj->pushst)&&STEmpty(&obj->popst);
}void myQueueFree(MyQueue* obj) {STDestroy(&obj->pushst);STDestroy(&obj->popst);free(obj);
}/*** Your MyQueue struct will be instantiated and called as such:* MyQueue* obj = myQueueCreate();* myQueuePush(obj, x);* int param_2 = myQueuePop(obj);* int param_3 = myQueuePeek(obj);* bool param_4 = myQueueEmpty(obj);* myQueueFree(obj);
*/

5.3 循环队列

循环队列
在这里插入图片描述
解决循环队列问题的话
我们可以先定义固定大小的数组，用来存储元素
例如，我们需要一个可以存储3个数据的数组，我们现在就开辟4个数据的空间，以便于我们操作在这里插入图片描述

在这里插入图片描述

typedef struct {int front;int rear;int size;int *a;
} MyCircularQueue;
bool myCircularQueueIsFull(MyCircularQueue* obj) ;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a=(int*)malloc(sizeof(int)*(k+1));obj->size=k+1;obj->front=0;obj->rear=0;return obj;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if((obj->rear+1)%(obj->size)==obj->front)return false;obj->a[obj->rear]=value;obj->rear++;obj->rear%=obj->size;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(obj->rear==obj->front)return false;(obj->front)++;obj->front%=obj->size;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(obj->rear==obj->front)return -1;return obj->a[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(obj->rear==obj->front)return -1;return obj->a[(obj->rear-1+obj->size)%obj->size];}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if(obj->rear==obj->front)return true;return false;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {if((obj->rear+1)%(obj->size)==obj->front)return true;return false;
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);obj->a=NULL;free(obj);
}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj = myCircularQueueCreate(k);* bool param_1 = myCircularQueueEnQueue(obj, value);* bool param_2 = myCircularQueueDeQueue(obj);* int param_3 = myCircularQueueFront(obj);* int param_4 = myCircularQueueRear(obj);* bool param_5 = myCircularQueueIsEmpty(obj);* bool param_6 = myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
*/

6、感谢与交流✅

🌹🌹🌹如果大家通过本篇博客收获了,对队列有了新的了解的话
那么希望支持一下哦如果还有不明白的，疑惑的话，或者什么比较好的建议的话，可以发到评论区，
我们一起解决，共同进步 ❗️❗️❗️
最后谢谢大家❗️❗️❗️💯💯💯


http://www.ppmy.cn/news/879112.html

相关文章

大自然Windows XP日文版镜像

大自然Windows XP日文版镜像

日文原版Windows XP镜像下载。 https://pan.baidu.com/s/111tNJFcd9uqbs82eQpUuag 提取码：g2f8 感谢作者的分享！
阅读更多...
hpy计算机维护系统 iso,hpy计算机维护系统.doc

hpy计算机维护系统 iso,hpy计算机维护系统.doc

文档介绍： 本贴导读为方便阅读,本帖汇编了本人历次发表的HPY系列五个板块八款启动U盘,包括UI写入GRUB型,UI写入SYSLINUX型,HP格式化grldr型,Fbinst全外置型,Fbinst全内置型,isolinux量产型以及 计算机维护系统ISO版和计算机维护系统GHO版。对每款启动盘的主要功能、…
阅读更多...
hpy计算机维护系统,HPY计算机维护系统.doc

hpy计算机维护系统,HPY计算机维护系统.doc

HPY计算机维护系统，集模版\3用版\网启版\新ud版\安装版\GHO制作包(7月16日) 本贴导读为方便阅读，本帖汇编了本人历次发表的HPY系列五个板块八款启动U盘，包括UI写入GRUB型，UI写入SYSLINUX型，HP格式化grldr型&#xff0c…
阅读更多...
U盘安装xp系统

U盘安装xp系统

安装过程 不想花费时间，直接下载，看教程安装(1) 推荐一个百度网盘下载工具， 以下是我的安装过程(2) 尝试使用MSCN上下载的xp sp3.iso镜像安装(3) 使用U盘安装大师安装Ghost Win XP系统（使用原版xp sp3.iso镜像）(4)最后…
阅读更多...
Windows XP / 2003 / Vista 原版光盘镜像（下载）及其主要特征

Windows XP / 2003 / Vista 原版光盘镜像（下载）及其主要特征

下载前必读—— WindowsXP“三优”进阶——优化资源、优化系统、优化技巧 关于Windows Vista——下载 刻盘 安装 激活 优化 安全 比较 综合 最新下载：Windows Vista 系统资源和破解激活工具大全（打包集成） ——压缩包内有：VISTA所有激活破解工具。可以成功激活并通过正版验…
阅读更多...
微软原版XP专业版ISO镜像(SP2)

微软原版XP专业版ISO镜像(SP2)

下载地址: http://www.ydez.com/tx/WindowsXP%20SP2.iso CD-KEY: DG8FV-B9TKY-FRT9J-6CRCC-XPQ4G 优点: (1) 只集成SP2 (2) 运行起来速度很快，而且很稳定（不容易出错） (3) VOL版本，没有激活概念，可以无限升级 必须…
阅读更多...
VMware安装winXP SP3专业版+常用软件+正常联网

VMware安装winXP SP3专业版+常用软件+正常联网

VMware安装winXP SP3专业版 VMware配置准备系统镜像原版WIN XP SP3专业版第三方Ghost镜像 原版镜像安装过程Ghost安装过程测试效果 VMware配置 这部分简单过一下，用VM装过虚拟机的都知道基本用法，教程也很多，就不细说了。给一下我的设置&…
阅读更多...
安装微软原版WinXP方法教程

安装微软原版WinXP方法教程

照例先推荐下载地址：ed2k://|file|zh-hans_windows_xp_professional_with_service_pack_3_x86_cd_x14-80404.iso|630239232|CD0900AFA058ACB6345761969CBCBFF4|/ 新建虚拟机，上篇Ghost XP文章已经说过了，只需把镜像换成你下载的XP原版中文镜像就可以啦~~ 方法详见[VM安装Gho…
阅读更多...
最新文章

Copyright @ 2022~2023