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

基于c++版本的数据结构改-python栈和队列思维总结

##栈部分-(叠猫猫)

##抽象数据类型栈的定义:是一种遵循先入后出的逻辑的线性数据结构。

换种方式去理解这种数据结构如果我们在一摞盘子中取到下面的盘子,我们首先要把最上面的盘子依次拿走,才可以继续拿下面的盘子,我们把盘子替代成各种类型的元素(如整形,字符,对象等),对于栈就是类似这种衍生出来的线性数据结构。

##栈的定义(c++):是限定仅在表尾进行插入或删除操作的线性表

##图例介绍

##LIFO结构:

##动态过程

##栈的表示和实现

##栈常用操作:pop(),push(),peek()

然而,某些语言可能没有专门提供栈类,这时我们可以将该语言的“数组”或“链表”当作栈来使用,并在程序逻辑上忽略与栈无关的操作。

栈遵循先入后出的原则,我们只能在栈顶添加或删除元素。

但是,数组和链表都可以在任意位置添加和删除元素,所以栈可以看作是一种受限制的数组或链表。

##栈的顺序表示-基于数组的实现

采用具有一块连续存储的地址进行相关操作,具有代表性的便是数组,基于数组的实现栈。

我们可以将数组的尾部视作栈顶,入栈和出栈操作分别对应在数组的尾部添加或者删除元素,时间复杂度都为O(1)。

##图解

##python代码实现

考虑到入栈的元素可能会远远不断的地增加,因此我们可以使用动态数组,这样就可以不用自行处理数组的扩容问题。

在进行代码介绍之前,我们先介绍一下Python中类class基础篇(用简单的话来说,类是一个模板,而实例则是根据类创建的对象)

##Python类的定义与实例的创建

类的创建-类通过 class 关键字定义,类名通用习惯为首字母大写

class Circle(object):#创建Circle类,Circle为类名

        pass#此处可添加属性和方法

实例的创建-创建实例使用 类名+(),类似函数调用的形式创建。

circle1 = Circle()

circle = Circle()

##Python类中的实例属性与类属性

实例属性:用于区分不同的实例

类属性:是每个实例的共有属性

区别:实例属性每个实例都各自拥有,相互独立;而类属性有且只有一份,是共有的属性。

circle1.r = 1#r为实例属性

circle2.R= 2

print(circle.r)#使用 实例名,属性名,可以访问我们的属性

print(circle.R)

在定义 Circle 类时,可以为 Circle 类添加一个特殊的 __init__() 方法,当创建实例时,__init__() 方法被自动调用为创建的实例增加实例属性。

class Circle(object):  # 创建Circle类def __init__(self, r): # 初始化一个属性r(不要忘记self参数,他是类下面所有方法必须的参数)self.r = r  # 表示给我们将要创建的实例赋予属性r赋值
class Circle(object):  # 创建Circle类def __init__(self, R):  # 约定成俗这里应该使用r,它与self.r中的r同名self.r = Rcircle1 = Circle(1)  
print(circle1.r)  #我们访问的是小写r

类属性-实例属性每个实例各自拥有,互相独立,而类属性有且只有一份。

class Circle(object):pi = 3.14  # 类属性def __init__(self, r):self.r = rcircle1 = Circle(1)
circle2 = Circle(2)
print('----未修改前-----')
print('pi=\t', Circle.pi)
print('circle1.pi=\t', circle1.pi)  #  3.14
print('circle2.pi=\t', circle2.pi)  #  3.14
print('----通过类名修改后-----')
Circle.pi = 3.14159  # 通过类名修改类属性,所有实例的类属性被改变
print('pi=\t', Circle.pi)   #  3.14159
print('circle1.pi=\t', circle1.pi)   #  3.14159
print('circle2.pi=\t', circle2.pi)   #  3.14159
print('----通过circle1实例名修改后-----')
circle1.pi=3.14111   # 实际上这里是给circle1创建了一个与类属性同名的实例属性
print('pi=\t', Circle.pi)     #  3.14159
print('circle1.pi=\t', circle1.pi)  # 实例属性的访问优先级比类属性高,所以是3.14111   
print('circle2.pi=\t', circle2.pi)  #  3.14159
print('----删除circle1实例属性pi-----')
----未修改前-----
pi=  3.14
circle1.pi=  3.14
circle2.pi=  3.14
----通过类名修改后-----
pi=  3.14159
circle1.pi=  3.14159
circle2.pi=  3.14159
----通过circle1实例名修改后-----
pi=  3.14159
circle1.pi=  3.14111
circle2.pi=  3.14159

