当前位置: 首页 > news >正文

【数据结构】栈和队列(笔记总结)

在这里插入图片描述

👦个人主页:@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 newnodepq->tail->next = newnode;pq->tail = newnode; //更新tail}//尾插后size个数+1pq->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;}//删掉一个元素,队列的个数就要减1pq->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;
}

相关文章:

【数据结构】栈和队列(笔记总结)

👦个人主页:Weraphael ✍🏻作者简介:目前学习C和算法 ✈️专栏:数据结构 🐋 希望大家多多支持,咱一起进步!😁 如果文章对你有帮助的话 欢迎 评论💬 点赞&…...

【Java】自定义注解和AOP切面的使用

前言 我们在开发的过程中,一般都需要对方法的入参进行打印,或者Debug调试的时候我们要查看方法入参的参数是否数量和数据正确性。 一般我们需要知道请求的参数、接口路径、请求ip等 但是考虑以后项目上线BUG排查的问题,最好的方式就是使用…...

前后台协议联调拦截器

前后台协议联调&拦截器4,前后台协议联调4.1 环境准备4.2 列表功能4.3 添加功能4.4 添加功能状态处理4.5 修改功能4.6 删除功能5,拦截器5.1 拦截器概念5.2 拦截器入门案例5.2.1 环境准备5.2.2 拦截器开发步骤1:创建拦截器类步骤2:配置拦截器类步骤3:S…...

【还在传统绑骨骼动画?】让AI助力你实现2D游戏角色动画流程

