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

队列和栈的实现

本节讲解的队列与栈,如果你对之前的线性和链式结构顺利掌握了,那么下边的队列和栈就小菜一碟了。因为我们会用前两节讲到的东西来实现队列和栈。 之所以放到一起讲是因为这两个东西很类似,队列是先进先出结构(FIFO, first in first out), 栈是后进先出结构(LIFO, last in first out)。

一,队列

队列(Queue)是计算机科学中一种基础的数据结构,它遵循先进先出(First In First Out, FIFO)的原则,即最早进入队列的元素也将是最先离开队列的元素。这个概念类似于现实生活中的排队场景,比如在超市结账,先到达收银台的顾客会先完成结账离开。

1.线式队列

线式队列就是线性表+队列性质组成的数据结构

代码实现

class Array():def __init__(self,size):self.__size = sizeself.__item = [None]*sizeself.__length = 0def __setitem__(self,key,value):self.__item[key] = valueself.__length += 1def __getitem__(self, index):return self.__item[index]def __len__(self):return self.__lengthdef __iter__(self):for value in self.__item:yield valueclass Linear_Queue():def __init__(self,size=4):self.size = sizeself.items = Array(size)self.head = 0self.end = 0def push(self,value):self.items[self.head % self.size] = valueself.head += 1def pop(self):temp = self.items[self.end % self.size]self.end += 1return tempif __name__ == '__main__':lq = Linear_Queue()lq.push(11)lq.push(12)lq.push(13)lq.push(14)print(lq.pop())print(lq.pop())print(lq.pop())print(lq.pop())

2.链式队列

链式队列就是链表+队列性质组成的数据结构

代码实现

class Node():def __init__(self,value=None,prev=None,next=None):self.value = valueself.next = nextself.prev = prevdef __str__(self):return "Node:{}".format(self.value)class DoubleLinkedList():def __init__(self):self.size = 0self.root = Node()self.end = Nonedef append(self,value):node = Node(value=value)#无节点if not self.end:self.root.next = node  # root节点指向新节点node.prev = self.root#新节点指向根节点self.end = node#末节点指针指向新节点#有节点else:self.end.next = node#末节点指向新节点node.prev = self.end  # 新节点指向末节点self.end = node#末节点移动到新节点self.size += 1def append_first(self,value):node = Node(value=value)#无节点if not self.end:self.root.next = node  # root节点指向新节点node.prev = self.root  # 新节点指向根节点self.end = node  # 末节点指针指向新节点else:node.prev = self.root#新节点指向根节点temp = self.root.next#保存原来的第一个节点self.root.next = node#将新节点替换为第一个节点node.next = temp#让新节点的下一个节点为原来的第一个节点temp.prev = node#将原来的第一个节点的上一个节点设置为新节点self.size += 1def __iter__(self):current = self.root.nextif current:while current is not self.end:yield currentcurrent = current.nextreturn currentelse:print("LinkedList is empty")#逆向迭代def inverse_iter(self):current = self.endif current:while current is not self.root:yield currentcurrent = current.prevelse:print("LinkedList is empty")def find(self,value):passdef find_count(self,value):passdef remove_first(self):if self.end:temp = self.root.nextself.root.next = temp.nextif temp.next:temp.next.prev = self.rootreturn tempdef remove_all(self,value):passclass Queue():def __init__(self,size=4):self.items = DoubleLinkedList()self.size = sizeself.length = 0def push(self,value):self.items.append(value)self.size += 1def pop(self):if self.length <= 0:returnself.length -= 1return self.items.remove_first()def empty(self):pass

二,栈 

1.双端队列

from collections import deque# 初始化队列
queue = deque()# 入队操作
queue.append(1)
queue.append(2)
queue.append(3)print("初始队列:", queue)# 出队操作
print("出队元素:", queue.popleft())  # 输出并移除队首元素
print("出队后队列:", queue)# 再次入队
queue.append(4)# 查看队列状态
print("当前队列:", queue)
print("队列长度:", len(queue))

根据双端队列的性质可以模仿出栈的效果(先进后出),其实就是 