实例属性访问优先级比类属性高

##Python类的实例方法

class Circle(object):pi = 3.14  # 类属性def __init__(self, r):self.r = r  # 实例属性def get_area(self):""" 圆的面积 """# return self.r**2 * Circle.pi # 通过实例修改pi的值对面积无影响,这个pi为类属性的值return self.r**2 * self.pi  # 通过实例修改pi的值对面积我们圆的面积就会改变circle1 = Circle(1)
print(circle1.get_area())  # 调用方法 self不需要传入参数,不要忘记方法后的括号  输出 3.14

##基于数组栈的代码实现

class ArrayStack:"""基于数组实现额栈"""def __init__(self):"""构造方法"""self._stack:list[int] = []def size(self):"""获取栈的长度"""return len(self._stack)def is_empty(self):"""判断栈是否为空"""return self._stack == []def push(self,item):"""入栈"""self._stack.append(item)def pop(self):"""出栈"""if self.is_empty():raise IndexError("栈为空")return self._stack.pop()def peek(self):"""访问栈顶元素"""if self.is_empty():raise IndexError("栈为空")return self._stack[-1]def to_list(self):"""返回列表用于打印"""return self._stack

时间效率:在基于数组的实现中,入栈和出栈操作都在预先分配好的连续内存中进行,具有很好的缓存本地性,因此效率较高。然而,如果入栈时超出数组容量,会触发扩容机制,导致该次入栈操作的时间复杂度变为O(n) 。

空间效率:在初始化列表时,系统会为列表分配“初始容量”,该容量可能超出实际需求;并且,扩容机制通常是按照特定倍率(例如 2 倍)进行扩容的,扩容后的容量也可能超出实际需求。因此,基于数组实现的栈可能造成一定的空间浪费

##栈的链式表示

使用链表实现栈时,我们可以将链表的头结点视为栈顶,尾结点视为栈底。

在进行插入元素的时候我们只需要把结点插入链表的头部,这种方法被称为“头插法”。

在进行删除操作时只需要把头结点删除即可。

##链栈示意图

##图解

##Python链栈代码实现

class ListNode(object):"""定义链表"""def __init__(self):self.val = Noneself.next = Noneclass LinkedListStack:"""基于链表实现的栈"""def __init__(self):"""构造方法"""self._peek:ListNode | None = Noneself._size: int = 0def size(self):"""获取栈的长度"""return self._sizedef is_empty(self):"""判断栈是否为空"""return self._sizedef push(self,val):"""入栈"""node = ListNode(val)node.next = self._peekself._peek = nodeself._size += 1def pop(self):"""出栈"""if self.is_empty():raise  IndexError("栈为空")return self._peek.valdef to_list(self):"""转化为列表用于打印"""arr = []node = self._peekwhile node :arr.append(node.val)node = node.nextarr.reverse()return arr

时间效率:在基于链表的实现中,链表的扩容非常灵活,不存在上述数组扩容时效率降低的问题。但是,入栈操作需要初始化节点对象并修改指针,因此效率相对较低。不过,如果入栈元素本身就是节点对象,那么可以省去初始化步骤,从而提高效率。

空间效率:由于链表节点需要额外存储指针,因此链表节点占用的空间相对较大

##栈典型的用例

浏览器中的后退与前进、软件中的撤销与反撤销。每当我们打开新的网页,浏览器就会对上一个网页执行入栈,这样我们就可以通过后退操作回到上一个网页。后退操作实际上是在执行出栈。如果要同时支持后退和前进,那么需要两个栈来配合实现。

程序内存管理。每次调用函数时,系统都会在栈顶添加一个栈帧,用于记录函数的上下文信息。在递归函数中,向下递推阶段会不断执行入栈操作,而向上回溯阶段则会不断执行出栈操作。

##队列部分-猫猫排队

是一种遵循先入先出规则的线性数据结构。

是一种模拟排队现象,新来的人不断加入到队列尾部,而位于队列头部的人不断离开。

##抽象数据类型队列的定义

