【数据结构】-- 栈和队列

server/2024/10/21 2:41:11/

🌈 个人主页：白子寰
🔥 分类专栏：python从入门到精通，魔法指针，进阶C++，C语言，C语言题集，C语言实现游戏👈 希望得到您的订阅和支持~
💡 坚持创作博文(平均质量分82+)，分享更多关于深度学习、C/C++，python领域的优质内容！（希望得到您的关注~）

 

目录

栈

引入

介绍

为什么栈用顺序表而不用数组？ 

 栈的实现

stack.h：结构体，栈的声明与定义

stack.c：栈的具体实现代码

栈的初始化

压入

弹出 

取栈顶元素

栈的大小 

判断栈是否为空

栈的销毁

Test.c：栈的测试

队列

引入

介绍

为什么队列选择链表而不用数组？ 

队列实现

Queue.h：结构体，队列的声明和定义

Queue.c：队列函数具体实现

队列初始化

队尾入队列（数据）

队头出队列（数据）

获取队列头部元素

获取队列尾部元素

判断队列是否为空

队列中有效元素个数

队列销毁

Test.c：队列的测试

栈

引入

 

介绍

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）
的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

为什么栈用顺序表而不用数组？ 

由于栈只用在同一端进行插入和删除，因此我们优先选择使用顺序表，因为在顺序表的末尾插入和删除的时间复杂度都是O(1)，并且操作简单 

 

 栈的实现

stack.h：结构体，栈的声明与定义

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);
//取栈顶元素
STDatatype STTPop(ST* ps);
//栈的大小
int STSize(ST* ps);
//判断栈是否为空
bool STEmpty(ST* ps);

 

stack.c：栈的具体实现代码

