【数据结构】C语言实现:栈(Stack)与队列(Queue)

栈与队列

    • 栈的概念及其结构
      • 栈的顺序结构(杯子)
      • 栈的相关接口
    • 栈的实现
      • 顺序栈
        • 定义栈结构:
        • 头文件 (Stack.h)
        • 初始化 (StackInit)
        • 销毁 (StackDestroy)
        • 压栈 (StackPush)
        • 出栈(StackPop)
        • 读取栈顶元素 (StackTop)
        • 判断空栈(StackEmpty)
        • 栈元素个数(StackSize)
  • 队列
    • 队列的概念及结构
    • 队列的实现
    • 队列的相关接口
    • 队列的实现
        • 队列的定义:
        • 头文件(Queue.h)
        • 初始化(QueueInit)
        • 销毁(QueueDestroy)
        • 入队列(QueuePush)
        • 出队列(QueuePop)
        • 判断队列是否为空(QueueEmpty)
        • 返回队列的结点个数(QueueSize)
        • 队列首结点(QueueFront)
        • 队列尾结点(QueueBack)

栈的概念及其结构

:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。 栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。所以也有被称为后进先出的顺序结构。

压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶
出栈:栈的删除操作叫做出栈。出数据也在栈顶

栈的顺序结构(杯子)

在这里插入图片描述

~~就像上述图片一样,像个”杯子“,只能从上面进出,后进先出;栈底是固定的,无法插入于删除。

栈的相关接口

我们来到cplusplus这个网站,查找库中的栈的接口。(这里我们只讲解C语言的哈,C++涉及的emplace和swap就暂不讲解)
在这里插入图片描述

栈的实现

栈,我们可以用顺序表实现,也可以用链表实现,各有各的优势,接下来我们就具体用C语言代码来实现下顺序栈链栈

顺序栈

顺序栈,也就是用顺序表来实现,顺序表也就是用了数组这一结构。动态内存管理,开辟一个空间大小固定的数组(当然可以扩容)。这一结构地址相连,方便访问。接下来我们先定义一个栈。

定义栈结构:

定义栈分为三部分:动态开辟数组(a)、top下标、容量(capacity)

typedef int STDataType;
//栈的定义
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}S;
头文件 (Stack.h)

我们进行一个简单的分装,把库头文件接口函数声明结构体定义封装到头文件中。

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//定义初始空间大小
#define A_INIT 2
//定义栈元素类型:这里是为了我们的栈更兼容其他类型元素,比如我们现在想变为存储double的栈,只需要在这里把int改成double就可以。
typedef int STDataType;
//栈的定义
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}S;
//初始化栈
void StackInit(S* stack);
//栈的销毁
void StackDestroy(S* stack);
//压栈
void StackPush(S* stack, STDataType x);
//出栈
void StackPop(S* stack);
//读取栈顶元素
STDataType StackTop(S* stack);
//判断是否空栈
bool StackEmpty(S* stack);
//栈的元素个数
int StackSize(S* stack);
初始化 (StackInit)

初始化:我们根据栈结构来初始化,所以也分为三部分:
1.对a,进行空间开辟,用malloc来开辟空间。
2.容量(便于后续扩容操作)
3.top下标。这里我们有两种主流的:初始化为0或者初始化为-1.
(ps:初始化为0,则表示top指向的是栈顶上一个元素,我们访问的时候就需要-1;初始化为-1,则表示top指针指向栈顶元素,直接访问即可。这里我便是采用初始化为-1)

void StackInit(S* stack)
{
	assert(stack);//断言
	stack->a = (STDataType*)malloc(sizeof(STDataType) * A_INIT);
	stack->capacity = A_INIT;
	stack->top = -1;
}
销毁 (StackDestroy)

同上,根据定义来,malloc的动态空间,调用free()函数来释放空间,以防内存泄漏。

void StackDestroy(S* stack)
{
	free(stack->a);
	stack->a = NULL;
	stack->capacity = 0;
	stack->top = -1;
}
压栈 (StackPush)
  • 压栈:只需要把top指针上移,赋值新插入元素即可,也就是对应最后两段代码。
  • ps:但我们插入要考虑我们开辟的容量问题,当容量空间不够我们需要扩容操作。
  • 扩容:调用realloc函数进行空间的扩容。这里也有两个问题:原地扩容和异地扩容,这个详细我们在realloc函数那篇解释。这里影响并不是很大。