队列是一种先进先出的线性表,它只允许在表的一端进行插入,而在另一端删除元素。

##图例显示

我们将队列头部称为“队首”,尾部称为“队尾”,将把元素加入队尾的操作称为“入队”,删除队首元素的操作称为“出队”。

##队列的常用操作

##图解

##基于数组的队列实现

我们在数组中进行删除首元素的时间复杂度为O(n),这就导致了出队的操作效率低下。

采用变量front指向队首元素的索引,rear = front + size ,通过一个变量size来记录队列的长度。

基于此设计,数组中所包含的元素的有效区间为[front,rear - 1]

入队操作:只需要将元素赋值给rear索引处,并将size增加1。

出队操作:只需要将front增加1,并将size减少1。

##问题:

在不断进行入队和出队的过程中,front 和 rear 都在向右移动,当它们到达数组尾部时就无法继续移动了。为了解决此问题,我们可以将数组视为首尾相接的“环形数组”。

对于环形数组,我们需要让 front 或 rear 在越过数组尾部时,直接回到数组头部继续遍历。这种周期性规律可以通过“取余操作”来实现,

##基于数组的队列代码实现

class ArrayQueue:"""基于环形数组实现的队列"""def __init__(self,size):"""构造方法"""self._nums : list[int] = [0] *size #用于存储队列元素的数组self._front : int = 0 #队首指针,指向队首元素self._size : int = 0 #队列长度def capacity(self):"""获取队列的容量"""return  len(self._nums)def size(self):"""获取队列的长度"""return self._sizedef is_empty(self):"""判断队列是否为空"""return  self._size == 0def push(self,num):"""入队操作"""if self._size == self.capacity():raise IndexError("队列已满")#计算尾指针,指向对尾的索引 + 1#通过取余操作,实现rear超过数组尾部后回到头部rear : int = (self._front + self._size) % self.capacity()#将num添加至对尾self._nums[rear] = numself._size += 1def pop(self):"""出队"""num : int = self.peek()#队首指针指向后移动一位,若超过数组尾部后回到头部rear : int = (self._front + self._size) % self.capacity()self._size -= 1return numdef peek(self):"""访问队首元素"""if self.is_empty():raise IndexError("栈为空")return self._nums[self._front]def to_list(self):"""转化成列表用于打印"""res = [0] * self.size()j : int = self._frontfor i in range(self.size()):res[i] = self._nums[(j%self.capacity())]j += 1return  res

时间效率:在基于数组的实现中,入对和出对操作都在预先分配好的连续内存中进行,具有很好的缓存本地性,因此效率较高。然而,如果入对时超出数组容量,会触发扩容机制,导致该次入对操作的时间复杂度变为O(n) 。

空间效率:在初始化列表时,系统会为列表分配“初始容量”,该容量可能超出实际需求;并且,扩容机制通常是按照特定倍率(例如 2 倍)进行扩容的,扩容后的容量也可能超出实际需求。因此,基于数组实现的栈可能造成一定的空间浪费

##基于链表的队列实现

可以将链表的“头节点”和“尾节点”分别视为“队首”和“队尾”,规定队尾仅可添加节点,队首仅可删除节点。

##图解

##基于链表的队列实现代码

class ListNode:"""定义链表"""def __init__(self):self.val = Noneself.next = Noneclass LinkedListQueue:"""基于链表实现的队列"""def __init__(self):"""构造方法"""self._front : ListNode | None = None #头结点frontself._rear: ListNode | None = None  # 尾节点 rearself._size: int = 0def size(self):"""获取队列的长度"""return self._sizedef is_empty(self):"""判断队列是否为空"""return not self._frontdef push(self, num):"""入队"""# 尾节点后添加 numnode = ListNode(num)# 如果队列为空,则令头、尾节点都指向该节点if self._front is None:self._front = nodeself._rear = node# 如果队列不为空,则将该节点添加到尾节点后else:self._rear.next = nodeself._rear = nodeself._size += 1def pop(self) -> int:"""出队"""num = self.peek()# 删除头节点self._front = self._front.nextself._size -= 1return numdef peek(self) -> int:"""访问队首元素"""if self.is_empty():raise IndexError("队列为空")return self._front.valdef to_list(self) -> list[int]:"""转化为列表用于打印"""queue = []temp = self._frontwhile temp:queue.append(temp.val)temp = temp.nextreturn queue

