【数据结构实战篇】用C语言实现你的私有队列

news/2024/11/27 8:19:29/

🏝️专栏：【数据结构实战篇】

🌅主页：f狐o狸x

         在前面的文章中我们用C语言实现了栈的数据结构，本期内容我们将实现队列的数据结构

一、队列的概念

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

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

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

二、队列的实现

        2.1 队列的定义

        动用你聪明的小脑袋想一想队列的结构是啥样的，是不是从队尾插入数据，再从队头输出数据，那是不是在队列的结构里面需要一个头结点，还需要一个尾节点，为了方便后面的操作，我们再加一个size变量来记录当前队列的大小


typedef int QDatatype;typedef struct QueueNode
{QDatatype Data;struct QueueNode* next;
}QueueNode;typedef struct Queue
{struct QueueNode* head;struct QueueNode* tail;int size;
}Queue;

        2.2 队列的初始化

//初始化队列
void QueueInit(Queue* pq)
{pq->size = 0;pq->head = NULL;pq->tail = NULL;
}

        2.3 队列入、出

        其实这里就是简单的尾插和头删

//队列增
void QueuePush(Queue* pq, QDatatype x)
{QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail");return;}newnode->Data = x;newnode->next = NULL;if (pq->head == NULL){assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}
//队列删
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));QueueNode* cur = pq->head;if (cur->next == NULL){free(cur);cur = NULL;}else{pq->head = pq->head->next;free(cur);cur = NULL;}pq->size--;
}

        2.4 检查队列是否为空、队列大小

//队列大小
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}

        2.5 返回队头、队尾

//返回队头
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;
}

        2.6 测试队列


int main()
{Queue Q = { 0 };QueueInit(&Q);QueuePush(&Q, 1);QueuePush(&Q, 2);QueuePush(&Q, 3);QueuePush(&Q, 4);QueuePush(&Q, 5);QueuePush(&Q, 6);while (!QueueEmpty(&Q)){printf("%d ", QueueFront(&Q));QueuePop(&Q);}return 0;
}

        运行结果如下：

三、实战练习

        学习了栈和队列的数据结构，我们现在就来练练手

        3.1 有效的括号

        力扣链接：有效的括号

        给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效

        3.1.1题目分析

        这个题可以用栈的结构来完成这个题，如果字符串中是左括号 ‘ （ ’ ‘ [ ’ ‘ { ’，则正常入栈，如果字符串为右括号‘ ) ’ ‘ ] ’ ‘ } ’，则将这个字符和栈顶元素对比，如果相等就进行下一次循环，如果没有匹配成功，则放回false，循环结束后，并且栈里没有元素了，就返回true，记得在每次返回的时候将空间释放了，不要有内存泄漏哈~

        3.1.2 解题代码

        对了，因为这里用的是c语言，因此我们需要自己手搓一个栈，不过问题不大啦

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int StackDataType;typedef struct stack
{int* StackData;int top;int capacity;
}ST;//初始化
void InitStack(ST* ps);
//销毁
void DestoryStack(ST* ps);
//增加
void STPush(ST* ps, StackDataType x);
//删除
void STPop(ST* ps);
//判断是否为空
bool STEmpty(ST* ps);
//栈顶位置
StackDataType STTop(ST* ps);//初始化
void InitStack(ST* ps)
{assert(ps);ps->StackData = (StackDataType*)malloc(sizeof(StackDataType)*4);if (ps->StackData == NULL){perror("InitStack：：malloc");return;}ps->capacity = 4;ps->top = 0;
}//销毁
void DestoryStack(ST* ps)
{assert(ps);free(ps->StackData);ps->StackData = NULL;ps->capacity = 0;ps->top = 0;
}//增加
void STPush(ST* ps, StackDataType x)
{assert(ps);if (ps->top == ps->capacity){StackDataType* tmp = (StackDataType*)realloc(ps->StackData,sizeof(StackDataType) * ps->capacity * 2);if(tmp == NULL){perror("STPush：：realloc");return;}ps->StackData = tmp;ps->capacity *= 2;}ps->StackData[ps->top] = x;ps->top += 1;}//删除
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}//判断是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//栈顶位置
StackDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->StackData[ps->top - 1];
}bool isValid(char* s) {ST st = {0};InitStack(&st);char* ps = s;while(*s){if(*s == '(' || *s == '[' || *s == '{'){STPush(&st, *s);//左括号入栈}else{if(STEmpty(&st)){DestoryStack(&st);return false;}char top = STTop(&st);STPop(&st);if((*s == ')' && top != '(') ||(*s == ']' && top != '[') ||(*s == '}' && top != '{')){DestoryStack(&st);return false;                }}s++;}bool ret = STEmpty(&st);DestoryStack(&st);return ret;
}

        3.2 用队列实现栈

        力扣链接：用队列实现栈

        请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）

        3.2.1 题目分析

        题目要求我们用两个队列来实现栈的结构，因此我们可以先随便将数据输入到一个队列中，再把队列一中的数据除了最后一个，全部转移到另外一个空的队列中，这样就可以实现栈的操作

         3.2.2 解题代码

        这里也是同样的需要我们手搓一个队列出来，不过上面已经实现过来，所以我们直接cv一下

typedef int QDatatype;typedef struct QueueNode
{QDatatype Data;struct QueueNode* next;
}QueueNode;typedef struct Queue
{struct QueueNode* head;struct QueueNode* tail;int size;
}Queue;//初始化队列
void QueueInit(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);
//队列增
void QueuePush(Queue* pq, QDatatype x);
//队列删
void QueuePop(Queue* pq);
//队列大小
int QueueSize(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
//返回队头
QDatatype QueueFront(Queue* pq);
//返回队尾
QDatatype QueueBack(Queue* pq);//初始化队列
void QueueInit(Queue* pq)
{pq->size = 0;pq->head = NULL;pq->tail = NULL;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* cur = pq->head;while (cur){QueueNode* del = cur;cur = cur->next;free(del);}pq->head = NULL;pq->tail = NULL;pq->size = 0;
}
//队列增
void QueuePush(Queue* pq, QDatatype x)
{QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail");return;}newnode->Data = x;newnode->next = NULL;if (pq->head == NULL){assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}
//队列删
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = NULL;}else{QueueNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}
//队列大小
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}
//返回队头
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;
}typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* pst = (MyStack*)malloc(sizeof(MyStack));if(pst == NULL){perror("myStackCreate::malloc");}QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;
}void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}int myStackPop(MyStack* obj) {Queue* emptyQ = &obj->q1;Queue* nonemptyQ = &obj->q2;if(!QueueEmpty(&obj->q1)){emptyQ = &obj->q2;nonemptyQ = &obj->q1;}while(QueueSize(nonemptyQ)>1){QueuePush(emptyQ,QueueFront(nonemptyQ));QueuePop(nonemptyQ);}int top = QueueFront(nonemptyQ);QueuePop(nonemptyQ);return top;
}int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}}bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}

        本期内容到这里就完啦，感谢大家观看~

        对了对了，留下你的三连吧，求你啦~ QAQ


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