void StackPush(S* stack, STDataType x)
{
	//扩容
	assert(stack);
	if (stack->top + 1 == stack->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(stack->a, sizeof(STDataType) * 2 * stack->capacity);
		if (tmp == NULL)//判断是否扩容成功
		{
			perror("realloc error");
			return;
		}
		stack->a = tmp;
		stack->capacity = 2 * stack->capacity;
	}
	stack->top++;
	stack->a[stack->top] = x;
}
出栈(StackPop)

出栈就十分简单,先判断是否为空栈,若不是,只需要收回栈顶访问权,让栈顶指针指向下一个位置。

void StackPop(S* stack)
{
	assert(stack);
	assert(stack->top != -1);

	stack->top--;
}
读取栈顶元素 (StackTop)

这里值得注意的是top的初始化是0还是-1问题。

STDataType StackTop(S* stack)
{
	assert(stack);
	assert(stack->top + 1 != 0);

	return stack->a[stack->top];
}
判断空栈(StackEmpty)

判断栈顶top是否为默认初始值即可。

bool StackEmpty(S* stack)
{
	assert(stack);

	return stack->top == -1;
}
栈元素个数(StackSize)

这里也是需要注意top初始值问题。

int StackSize(S* stack)
{
	assert(stack);

	return stack->top+1;
}

队列

队列的概念及结构

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)像个管道只允许一个数据通过,所以不能插队,先进先出。
入队列:进行插入操作的一端称为队尾
出队列:进行删除操作的一端称为队头

请添加图片描述

队列的实现

队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。
请添加图片描述

队列的相关接口

我们同样登录cplusplus网站去看下Queue的接口。
在这里插入图片描述

队列的实现

队列的定义:

队列的定义我们采用链表来定义,这里队列整体存在两个指针,和前面的双向循环的链表一样,我们最好把两个外部指针封装一下。
1.队列单独结点的定义有值和next指针。
2.队列整体的话有两个指向队列单独结点的head和tail指针,为了方便我这边也定义了size来定义队列结点个数。

typedef int Datatype;
//定义队列
typedef struct Queue
{
	struct Queue* next; 
	Datatype data;
}qnode;

typedef struct
{
	qnode* head;
	qnode* tail;
	int size;
}queue;

头文件(Queue.h)
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef int Datatype;
//定义队列
typedef struct Queue
{
	struct Queue* next; 
	Datatype data;
}qnode;

typedef struct
{
	qnode* head;
	qnode* tail;
	int size;
}queue;

void QueueInit(queue* pq);
void QueueDestroy(queue* pa);
void QueuePush(queue* pq, Datatype x);
void QueuePop(queue* pq);
bool QueueEmpty(queue* pq);
int QueueSize(queue* pq);
Datatype QueueFront(queue* pq);
Datatype QueueBack(queue* pq);

初始化(QueueInit)

队列的初始化,因为没有结点,直接初始化外部指针即可。

void QueueInit(queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}
销毁(QueueDestroy)

遍历指针,在释放即可。