##队列典型应用

淘宝订单。购物者下单后,订单将加入队列中,系统随后会根据顺序处理队列中的订单。在双十一期间,短时间内会产生海量订单,高并发成为工程师们需要重点攻克的问题。

各类待办事项。任何需要实现“先来后到”功能的场景,例如打印机的任务队列、餐厅的出餐队列等,队列在这些场景中可以有效地维护处理顺序。

相关文章:

基于c++版本的数据结构改-python栈和队列思维总结

##栈部分-(叠猫猫) ##抽象数据类型栈的定义:是一种遵循先入后出的逻辑的线性数据结构。 换种方式去理解这种数据结构如果我们在一摞盘子中取到下面的盘子,我们首先要把最上面的盘子依次拿走,才可以继续拿下面的盘子&…...

算法通关村第七关—迭代实现二叉树的遍历(黄金)

迭代实现二叉树的遍历 迭代法实现前序遍历 前序遍历是中左右&#xff0c;如果还有左子树就一直向下找。完了之后再返回从最底层逐步向上向右找。不难写出如下代码&#xff1a;&#xff08;注意代码中&#xff0c;空节点不入栈&#xff09; public List<Integer>preorde…...

Java期末复习题之封装

点击返回标题->23年Java期末复习-CSDN博客 第1题. 定义一个类Person,定义name和age私有属性&#xff0c;定义有参的构造方法对name和age进行初始化。在测试类中创建该类的2个对象&#xff0c;姓名、年龄分别为lili、19和lucy、20&#xff0c;在屏幕打印出2个对象的姓名和年龄…...

湖科大计网:计算机网络概述

一、计算机网络的性能指标 一、速率 有时候数据量也认为是以10为底的&#xff0c;看怎么好算。&#xff08;具体吉大考试用什么待商榷&#xff09; 二、带宽 在模拟信号系统中带宽的含义&#xff0c;本课程中用到的地方是&#xff1a;香农定理和奈奎斯特定理公式的应用之中。 …...

每日一道c语言

任务描述 题目描述:输入10个互不相同的整数并保存在数组中&#xff0c;找到该最大元素并删除它&#xff0c;输出删除后的数组 相关知识&#xff08;略&#xff09; 编程要求 请仔细阅读右侧代码&#xff0c;结合相关知识&#xff0c;在Begin-End区域内进行代码补充&#xf…...

(C)一些题11

1. #include<stdio.h> #include<string.h> void main() { char *s1"ABCDEF"&#xff0c;*s2"aB"&#xff1b; s1; s2; puts(s1)&#xff1b; puts(s2)&#xff1b; printf("%d\n",strcmp(s1,s2))&#xff1b; } 答案&#xff1…...

多级路由component页面不加载

