【数据结构】栈和队列（笔记总结）

在这里插入图片描述

👦个人主页：@Weraphael
✍🏻作者简介：目前学习C++和算法
✈️专栏：数据结构
🐋 希望大家多多支持，咱一起进步！😁
如果文章对你有帮助的话
欢迎 评论💬 点赞👍🏻 收藏 📂 加关注✨

【本章内容】

在这里插入图片描述

目录

  • 一、栈
      • 1.1 概念
      • 1.2 栈的结构
      • 1.3 准备工作
      • 1.4 常见接口
      • 1.5 代码实现之栈的初始化
      • 1.6 代码实现之栈的销毁
      • 1.7 代码实现之栈的尾插
      • 1.8 代码实现之栈的尾删
      • 1.9 代码实现之栈的大小
      • 1.9 代码实现之判断栈是否为空
      • 1.10 代码实现之返回栈顶元素
      • 1.11 test.c
  • 二、队列
      • 2.1 概念
      • 2.2 队列的结构
      • 2.3 准备工作
      • 1.4 常见接口
      • 1.5 队列之头尾指针初始化
      • 1.5 队列之内存空间的销毁
      • 1.6 队列之尾插
      • 1.7 队列之头删
      • 1.8 队列之求队列大小
      • 1.9 队列之判断队列是否为空
      • 1.10 队列之求队头元素
      • 1.11 队列之求队尾元素
      • 1.12 test.c部分

一、栈

1.1 概念

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

1.2 栈的结构

栈的实现既可以使用顺序表实现，也可以用链表实现。但是，栈使用顺序表实现会比链表实现更有优势。因为栈是后进（栈顶进）的先出（栈顶出），实现一个栈需要尾插和尾删，而顺序表的尾插和尾删效率高，它的时间复杂度都是O(1)，而单链表的尾插和尾删比顺序表低，它的时间复杂度是O(n)
对于顺序表大家可以看看这边博客 —> 点击跳转

【结构】

typedef struct Stack
{
	int* a;  	//指向动态开辟的数组
	int top; 	//表示栈顶
	int capacity;//容量空间的大小
}Stack;

1.3 准备工作

为了方便管理，我们可以创建多个文件来实现
test.c - 测试代码逻辑 （源文件）
stack.c - 动态的实现 （源文件）
stack.h - 存放函数的声明 （头文件）
在这里插入图片描述

1.4 常见接口

【stack.h】

typedef struct Stack
{
	int* a;
	int top;
	int capacity;
}Stack;

//栈的初始化
void STInit(Stack* ps);

//栈的销毁
void STDestroy(Stack* ps);

//栈的尾插
void STPush(Stack* ps, int x);

//栈的尾删
void STPop(Stack* ps);

//栈的大小
int STSize(Stack* ps);

//栈是否为空
bool STEmpty(Stack* ps);

//栈顶元素
int STTop(Stack* ps);

1.5 代码实现之栈的初始化

【stack.c】

//栈的初始化
void STInit(Stack* ps)
{
	assert(ps);
	ps->a = (int*)malloc(sizeof(int) * 4);
	if (ps->a == NULL)
	{
		perror("ps->a :: malloc");
		return;
	}
	ps->top = 0;
	ps->capacity = 4;
}
  • 详细细节参考这篇博客： 点击跳转

1.6 代码实现之栈的销毁

【stack.c】

//栈的销毁
void STDestroy(Stack* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;

	ps->capacity = 0;
	ps->top = 0;
}
  • 详细细节参考这篇博客： 点击跳转

1.7 代码实现之栈的尾插

【stack.c】

//栈的尾插
void STPush(Stack* ps, int x)
{
	assert(ps);
	//判断是否需要扩容
	if (ps->top == ps->capacity)
	{
		int* tmp = (int*)realloc(ps->a, sizeof(int) * ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("tmp :: realloc");
			return;
		}
		ps->capacity *= 2;
		ps->a = tmp;
		tmp = NULL;
	}
	//尾插
	ps->a[ps->top] = x;
	ps->top++;
}
  • 详细细节参考这篇博客： 点击跳转

1.8 代码实现之栈的尾删

【stack.c】

//栈的尾删
void STPop(Stack* ps)
{
	assert(ps);
	//特判顺序表为空的情况
	assert(!STEmpty(ps));

	ps->top--;
}
  • 详细细节参考这篇博客： 点击跳转

1.9 代码实现之栈的大小

【stack.c】

//栈的大小
int STSize(Stack* ps)
{
	assert(ps);

	return ps->top;
}

【学习笔记】
一开始初始化栈顶top为 0，表示栈尾插后，top会指向栈顶的下一个元素。因此top就代表整个栈的大小。

1.9 代码实现之判断栈是否为空