void QueueDestroy(queue* pq)
{
	assert(pq);
	qnode* cur = pq->head;
	while (cur)
	{
		qnode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = NULL;
	pq->tail = NULL;
}
入队列(QueuePush)

入队列先进先出,单道通行。
1.首先是申请结点空间,然后赋值。
2.如果是队列为空,直接给head和tail指针赋值新节点地址;如果不为空,就赋值给tail的next指针。接在后方。
3.最后size计数,加加即可。

void QueuePush(queue* pq, Datatype x)
{
	qnode* node = (qnode*)malloc(sizeof(qnode));
	if (node == NULL)
	{
		perror("malloc error!");
		return;
	}
	node->next = NULL;
	node->data = x;

	if (pq->head == NULL)
	{
		pq->head = pq->tail = node;
	}
	else
	{
		pq->tail->next = node;
		pq->tail = node;
	}
	pq->size++;
}
出队列(QueuePop)

出队列先入先出
1.注意断言队列是否为空。
2.若队列只有一个结点,直接释放,双指针置空即可;若队列不止一个结点,保存head的next指针,释放head指针,在head指针赋值新的head位置。
3.最后size减减即可。

void QueuePop(queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		qnode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}
判断队列是否为空(QueueEmpty)
bool QueueEmpty(queue* pq)
{
	assert(pq);

	return pq->head == NULL;
}
返回队列的结点个数(QueueSize)

这里直接返回size即可,若前方定义没有加size,就需要遍历计数返回。

int QueueSize(queue* pq)
{
	assert(pq);
	return pq->size;
}
队列首结点(QueueFront)
Datatype QueueFront(queue* pq)
{
	assert(pq);
	return pq->head->data;
}
队列尾结点(QueueBack)
Datatype QueueBack(queue* pq)
{
	assert(pq);
	return pq->tail->data;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/230414.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Github入门教程之高效搜索和查看需要的项目

对咱们新入门的小白来说&#xff0c;前两天手把手注册 Github 账号的任务已经完成&#xff0c;接下来&#xff0c;学习如何高效搜索和查看自己感兴趣的内容。 下面是之前教程传送门 超详细GitHub注册和登录教程-CSDN博客 一. 搜索 可以在页面左上角「Search or jump to ...」…

C语言WFC实现绘制Lagrange插值多项式曲线的函数

前言&#xff08;引用&#xff09;&#xff1a; 拉格朗日多项式插值 插值方法有许多&#xff0c;常用的、基本的有&#xff1a;拉格朗日多项式插值、牛顿插值、分段线插值、Hermite插值和三次样条插值。这里只将一下拉格朗日多项式插值法&#xff1a; 方法应用 通缩点说&…

思维链(CoT)提出者 Jason Wei:关于大语言模型的六个直觉

文章目录 一、前言二、主要内容三、总结 &#x1f349; CSDN 叶庭云&#xff1a;https://yetingyun.blog.csdn.net/ 一、前言 Jason Wei 的主页&#xff1a;https://www.jasonwei.net/ Jason Wei&#xff0c;一位于 2020 年从达特茅斯学院毕业的杰出青年&#xff0c;随后加盟了…

人工智能|深度学习——知识蒸馏

一、引言 1.1 深度学习的优点 特征学习代替特征工程&#xff1a;深度学习通过从数据中自己学习出有效的特征表示&#xff0c;代替以往机器学习中繁琐的人工特征工程过程&#xff0c;举例来说&#xff0c;对于图片的猫狗识别问题&#xff0c;机器学习需要人工的设计、提取出猫的…

STM32F1之CAN介绍

目录 ​编辑 1. CAN 是什么&#xff1f; 2. 总线拓扑图 3. CAN 的特点 4. CAN 协议的基本概念 1. CAN 是什么&#xff1f; CAN 是 Controller Area Network 的缩写&#xff08;以下称为 CAN&#xff09;&#xff0c;是 ISO*1 国际标准化的串行通信协议。 在当前的汽车产…

【LeetCode每日一题合集】2023.11.27-2023.12.3 (⭐)

文章目录 907. 子数组的最小值之和&#xff08;单调栈贡献法&#xff09;1670. 设计前中后队列⭐&#xff08;设计数据结构&#xff09;解法1——双向链表解法2——两个双端队列 2336. 无限集中的最小数字解法1——维护最小变量mn 和 哈希表维护已经去掉的数字解法2——维护原本…

【UE5】监控摄像头效果(上)

目录 效果 步骤 一、视角切换 二、摄像头画面后期处理 三、在场景中显示摄像头画面 效果 步骤 一、视角切换 1. 新建一个Basic关卡&#xff0c;添加第三人称游戏资源到项目浏览器 2. 新建一个Actor蓝图&#xff0c;这里命名为“BP_SecurityCamera” 打开“BP_Securit…

90. 子集 II

90. 子集 II 原题链接&#xff1a;完成情况&#xff1a;解题思路&#xff1a;参考代码&#xff1a;错误经验吸取 原题链接&#xff1a; 90. 子集 II https://leetcode.cn/problems/subsets-ii/description/ 完成情况&#xff1a; 解题思路&#xff1a; /** * 包含重复元素…

图的邻接链表储存

喷了一节课 。。。。。。。、。 #include<stdio.h> #include<stdlib.h> #define MAXNUM 20 //每一个顶点的节点结构&#xff08;单链表&#xff09; typedef struct ANode{ int adjvex;//顶点指向的位置 struct ArcNode *next;//指向下一个顶点 …

.Net6.0 Microsoft.AspNetCore.Http.Abstractions 2.20 已弃用

您想要升级 Microsoft.AspNetCore.Http.Abstractions 包&#xff0c;您需要注意以下几点&#xff1a; Microsoft.AspNetCore.Http.Abstractions 包在 ASP.NET Core 2.2 版本后已经被标记为过时&#xff0c;因为它已经被包含在 Microsoft.AspNetCore.App 框架引用中12。因此&am…

树莓派 5 - Raspberry Pi 5 入门教程

系列文章目录 文章目录 ​​​​​​​ 前言 如果您是第一次使用 Raspberry Pi&#xff0c;请参阅我们的入门指南&#xff08;how to get started&#xff09;。 Raspberry Pi 5 Raspberry Pi 5 配备了运行频率为 2.4GHz 的 64 位四核 Arm Cortex-A76 处理器&#xff0c;CPU 性…

ResNeXt(2017)

文章目录 Abstract1. Introductionformer workour work 2. Related Work多分支卷积网络分组卷积压缩卷积网络Ensembling 3. Method3.1. Template3.2. Revisiting Simple Neurons3.3. Aggregated Transformations3.4. Model Capacity 4. Experiment 原文地址 源代码 Abstract 我…

【二分查找】LeetCode:2354.优质数对的数目

作者推荐 贪心算法LeetCode2071:你可以安排的最多任务数目 本文涉及的基础知识点 二分查找算法合集 题目 给你一个下标从 0 开始的正整数数组 nums 和一个正整数 k 。 如果满足下述条件&#xff0c;则数对 (num1, num2) 是 优质数对 &#xff1a; num1 和 num2 都 在数组 …

VisualStudio反汇编功能使用

VisualStudio反汇编功能使用 使用方法 到达断点时&#xff1a;CtrlK&#xff08;松开&#xff09;G&#xff08;后按&#xff09;唤出反汇编界面&#xff0c;就可以看到当前代码对应的汇编语言了 注意&#xff1a;进入反汇编窗口后可以F10单次调试一条汇编指令 其他&#…

【vscode写vue代码是白色怎么办】

【vscode写vue代码是白色怎么办】 在插件列表中搜索Vetur 安装即可

linux虚拟机Virtualbox的下载安装及vagrant镜像下载安装

Virtualbox下载安装以及创建及简单使用一个虚拟机 1.开启电脑cpu虚拟机 以戴尔G3为例 找到电脑设置–>更新与安全–>恢复 这个步骤也可以在电脑开机时一直按键esc(或者F1、或者F2、或者deleete)都可以进入BIOS 进入BIOS 完成以上步骤就可以开启电脑cpu虚拟机了 …

使用Tomcat部署静态项目并处理BUG

--听讲的习惯 Tomcat介绍 tomcat what_Arenaschi的博客-CSDN博客 Tomcat安装及配置教程&#xff08;超详细&#xff09; 那些年我们用过的tomcat_Arenaschi的博客-CSDN博客 简单使用tomcat查看版本信息等_windows查看tomcat版本命令-CSDN博客 Tomcat部署html静态网站的五种方…

红海云eHR 任意文件上传漏洞复现

0x01 产品简介 红海eHR是大中型企业广泛采用人力资源管理系统。红海云是国内顶尖的HR软件供应商,是新一代eHR系统的领导者。 0x02 漏洞概述 红海云EHR系统PtFjk.mob接口处存在未授权文件上传漏洞,攻击者可上传webshell来命令执行,获取服务器权限。 0x03 复现环境 FOFA:…

Leetcode 17 电话号码的字母组合

理解题意&#xff1a; 给定一个仅包含数字 2-9 的字符串&#xff0c;返回所有它能表示的字母组合 本质上&#xff1a;数字代表着一个字母集合 数字的个数决定了递归的深度&#xff0c;即树的深度 数字代表的字母组合决定了当前树的宽度。 1.暴力回溯 这里没有什么剪枝…

拆解大语言模型 RLHF 中的PPO算法

为什么大多数介绍大语言模型 RLHF 的文章&#xff0c;一讲到 PPO 算法的细节就戛然而止了呢&#xff1f;要么直接略过&#xff0c;要么就只扔出一个 PPO 的链接。然而 LLM x PPO 跟传统的 PPO 还是有些不同的呀。 其实在 ChatGPT 推出后的相当一段时间内&#xff0c;我一直在等…