from collections import deque
d = deque([1,2,3,4])print(d.pop())print(d.pop())print(d.pop())print(d.pop())

输出结果: 4 3 2 1

这就类似栈的性质,但是这里只是用双端了队列模拟的。 

相关文章:

队列和栈的实现

本节讲解的队列与栈&#xff0c;如果你对之前的线性和链式结构顺利掌握了&#xff0c;那么下边的队列和栈就小菜一碟了。因为我们会用前两节讲到的东西来实现队列和栈。 之所以放到一起讲是因为这两个东西很类似&#xff0c;队列是先进先出结构(FIFO, first in first out)&…...

lua vm 五: upvalue

前言 在 lua vm 中&#xff0c;upvalue 是一个重要的数据结构。upvalue 以一种高效的方式实现了词法作用域&#xff0c;使得函数能成为 lua 中的第一类值&#xff0c;也因其高效的设计&#xff0c;导致在实现上有点复杂。 函数 (proto) upvalue 构成了闭包&#xff08;closu…...

React Native中集成ArcGIS以显示地图、渲染自定义图层和获取地理信息数据

在您的数据采集上传的应用中集成ArcGIS以显示地图、渲染自定义图层和获取地理信息数据是一项常见需求。下面是如何实现这些功能的详细指南&#xff0c;包括具体步骤和示例代码。 1. 显示地图 原生开发 Android&#xff1a; 使用ArcGIS Android SDK。您需要在AndroidManifest…...

java中的异常-异常处理(try、catch、finally、throw、throws)+自定义异常

一、概述 1、java程序员在编写程序时提前编写好对异常的处理程序&#xff0c;在程序发生异常时就可以执行预先设定好的处理程序&#xff0c;处理程序执行完之后&#xff0c;可以继续向后执行后面的程序 2、异常处理程序是在程序执行出现异常时才执行的 二、5个关键字 1、tr…...

深入了解反射

newInstance 可访问性限制&#xff1a; newInstance()方法只能调用无参的公共构造函数。如果类没有无参公共构造函数&#xff0c;那么newInstance()方法将无法使用。 异常处理&#xff1a; newInstance()方法在创建对象时会抛出受检异常InstantiationException和IllegalAcces…...

5、搭建前端项目

5.1 使用vite vue搭建 win r 打开终端 切换到你想要搭建的盘 npm init vitelatest跟着以下步骤取名即可 cd fullStackBlognpm installnpm run dev默认在 http://localhost:5173/ 下启动了 5.2 用vscode打开项目并安装需要的插件 1、删除多余的 HelloWorld.vue 文件 2、安装…...

LLM之Agent初探

Agent是什么&#xff1f; Agent一词起源于拉丁语中的Agere&#xff0c;意思是“to do”。在LLM语境下&#xff0c;Agent可以理解为在某种能自主理解、规划决策、执行复杂任务的智能体。 Agent并非ChatGPT升级版&#xff0c;它不仅告诉你“如何做”&#xff0c;更会帮你去做。…...

目录穿越漏洞CVE-2018-7171复现 又学到一招小技巧!!!!

还是半夜睡不着&#xff0c;打开靶机开始操作。今天看了文件下载和目录穿越漏洞想结合以及防御方法。半夜来进行操作一波。复现一下漏洞&#xff0c;这个网上的文章页比较的少&#xff01;&#xff01;&#xff01; 开始操作起来&#xff01;&#xff01;&#xff01; 进入到页…...

代码随想录算法训练营day41

题目&#xff1a;01背包理论基础、416. 分割等和子集 参考链接&#xff1a;代码随想录 动态规划&#xff1a;01背包理论基础 思路&#xff1a;01背包是所有背包问题的基础&#xff0c;第一次看到比较懵&#xff0c;完全不知道dp数据怎么设置。具体分析还是dp五部曲&#xff…...

从0~1开发财务软件

1.获取图形验证码接口 功能要求 1、随机生成6位字符 2、将字符生成base64位格式的图片&#xff0c;返回给前端 3、将生成的字符存储到redis中&#xff0c;用匿名身份id&#xff08;clientId&#xff09;作为key&#xff0c;验证码作为value。 clientId通过/login/getClien…...