【stack.c】

//栈是否为空
bool STEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

1.10 代码实现之返回栈顶元素

【stack.c】

//栈顶元素
int STTop(Stack* ps)
{
	assert(ps);
	//当ps->top 为 0时，会导致越界
	assert(ps->top != 0);//assert(!STEmpty(ps));
	
	return ps->a[ps->top - 1];
}

1.11 test.c

#include "stack.h"

int main()
{
	Stack st;
	STInit(&st);

	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	
	//注意：栈不能直接打印，因为它在途中出数据
	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st);
	}

	STDestroy(&st);

	return 0;
}

二、队列

2.1 概念

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

在这里插入图片描述

2.2 队列的结构

首先队列也可以用顺序表和链表的结构实现，但是，使用链表实现会更优一些，为什么呢？

答：首先队列是先进先出的，并且它需要尾插和头删。所以，对于顺序表来说，尾删是比单链表快很多，但其头删却要移动整个数据，就显得非常麻烦。而对于单链表来说，头删是非常easy的，而尾插需要遍历，时间复杂度是O（n）

【结构】

typedef struct QNode
{
	struct QNode* next;
	int data;
}QNode;


typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

大家可能会有点奇怪，为什么在单链表章节不定义一个首尾指针结构体？
答案是：因为队列需要尾插而不需要尾删，什么意思呢？对于普通单链表来说，在尾删之前是需要记录尾节点的前一个节点的，即使在单链表上定义一个首尾指针结构体，但时候尾删还是得遍历一遍链表来找到尾节点的前一个结点，因此普通单链表再定义一个首尾指针结构体有点白费力气，而队列不同，它只进行头删和尾插的操作。

2.3 准备工作

为了方便管理，我们可以创建多个文件来实现
test.c - 测试代码逻辑 （源文件）
Queue.c - 动态的实现 （源文件）
Queue.h - 存放函数的声明 （头文件）
在这里插入图片描述

1.4 常见接口

【Queue.h】

typedef struct QNode
{
	struct QNode* next;
	int data;
}QNode;


typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size; // 队列大小
}Queue;

//头指针和尾指针的初始化
void QueueInit(Queue* pq);

//开辟内存空间的销毁
void QueueDestroy(Queue* pq);

//队列的尾插
void QueuePush(Queue* pq, int x);

//队列的头删
void QueuePop(Queue* pq);

//队列的大小
int QueueSize(Queue* pq);

//判断队列是否为空
bool QueueEmpty(Queue* pq);

//队头数据
int QueueFront(Queue* pq);

//队尾数据
int QueueBack(Queue* pq);

1.5 队列之头尾指针初始化

//头指针和尾指针的初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

【笔记总结】

  1. 断言问题。pq是一个结构体指针，指向一个首尾指针的结构体，pq指向NULL，这个队列就没法玩了
    在这里插入图片描述

1.5 队列之内存空间的销毁

//开辟内存空间的销毁
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		//在删除当前节点前记录下一个节点
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

1.6 队列之尾插

//队列的尾插
void QueuePush(Queue* pq, int x)
{
	assert(pq);
	//尾插的第一步，先向内存申请空间
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("newnode :: malloc");
		return;
	}
	//再对newnode初始化
	newnode->data = x;
	newnode->next = NULL;

	//接下来开始尾插
	//第一个问题：当前的链表可能为空
	if (pq->head == NULL)
	{
		//在链表为空的情况下tail，也一定为空（特判）
		//若tail不为空就是传错了
		assert(pq->tail == NULL);
		//直接赋值即可
		pq->head = pq->tail = newnode;
	}
	//否则就是正常的尾插
	else
	{
		//tail newnode
		pq->tail->next = newnode;
		pq->tail = newnode; //更新tail
	}
	//尾插后size个数+1
	pq->size++;
}

1.7 队列之头删

//队列的头删
void QueuePop(Queue* pq)
{
	assert(pq);
	//空链表是不能头删的
	assert(pq->head != NULL);
	
	//头删的特殊情况：链表中只有一个节点
	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;
	}
	//删掉一个元素，队列的个数就要减1
	pq->size--;
}

1.8 队列之求队列大小

//队列的大小
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

1.9 队列之判断队列是否为空

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

1.10 队列之求队头元素

//队头数据
int QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

1.11 队列之求队尾元素

//队尾数据
int QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

1.12 test.c部分

#include "Queue.h"

int main()
{
	Queue node;
	QueueInit(&node);

	//入队列（尾插）
	QueuePush(&node, 1);
	QueuePush(&node, 2);
	QueuePush(&node, 3);
	QueuePush(&node, 4);

	//注意：队列不能直接打印，因为它在途中出数据
	while (!QueueEmpty(&node))
	{
		printf("%d ", QueueFront(&node));
		QueuePop(&node);
	}
	printf("\n");

	QueueDestroy(&node);
	return 0;
}

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

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