思路(让3D模型替代动作) 一、利用MJ或者SD生成你需要的游戏角色(获取原图像) 需要的知识: 会调关键词chatGpt(看小红书、抖音、B站、Youtube、Telegrame等等都行,别傻忽忽跑到知识星球被收割…...

动态规划+例题

适用场景 题目链接&#xff1a;数字三角形 /*正推DP&#xff0c;可能数据比较小&#xff0c;这个正推不太麻烦可以AC*/ #include<bits/stdc.h> using namespace std; int r; int a[1005][1005],f[1005][1005];int main(){cin>>r;for(int i1;i<r;i){for(int j1…...

快商通荣获多个政府科技、人才奖项

近日&#xff0c;快商通与快商通首席科学家李海洲教授荣获由厦门市科学技术局、厦门市委人才办等多部门发布的“2022年度厦门市科学技术奖”、“2022厦门十大成长性人才企业”、“2022厦门战略性新兴产业十大创新人才”等多个 政府科技、人才奖项 &#xff0c;并进行全网公示。…...

Linux的基本命令的使用

文章目录一、初识LinuxLinux目录结构二、如何拥有一个Linux环境&#xff1f;三、Linux命名Linux命令基础lscd pwd特殊路径符clearmkdirtouch cat morecp mv rmsuwhich findgrep wc 管道符ehco tail 重定向符psnetstatvi vim一、初识Linux 我们的计算机由硬件和软件两部分组成&…...

RecycleView小结

RecycleView四级缓存 一级缓存&#xff1a;用于存放当前屏幕可显示区域的ViewHolder&#xff0c;目的是为了方便更新数据&#xff0c;以及对View操作时更加快捷二级缓存&#xff1a;用于缓存最近滑动出屏幕的ViewHolder&#xff0c;目的是为了当用户将该View滑出屏幕外时又突然…...

【Python】如何实现Redis构造简易客户端(教程在这)

文章目录前言一、准备二、原理剖析三、编写简易Redis客户端总结前言 Redis 是我们在开发过程中经常会用到的内存数据库&#xff0c;尤其是在Python的第三方模块Redis-py的支持下&#xff0c;在Python中使用Redis及其方便。 但是在有些情况下&#xff0c;我们无法使用像Redis-…...

326. 3 的幂 ——【Leetcode每日一题】

326. 3 的幂 给定一个整数&#xff0c;写一个函数来判断它是否是 3 的幂次方。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 整数 n 是 3 的幂次方需满足&#xff1a;存在整数 x 使得 n3xn 3^xn3x。 示例 1&#xff1a; 输入&#xff1a;n 27 …...

UE4 Sequence学习

1.常用轨道 1.1 Camera轨道 Camera轨道可以理解为Camera Cuts轨道和Camera Actor轨道&#xff0c;一般点击Sequencer上的摄像机图标可以自动创建&#xff1a; Camera Cuts轨道&#xff0c;可以进行不同相机机位的切换&#xff0c;一般会随着Camera Actor轨道自动创建&#x…...

总结MySQL、Redis的优化措施与使用 mysql_upgrade升级数据结构

目录 一.MySQL数据库优化 二.Redis优化 三.MySQL创建测试账号报错 一.MySQL数据库优化 遵循MySQL层优化的五个原则: 减少数据访问&#xff0c;返回更少的数据&#xff0c;减少交互次数减少服务器CPU开销&#xff0c;利用更多资源。理解SQL优化原理并进行SQL优化&#xff0c…...

C++11线程库

C11线程库 本质是对不同平台的线程库进行封装。因为windows和linux下各有自己的接口&#xff0c;这使得代码的可移植性比较差。C11中最重要的特性就是对线程进行支持了&#xff0c;使得C在并行编程时不需要依赖第三方库&#xff0c;而且在原子操作中还引入了原子类的概念。要使…...

智能化生产,提高效率!使用关键词采集工具助力企业数字化转型

关键词采集工具在企业数字化转型中的优势和作用进行阐述。 随着信息技术的不断发展&#xff0c;企业数字化转型已经成为了企业发展的必然趋势。 对于各种规模的企业而言&#xff0c;数字化转型可以提升企业的生产效率、降低成本、提高产品质量等方面带来更多的发展机遇。 而关…...

浅谈自动化测试用例创建和文档

通过自动创建测试用例和文档&#xff0c;探索自然语言处理 (NLP) 在革新软件测试方面的变革力量。 技术的快速发展导致对高效和有效的软件测试方法的需求增加。该领域最有前途的进步之一是自然语言处理 (NLP) 技术的集成。NLP 是人工智能(AI)的一个子集&#xff0c;专注于通过…...

[Java Web]AJAX Axios | 一种结合HTML来取代传统JSP的技术

⭐作者介绍&#xff1a;大二本科网络工程专业在读&#xff0c;持续学习Java&#xff0c;努力输出优质文章 ⭐作者主页&#xff1a;逐梦苍穹 ⭐所属专栏&#xff1a;Java Web 目录1、AJAX1.1、简介1.2、作用1.3、同步和异步1.4、代码实现1.4.1、服务端1.4.2、客户端1.4.2.1、完善…...

【C++】多态问答题

前言 本篇仅整理一些比较偏的多态的问答题 文章目录前言一. 内联与虚函数二. 静态函数与虚函数三. 构造函数与虚函数四. 虚函数与普通函数结束语一. 内联与虚函数 内联函数可以是虚函数吗&#xff1f; 首先我们看一下语法有没有问题 我们看到&#xff0c;程序成功运行了&#…...

【设计模式】适配器模式

一&#xff0c;定义适配器模式&#xff1a;结构型模式之一&#xff0c;适配器提供客户类需要的接口&#xff0c;适配器的实现就是把客户类的请求转化为对适配者的相应接口的调用。也就是说:当客户类调用适配器的方法时&#xff0c;在适配器类的内部将调用适配者类的方法&#x…...

跨域之CorsFilter

跨域之CorsFilter CorsFilter 是 Spring 框架提供的一个用于处理跨域请求的过滤器。在开发中&#xff0c;我们常常需要处理前端发来的跨域请求&#xff0c;CorsFilter 就可以帮助我们实现这一功能。 CorsFilter 主要用于设置跨域请求的响应头&#xff0c;以允许跨域请求能够被…...

STM32基于HAL工程读取DS1302时间数据

STM32基于HAL工程读取DS1302时间数据✨申明&#xff1a;本文章仅发表在CSDN网站&#xff0c;任何其他网站&#xff0c;未注明来源&#xff0c;见此内容均为盗链和爬取&#xff0c;请多多尊重和支持原创!&#x1f341;对于文中所提供的相关资源链接将作不定期更换。&#x1f4cc…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...