Python实现连连看9

&#xff08;2&#xff09;标识选中的图片 在判断出玩家选中的是哪一张图片之后&#xff0c;接下来就可以标识选中的图片了&#xff0c;即在该选中的图片外围画矩形。代码如下所示。 FIRSTCLICK True #FIRSTCLICK是全局变量 if(click_col>0 and click_row>0) and \(no…...

项目验收总体计划书(实际项目验收原件参考Word)

测试目标&#xff1a;确保项目的需求分析说明书中的所有功能需求都已实现&#xff0c;且能正常运行&#xff1b;确保项目的业务流程符合用户和产品设计要求&#xff1b;确保项目的界面美观、风格一致、易学习、易操作、易理解。 软件全套文档过去进主页。 一、 前言 &#xff0…...

C++基础与深度解析 | 异常处理 | 枚举与联合 | 嵌套类与局部类 | 嵌套名字空间与匿名名字空间 | 位域与volatile关键字

文章目录 一、异常处理二、枚举与联合三、嵌套类与局部类四、嵌套名字空间与匿名名字空间五、位域与volatile关键字 一、异常处理 异常处理用于处理程序在调用过程中的非正常行为。 传统的处理方法&#xff1a;传返回值表示函数调用是否正常结束。 例如&#xff0c;返回 0 表示…...

番外篇 | 利用华为2023最新Gold-YOLO中的Gatherand-Distribute对特征融合模块进行改进

前言:Hello大家好,我是小哥谈。论文提出一种改进的信息融合机制Gather-and-Distribute (GD) ,通过全局融合多层特征并将全局信息注入高层,以提高YOLO系列模型的信息融合能力和检测性能。通过引入MAE-style预训练方法,进一步提高模型的准确性。🌈 目录 🚀1.论文解…...

python记录之字符串

在Python中&#xff0c;字符串是一种非常常见且重要的数据类型&#xff0c;用于存储文本信息。下面&#xff0c;我们将对Python字符串进行深入的讲解&#xff0c;包括其基本操作、常见方法、格式化以及高级特性。 1. 字符串的创建 在Python中&#xff0c;字符串可以通过单引号…...

Elasticsearch 认证模拟题 - 15

一、题目 原索引 task1 的字段 title 字段包含单词 The&#xff0c;查询 the 可以查出 1200 篇文档。重建 task1 索引为 task1_new&#xff0c;重建后的索引&#xff0c; title 字段查询 the 单词&#xff0c;不能匹配到任何文档。 PUT task1 {"mappings": {"…...

g++ 预处理 编译 汇编 链接 命令

g 预处理 编译 汇编 链接 命令 在命令行中使用 g 预处理、编译、汇编和链接源代码文件通常遵循以下步骤&#xff1a; 预处理&#xff08;Preprocessing&#xff09;&#xff1a;将源代码文件转换为经过预处理器处理的中间文件。 g -E source.cpp -o source.i 编译&#xff…...

计算机视觉中的low-level与 high-level任务

文章目录 low-level任务high-level任务区别联系others参考在计算机视觉领域中,low-level任务和high-level任务是两个重要的概念,他们分别涉及图像处理和分析的不同的层次。 low-level任务 low-level任务主要关注的是图像的底层特征,如颜色、纹理、边缘、形状等。通常涉及对…...

安徽京准NTP时钟系统:GPS北斗卫星授时下的生活重塑

安徽京准NTP时钟系统&#xff1a;GPS北斗卫星授时下的生活重塑 安徽京准NTP时钟系统&#xff1a;GPS北斗卫星授时下的生活重塑 时间的流逝自古以来时钟都是人类生活与活动的基础。然而&#xff0c;随着科技的进步&#xff0c;我们对时间管理和测量的方法已经发生了翻天覆地的变…...

图论第8天

685.冗余连接II 这题需要考虑两种情况&#xff1a; 1.两个输入 2.没有两个输入就是有成环 class Solution { public:static const int N 1005;int father[N];int n;void init(){for (int i 0; i < n; i){father[i] i;}}int find(int x){return x father[x] ? x : f…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...