相关文章

DC-1渗透实战

DC-1渗透实战

目标机：192.168.26.161 攻击机：192.168.26.144 1、信息收集： 使用ARP扫描，获得信息： arp-scan -l 适应NMAP进行扫描IP为192.168.26.161 ，看他开启了哪些端口、服务和操作系统： nmap -A -T…
阅读更多...
SQL函数

SQL函数

文章目录一、SQL 函数二、SQL COUNT() 函数三、SQL FIRST() 函数四、SQL LAST() 函数五、SQL MAX() 函数总结一、SQL 函数 SQL 拥有很多可用于计数和计算的内建函数。 SQL Aggregate 函数 SQL Aggregate 函数计算从列中取得的值，返回一个单一的值。 有用的 Aggrega…
阅读更多...
「程序员值得一看」| 传说中的“全球公认最健康的作息时间表”

「程序员值得一看」| 传说中的“全球公认最健康的作息时间表”

身体是革命的本钱，健康问题关乎我们每一个人，说到健康作息，下面这篇文章还是非常值得我们参考的，当然每个人结合自身可以好好总结一下。 都说程序员这一行，猝死概率极高，究其原因还是很难有很好的作息规律…
阅读更多...
【Matlab算法】粒子群算法求解二维线性优化问题（附MATLAB代码）

【Matlab算法】粒子群算法求解二维线性优化问题（附MATLAB代码）

MATLAB求解二维线性优化问题前言正文函数实现可视化结果前言 二维线性优化问题指的是在二维空间中，对于一个由线性函数构成的目标函数，通过限制自变量的范围或满足特定的约束条件，寻找一个最优解（最小值或最大值）。这…
阅读更多...
面试官 ： 你了解的MySQL 集群高可用架构都有哪些？

面试官 ： 你了解的MySQL 集群高可用架构都有哪些？

文章目录 MySQL 主从架构MySQL+DRDB 架构MySQL+MHA 架构MySQL+MMM 架构MySQL 主从架构 此种架构，一般初创企业比较常用，也便于后面步步的扩展 此架构特点： 1、成本低，布署快速、方便 2、读写分离 3、还能通过及时增加从库来减少读库压力 4、主库单点故障 5、数据一致性问题…
阅读更多...
Windows上提示 api-ms-win-core-path-l1-1-0.dll 丢失怎么办？

Windows上提示 api-ms-win-core-path-l1-1-0.dll 丢失怎么办？

Windows上提示 api-ms-win-core-path-l1-1-0.dll 丢失怎么办？最近有用户在开启电脑的photoshop软件使用的时候，出现另外无法启动软件的情况，因为系统中缺失了对应的dll文件。那么这个情况怎么去进行问题的解决呢？来看看以下的解决…
阅读更多...
PyTorch深度学习实战 | 基于YOLO V3的安全帽佩戴检测

PyTorch深度学习实战 | 基于YOLO V3的安全帽佩戴检测

本期将提供一个利用深度学习检测是否佩戴安全帽的案例，从而展示计算机视觉中的目标识别问题的一般流程。目标检测是基于图片分类的计算机视觉任务，既包含了分类，又包含了定位。给出一张图片，目标检测系统要能够识别出图片的目标并给出其位置。由于图片中目标数是不确定的，…
阅读更多...
JUC并发编程第一章之进程/并发/异步的概念[理解基本概念]

JUC并发编程第一章之进程/并发/异步的概念[理解基本概念]

1. 进程和线程的概念 进程: 系统正在运行的一个应用程序;程序一旦运行就是一个进程;进程是资源分配的最小单位 线程: 是进程的实际运行单位;一个人进程可以并发控制多个线程,每条线程并行执行不同的任务 区别: 进程基本上相互独立的;而线程存在于进程内，是进程…
阅读更多...
类ChatGPT项目的部署与微调(上)：从LLaMA到Alpaca、Vicuna、BELLE

类ChatGPT项目的部署与微调(上)：从LLaMA到Alpaca、Vicuna、BELLE