项目基于vue-element-admin 新建SubView.vue <template><router-view /> </template><script setup> </script>在父层添加component {path: /sj,component: Layout,redirect: /sj,name: 三级医院评审标准(2022),meta: {title: 三级医院评审标准(…...

【原创】Mac mini M1安装home-brew

Mac mini M1 所需神器 home-brew 按照官网的脚本无法安装。 无奈&#xff0c;从github下载安装包来安装。 Homebrew 结果&#xff0c;还需要先安装 Xcode command 命令行工具 xcode-select --install安装完了&#xff0c;却无法执行。 修改配置文件 cd vi .zshrc添加如下内…...

【python交互界面】实现动态观察图像在给定HSV范围的区域显示

HSV颜色空间 与RGB颜色空间相比&#xff0c;HSV颜色空间更适合进行颜色分析和提取特定颜色的目标。在HSV空间中&#xff0c;颜色信息被分布在不同的通道上&#xff0c;使我们能够更准确地定义颜色的范围&#xff0c;并使用阈值操作轻松地分离出我们感兴趣的区域部分。 HSV三个通…...

Vue3中定义变量是选择ref还是reactive?

目录 ref和reactive的优势 1. ref 优势&#xff1a; 应用场景&#xff1a; 示例&#xff1a; 2. reactive 优势&#xff1a; 应用场景&#xff1a; 示例&#xff1a; ref和reactive的劣势 1. ref 2. reactive 应用案例 总结 Vue3中定义变量可以选择使用ref或reac…...

数据结构 | 查漏补缺之哈希表、最短路径、二叉树与森林的转换

哈希表是什么&#xff1f; 或者说 设图采用邻接表的存储结构&#xff0c;写对图的删除顶点和删除边的算法步骤 删除边 删除点 最短路径问题 参考博文 迪杰斯特拉(Dijkstra)算法_dijkstra算法-CSDN博客 Dijkstra(迪杰斯特拉&#xff09;算法 定义一个点为源点&#xff0c;算源…...

SpringCloud

五大组件 注册/配置中心 Nacos 、Eureka远程调用 Feign负载均衡 Ribbon服务保护 sentinel&#xff08;实现限流、降级、熔断&#xff09;网关 gateway 注册中心 Eureka 服务注册&#xff1a;服务提供者把自己的信息注册到Eureka&#xff0c;由Eureka来保存这些信息服务发现…...

fastadmin嵌套关联查询,thinkPHP5嵌套关联查询

fastadmin嵌套关联查询 thinkPHP5嵌套关联查询 笔记记录 嵌套关联查询 A -> B -> C A 表关联B表 B表关联C表 同时把A&#xff0f;B&#xff0f;C表相关的数据展现出来 B表的model B表关联C表 我的C表是B表的自身关联。也是一个表&#xff0c;所以为C表 namespace app…...

Power BI - 5分钟学习拆分列

每天5分钟&#xff0c;今天介绍Power BI拆分列功能。 什么是拆分列&#xff1f; 有时导入Power BI的数据表中&#xff0c;某列内容都包含同样的特殊字符如 /&/-/_等&#xff0c;可以利用这个特殊字符进行拆分列的操作&#xff0c;获得我们想要的信息。 操作举例&#xf…...

ELK(四)—els基本操作

目录 elasticsearch基本概念RESTful API创建非结构化索引&#xff08;增&#xff09;创建空索引&#xff08;删&#xff09;删除索引&#xff08;改&#xff09;插入数据&#xff08;改&#xff09;数据更新&#xff08;查&#xff09;搜索数据&#xff08;id&#xff09;&…...

【100天精通Python】Day75:Python机器学习-第一个机器学习小项目_鸾尾花分类项目(上)

目录 1 机器学习中的Helloworld _鸾尾花分类项目 2 导入项目所需类库和鸾尾花数据集 2.1 导入类库 2.2 scikit-learn 库介绍 &#xff08;1&#xff09;主要特点&#xff1a; &#xff08;2&#xff09;常见的子模块&#xff1a; 3 导入鸾尾花数据集 3.1 概述数据 3.…...

gitlab高级功能之容器镜像仓库

今天给大家介绍一个gitlab的高级功能 - Container Registry&#xff0c;该功能可以实现docker镜像的仓库功能&#xff0c;将gitlab上的代码仓的代码通过docker构建后并推入到容器仓库中&#xff0c;好处就是无需再额外部署一套docker仓库。 文章目录 1. 参考文档2. Container R…...

线程的使用(二)

新增实现方式之实现Callable接口 特点 1、可以有返回值。 2、方法可以抛异常。 3、支持泛型的返回值。 4、需借助FutureTask类&#xff0c;比如获取返回值。 步骤 1、创建一个实现Callable接口的实现类。 2、重写call方法&#xff0c; 将此线程需执行的操作声明在call&…...

k8s之镜像拉取时使用secret

k8s之secret使用 一、说明二、secret使用2.1 secret类型2.2 创建secret2.3 配置secret 一、说明 从公司搭建的网站镜像仓库&#xff0c;使用k8s部署服务时拉取镜像失败&#xff0c;显示未授权&#xff1a; 需要在拉取镜像时添加认证信息. 关于secret信息,参考: https://www.…...

mysql面试题——MVCC

一&#xff1a;什么是MVCC&#xff1f; 多版本并发控制&#xff0c;更好的方式去处理读-写冲突&#xff0c;就是为了查询一些正在被另一个事务更新的行&#xff0c;并且可以看到它们被更新之前的值&#xff0c;这样在做查询的时候就不用等待另一个事务释放锁。 二&#xff1a…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

Oracle11g安装包

Oracle 11g安装包 适用于windows系统&#xff0c;64位 下载路径 oracle 11g 安装包...