相关文章

租赁小程序|租赁系统搭建|租赁系统需求

租赁小程序|租赁系统搭建|租赁系统需求

随着信息技术的高速发展&#xff0c;租赁行业逐渐向智能化、便捷化方向迈进。一款优秀的租赁小程序&#xff0c;旨在为用户提供一站式的租赁服务体验&#xff0c;同时帮助租赁企业优化管理流程&#xff0c;提高业务效率。 一、用户需求精准把握 在开发任何软件产品时&#xff0…
阅读更多...
C# 结构体

C# 结构体

文章目录 前言一、结构体的定义与基本使用&#xff08;一&#xff09;定义结构体&#xff08;二&#xff09;结构体的使用示例 二、C# 结构的特点&#xff08;一&#xff09;丰富的成员类型&#xff08;二&#xff09;构造函数相关限制与特性&#xff08;三&#xff09;继承方面…
阅读更多...
JavaScript的扩展运算符...

JavaScript的扩展运算符...

在JavaScript的世界里&#xff0c;扩展运算符&#xff08;...&#xff09;是一个多功能的工具&#xff0c;它可以在多种不同的上下文中使用&#xff0c;以实现不同的功能。从数组到对象&#xff0c;再到函数&#xff0c;扩展运算符都能大显身手。本文将深入探讨扩展运算符的用法…
阅读更多...
使用 Django 构建支持 Kubernetes API 测试连接的 POST 接口

使用 Django 构建支持 Kubernetes API 测试连接的 POST 接口

文章目录 使用 Django 构建支持 Kubernetes API 测试连接的 POST 接口功能需求使用 kubectl 获取 Token命令解析输出示例 完整代码实现Kubernetes API 客户端类功能说明 Django 接口视图关键点解析 路由配置 接口测试请求示例响应结果成功错误 优化建议1. 安全性2. 错误处理3. …
阅读更多...
PyTorch3

PyTorch3

自动微分&#xff1a; 自动微分模块torch.autograd负责自动计算张量操作的梯度&#xff0c;具有自动求导功能。自动微分模块是构成神经网络训练的必要模块&#xff0c;可以实现网络权重参数的更新&#xff0c;使得反向传播算法的实现变得简单而高效。 张量&#xff1a; Torc…
阅读更多...
深入解析 Django 中数据删除的最佳实践：以动态管理镜像版本为例

深入解析 Django 中数据删除的最佳实践：以动态管理镜像版本为例

文章目录 引言场景与模型设计场景描述 删除操作详解1. 删除单个 Tag2. 批量删除 Tags3. 删除前确认4. 日志记录 高阶优化与问题分析1. 外键约束与误删保护2. 并发删除的冲突处理3. 使用软删除 结合 Django Admin 的实现总结与实践思考 引言 在现代应用开发中&#xff0c;服务和…
阅读更多...
精准零售驱动下的中国零售业变革与“开源 2+1 链动小程序”应用探究

精准零售驱动下的中国零售业变革与“开源 2+1 链动小程序”应用探究

摘要&#xff1a;本文聚焦于中国零售业正迈向的精准零售这一重要趋势&#xff0c;阐述新科技融入促使零售业业态革新&#xff0c;剖析未来零售在商品、供应链、物流系统层面的发展方向与支撑要素。深入解读精准零售内涵及其与现代零售业经营理念、业务方式的契合性&#xff0c;…
阅读更多...
YB2503HV：高效率降压IC，助力电动车、太阳能设备等领域的能源转换

YB2503HV：高效率降压IC，助力电动车、太阳能设备等领域的能源转换

今天我要向大家介绍一款引人注目的产品—— YB2503HV 100V 3A SOP8内置MOS 高效率降压IC。这款单片集成芯片具备可设定输出电流的开关型降压恒压驱动器功能&#xff0c;可广泛应用于电动车、太阳能设备、电子电池充电等领域。让我们一起来看看它的特点和应用吧&#xff01; 首先…
阅读更多...
最新文章

Copyright @ 2022~2023