栈的初始化
void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}
压入
void STPush(ST* ps, STDatatype x)
{assert(ps);//如果栈顶 = 容量，满了if (ps->top == ps->capacity){//扩容int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDatatype* tmp = (STDatatype*)realloc(ps->a, newcapacity * sizeof(STDatatype));if (tmp == NULL){perror("realloc");return;}//赋值ps->a = tmp;ps->capacity = newcapacity;}//新数据给值ps->a[ps->top] = x;ps->top++;
}
弹出 
void STPop(ST* ps)
{assert(ps);//判断栈是否为空assert(!STEmpty(ps));//栈顶元素删除ps->top--;
}
取栈顶元素
STDatatype STTPop(ST* ps)
{assert(ps);//判断栈是否为空assert(!STEmpty(ps));return ps->a[ps->top - 1];//栈顶元素下标
}
栈的大小 
int STSize(ST* ps)
{assert(ps);return ps->top;
}
判断栈是否为空
bool STEmpty(ST* ps)
{assert(ps);//为空返回True,不为空返回Falsereturn ps->top == 0;
}
栈的销毁
void STDestroy(ST* ps)
{//判断穿的指针是否有效assert(ps);//先释放，后置空free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}

 

Test.c：栈的测试

int main()
{ST st;//初始化STInit(&st);//压入STPush(&st, 1);//1STPush(&st, 2);//1 2 STPush(&st, 3);//1 2 3 STPush(&st, 4);//1 2 3 4//取栈顶元素int top = STTPop(&st);//4//printf("%d ", top);//4//弹出STPop(&st);//1 2 3//压入STPush(&st, 5);//1 2 3 5 STPush(&st, 6);//1 2 3 5 6while (!STEmpty(&st))//栈不为空{int top = STTPop(&st);//6 5 3 2 1printf("%d ", top);	  //6 5 3 2 1STPop(&st);}//摧毁STDestroy(&st);return 0;
}

 

队列

引入

 

介绍

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

为什么队列选择链表而不用数组？ 

由于队列需要在队列两端进行插入或删除，因此我们优先选择链表来进行实现。当然使用数组实现也可以，只是数组在头部插入和删除元素需要O(n)的时间复杂度，因此选择链表更优。 

 

队列实现

Queue.h：结构体，队列的声明和定义

#pragma once#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QueDatatype;
typedef struct QueueNode
{int val;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Que;//队列初始化
void QueueInit(Que* pq);
//队列销毁
void QueueDestroy(Que* pq);// 队尾入队列
void QueuePush(Que* pq, QueDatatype x);
// 队头出队列
void QueuePop(Que* pq);
//获取队列头部元素
QueDatatype QueueFront(Que* pq);
//获取队列尾部元素
QueDatatype QueueBack(Que* pq);
//判断队列中有效元素
bool QueueEmpty(Que* pq);
//队列中有效元素个数
int QueueSize(Que* pq);

 

Queue.c：队列函数具体实现

队列初始化
void QueueInit(Que* pq)
{assert(pq);//一开始队列为空pq->phead = NULL;pq->ptail = NULL;pq->size = 0;     //队列大小
}
队尾入队列（数据）
void QueuePush(Que* pq, QueDatatype x)
{assert(pq);//扩容QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc");return;}//给值newnode->val = x;newnode->next = NULL;//队列不止一个元素if (pq->ptail){pq->ptail->next = newnode;pq->ptail = newnode;}//队列只有一个元素else{pq->phead = pq->ptail = newnode;}pq->size++;
}
队头出队列（数据）
void QueuePop(Que* pq)
{assert(pq);assert(pq->phead);//队列中不止一个元素if (pq->phead->next == NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}//队列中只有一个元素else{//先记录队头的下一个元素QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}
获取队列头部元素
QueDatatype QueueFront(Que* pq)
{assert(pq);//判断队列是否为空assert(pq->phead);return pq->phead->val;
}
获取队列尾部元素
QueDatatype QueueBack(Que* pq)
{assert(pq);//判断队列是否为空assert(pq->ptail);return pq->ptail->val;
}
判断队列是否为空
bool QueueEmpty(Que* pq)
{assert(pq);//为空返回True，不为空返回Falsereturn pq->size == 0;
}
队列中有效元素个数
int QueueSize(Que* pq)
{assert(pq);return pq->size;//队列大小
}
队列销毁
void QueueDestroy(Que* pq)
{assert(pq);QNode* cur = pq->phead;//依次释放节点while (cur){QNode* next = cur->next;free(cur);cur = next;}//置为空pq->phead = pq->ptail = NULL;pq->size = 0;
}

 

Test.c：队列的测试

#include"Queue.h"int main()
{Que q;//初始化QueueInit(&q);//队尾进入队列QueuePush(&q, 1);//1QueuePush(&q, 2);//1 2QueuePush(&q, 3);//1 2 3QueuePush(&q, 4);//1 2 3 4printf("%d ", QueueFront(&q));//1printf("%d ", QueueBack(&q));//4//对头出队列QueuePop(&q);//2 3 4printf("%d ", QueueFront(&q));//2printf("%d ", QueueBack(&q));//4printf("%d", QueueSize(&q));//3//while (!QueueEmpty(&q))//{//	printf("%d ", QueueFront(&q));//	QueuePop(&q);//}//销毁QueueDestroy(&q);return 0;
}

 

***********************************************************分割线*****************************************************************************
完结！！！
感谢浏览和阅读。
等等等等一下，分享最近喜欢的一句话:

“没有永恒的梅雨季，只有久违的艳阳天”。

我是白子寰，如果你喜欢我的作品，不妨你留个点赞+关注让我知道你曾来过。
你的点赞和关注是我持续写作的动力！！！ 
好了划走吧。


http://www.ppmy.cn/server/4907.html

相关文章

Vue的项目文件夹中的＜router＞指的是什么

Vue的项目文件夹中的＜router＞指的是什么

在Vue框架搭建的项目中&#xff0c;前端路由主要指的是基于HTML5的history模式或hash模式来实现在不刷新页面的情况下进行页面之间的跳转。这是单页应用&#xff08;SPA, Single Page Application&#xff09;中的一个核心概念。 具体来说&#xff0c;前端路由允许我们在不重新…
阅读更多...
jvm概述

jvm概述

JVM&#xff08;Java Virtual Machine&#xff0c;Java虚拟机&#xff09;是Java程序运行的核心组件&#xff0c;它是一个运行时环境&#xff0c;负责将Java字节码&#xff08;bytecode&#xff09;转换为机器码并执行。JVM是平台相关的&#xff0c;这意味着不同的操作系统需要…
阅读更多...
几款AI语音克隆使用分享(未完成)

几款AI语音克隆使用分享(未完成)

近期在看AI语音克隆&#xff0c;发现很多的语音克隆对于原始的音频或者朗读者要求过高&#xff0c;不知各位懂的有没有能给推荐个靠谱的。 1、剪映 语音克隆&#xff0c;2个字1积分&#xff0c;600积分6元。贵&#xff0c;多充并没有优惠。 声音相似度高&#xff0c;但是&#…
阅读更多...
什么是IIoT?

什么是IIoT?

什么是IIoT? IIoT，即工业物联网（Industrial Internet of Things），是指将物联网技术应用到工业领域，通过微型低成本传感器、高带宽无线网络等技术手段，实现工业设备、系统和服务的互联互通，从而提高生产效率、降低能耗和成本，实现智能化和自动化生产。 IIoT的应用范围…
阅读更多...
5_vscode+valgrind+gdb调试程序

5_vscode+valgrind+gdb调试程序

需求 项目程序, 读取串口数据, 出现程序崩溃问题valgrind 可以调试定位内存问题: 内存泄漏,非法地址访问,越界访问等内存问题vscode gdb 可视化调试效果, 比命令行简单快捷很多期望使用vscode valgrind gdb 调试程序内存异常, 崩溃退出的问题 环境准备 sudo apt install v…
阅读更多...
面试经典150题——H指数

面试经典150题——H指数

面试经典150题 day11 题目来源我的题解方法一 排序从后往前遍历方法二 计数排序后缀和方法三 排序从左到右遍历 题目来源 力扣每日一题&#xff1b;题序&#xff1a;274 我的题解 方法一 排序从后往前遍历 先将数组升序排序&#xff0c;然后h从n到0开始遍历&#xff0c;计算…
阅读更多...
2024-04-14 问AI: 在深度学习中，为什么需要激活函数？

2024-04-14 问AI: 在深度学习中，为什么需要激活函数？

文心一言 在深度学习中&#xff0c;激活函数起着至关重要的作用&#xff0c;主要有以下几个原因&#xff1a; 引入非线性特性&#xff1a;深度学习的目标之一是模拟人脑的复杂功能和决策过程。然而&#xff0c;线性模型的组合仍然是线性的&#xff0c;这限制了模型的表示能力…
阅读更多...
Linux的学习之路：9、冯诺依曼与进程（1）

Linux的学习之路：9、冯诺依曼与进程（1）

摘要 本章主要是说一下冯诺依曼体系结构和进程的一部分东西。 目录 摘要 一、冯诺依曼体系结构 二、操作系统的概念 三、设计OS的目的 四、管理 五、进程的基本概念 六、PCB 七、在Linux环境下查看进程 八、使用代码创建进程 九、思维导图 一、冯诺依曼体系结构 如…
阅读更多...
最新文章

Copyright @ 2022~2023