前言 近期，除了研究ChatGPT背后的各种技术细节 不断看论文(至少100篇，100篇目录见此：ChatGPT相关技术必读论文100篇)，还开始研究一系列开源模型(包括各自对应的模型架构、训练方法、训练数据、本地私有化部署、硬件配置要求、微…
阅读更多...
如何把多个文件（夹）随机复制到多个文件夹中

如何把多个文件（夹）随机复制到多个文件夹中

首先，需要用到的这个工具： 百度 密码：qwu2 蓝奏云 密码：2r1z 先看文件的情况一共20个兔兔的图片，4个文件夹，把全部的图片随机的复制这些地方去 打开工具，切换到 文件批量复制 版块 找到右下角…
阅读更多...
Java EE企业级应用开发(SSM)第3章

Java EE企业级应用开发(SSM)第3章

第3章Spring Bean装配一.预习笔记 1.Spring中的Bean 在Spring中，一切Java类都被视为资源，而这些资源都被视为Bean，而Spring就是管理这些Bean的容器。 Bean的配置有3种方式，分别是XML文件配置、Java类和注解 2.基于XML的Bean装…
阅读更多...
`Caché/IRIS` 代码优化效率提升十一条 - 持续更新

`Caché/IRIS` 代码优化效率提升十一条 - 持续更新

文章目录Cach/IRIS代码优化效率提升十一条 - 持续更新 汇总数据使用多维数组Global取数据时需将Global先赋值变量将表达式直接返回使用块语法的运行效率要比点语法更快复杂的if逻辑条件，可以调整顺序，让程序更高效在循环中取不变的配置时，应使…
阅读更多...
SpringRetry接口异常优雅重试机制

SpringRetry接口异常优雅重试机制

场景&#xff1a; 某些场景下&#xff0c;如果接口出现异常需要进行重试&#xff0c;例如网络抖动、调用接口超时等并非接口代码导致的报错&#xff0c;此时可以进行接口重试机制 1、导入 spring retry 重试依赖 <!-- spring retry --><dependency><groupId>…
阅读更多...
【Node.js】Express框架的基本使用

【Node.js】Express框架的基本使用

✍️ 作者简介: 前端新手学习中。 &#x1f482; 作者主页: 作者主页查看更多前端教学 &#x1f393; 专栏分享&#xff1a;css重难点教学 Node.js教学 从头开始学习 目录 初识Express Express简介 什么是Express 进一步理解 Express Express能做什么 Express的基本使用 …
阅读更多...
分享：如何给 DBA 减负？

分享：如何给 DBA 减负？

欢迎访问 OceanBase 官网获取更多信息&#xff1a;https://www.oceanbase.com/ 本文来自OceanBase社区分享&#xff0c;仅限交流探讨。原作者肖杨&#xff0c;OceanBase 软件开发工程师。 研发、数据分析师及运维内部人员有数据查询、数据订正等需求&#xff0c;若无管控平台&…
阅读更多...
Midjourney 使用总结

Midjourney 使用总结

1.关键词提问 中国古典女性&#xff0c;东方美女极致面容站在运河码头遥望丈夫&#xff0c;史诗奇幻场景风格&#xff0c;深绿浅棕&#xff0c;细节风帆&#xff0c;柔焦&#xff0c;人像隐喻&#xff0c;4K&#xff0c;电影级高品质照片&#xff0c;全景图&#xff0c; 焦距 …
阅读更多...
突破市场壁垒：如何利用关键词采集和市场调查找到你的细分市场？

突破市场壁垒：如何利用关键词采集和市场调查找到你的细分市场？

在市场竞争日益激烈的今天&#xff0c;寻找一个适合自己的细分市场成为了每个企业和创业者的必要之举。然而&#xff0c;许多人在寻找细分市场时陷入了困境&#xff0c;不知道如何找到一个符合自己产品的市场&#xff0c;因此&#xff0c;在这种情况下&#xff0c;利用关键词采…
阅读更多...
UVM response_handler和get_response机制

UVM response_handler和get_response机制

很多UVM用户平时更多的使用get_response()方式去获得uvm_driver的response&#xff0c;但get_response有些缺点&#xff1a;由于 get_response() 是一种阻塞方法&#xff0c;它会阻塞直到收到来自 UVM 驱动程序 (put_response()) 的响应。因此&#xff0c;如果我们使用 get_res…
阅读更多...
CleanMyMac X4.20最新mac电脑优化工具好用吗?

CleanMyMac X4.20最新mac电脑优化工具好用吗?

如果你的Mac运行速度变慢&#xff0c;很有可能是因为RAM内存被过度占用了。本文将向Mac用户&#xff0c;尤其是小白用户归纳一些常见的Mac内存清理方法。通过释放RAM内存&#xff0c;你将会看到自己Mac的运行速度有显著提升。 你的Mac运行速度是否变得慢到让人抓狂&#xff1f;…
阅读更多...
项目下载中心-超简单版解决方案

项目下载中心-超简单版解决方案

简单的下载中心的设计流程 直接上设计流程&#xff1a; 以上就是步骤了&#xff0c;至于每个步骤怎么实现&#xff0c;那方法就很多了 &#xff0c;随意&#xff0c;达到目的就行。 至于各种问题&#xff0c;比如队列性能&#xff0c;消息重复或丢失&#xff0c;等等&#…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发