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

ops/2024/11/27 6:03:05/

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

🌅主页：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/ops/137004.html

相关文章

我谈离散傅里叶变换的补零

我谈离散傅里叶变换的补零

有限序列的零延拓——零延拓不会改变离散傅里叶变换的形状的续篇。 L点序列可以做N点傅里叶变换&#xff0c;当 L ⩽ N L\leqslant N L⩽N时不会产生混叠。这部分内容在Rafael Gonzalez和Richard Woods所著的《数字图像处理》完全没有提到。 补零是序列末尾补零&#xff0c;不…
阅读更多...
簡單易懂：如何在Windows系統中修改IP地址？

簡單易懂：如何在Windows系統中修改IP地址？

無論是為了連接到一個新的網路&#xff0c;還是為了解決網路連接問題&#xff0c;修改IP地址都是一個常見的操作。本文將詳細介紹如何在Windows系統中修改IP地址&#xff0c;包括靜態IP地址的設置和動態IP地址的獲取。 IP地址是什麼&#xff1f; IP地址是互聯網協議地址的簡稱…
阅读更多...
nodejs第三方库sharp对图片的操作生成新图片、压缩、添加文字水印及图片水印等

nodejs第三方库sharp对图片的操作生成新图片、压缩、添加文字水印及图片水印等

Sharp是一个基于libvips的高性能Node.js图像处理库&#xff0c;它提供了广泛的功能&#xff0c;包括调整大小、裁剪、旋转、格式转换等。Sharp可以处理多种图像格式&#xff0c;并且能够高效地转换图像格式。 相关说明及用法看&#xff1a;https://sharp.nodejs.cn/ 安装&#…
阅读更多...
k8s集群增加nfs-subdir-external-provisioner存储类

k8s集群增加nfs-subdir-external-provisioner存储类

文章目录 前言一、版本信息二、本机安装nfs组件包三、下载nfs-subdir-external-provisioner配置文件并进行配置1.下载文件2.修改配置 三、进行部署备注&#xff1a;关于镜像无法拉取问题的处理 前言 手里的一台服务器搭建一个单点的k8s集群&#xff0c;然后在本机上使用nfs-su…
阅读更多...
001 MATLAB介绍

001 MATLAB介绍

前言&#xff1a; 软件获取渠道有很多&#xff0c;难点也就是百度网盘下载慢&#xff1b; 线上版本每月有时间限制。 01 MATLAB介绍 性质&#xff1a; MATLAB即Matrix Laboratory 矩阵实验室的意思&#xff0c;是功能强大的计算机高级语言, 已广泛应用于各学科研究部门、…
阅读更多...
力扣-位运算-4【算法学习day.44】

力扣-位运算-4【算法学习day.44】

前言 ###我做这类文章一个重要的目的还是给正在学习的大家提供方向和记录学习过程&#xff08;例如想要掌握基础用法&#xff0c;该刷哪些题&#xff1f;&#xff09;我的解析也不会做的非常详细&#xff0c;只会提供思路和一些关键点&#xff0c;力扣上的大佬们的题解质量是非…
阅读更多...
logminer挖掘日志归档查找问题

logminer挖掘日志归档查找问题

--根据发生问题时间点查找归档文件 select first_time,NAME from gv$archived_log where first_time>2016-03-15 17:00:00 and first_time<2016-03-15 21:00:00; 2016-03-15 17:23:55 ARCH/jxdb/archivelog/2016_03_15/thread_1_seq_41588.4060.906577337 2016-03-15 17:…
阅读更多...
从零开始：Linux 环境下的 C/C++ 编译教程

从零开始：Linux 环境下的 C/C++ 编译教程

个人主页&#xff1a;chian-ocean 文章专栏 前言&#xff1a; GCC&#xff08;GNU Compiler Collection&#xff09;是一个功能强大的编译器集合&#xff0c;支持多种语言&#xff0c;包括 C 和 C。其中 gcc 用于 C 语言编译&#xff0c;g 专用于 C 编译。 Linux GCC or G的安…
阅读更多...
最新文章

Copyright @ 2022~2023