当前位置: 首页 > 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…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

【SpringBoot自动化部署】

SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一&#xff0c;能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时&#xff0c;需要添加Git仓库地址和凭证&#xff0c;设置构建触发器&#xff08;如GitHub…...

【Linux】Linux安装并配置RabbitMQ

目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的&#xff0c;需要先安…...

解析“道作为序位生成器”的核心原理

解析“道作为序位生成器”的核心原理 以下完整展开道函数的零点调控机制&#xff0c;重点解析"道作为序位生成器"的核心原理与实现框架&#xff1a; 一、道函数的零点调控机制 1. 道作为序位生成器 道在认知坐标系$(x_{\text{物}}, y_{\text{意}}, z_{\text{文}}…...

Python的__call__ 方法

在 Python 中&#xff0c;__call__ 是一个特殊的魔术方法&#xff08;magic method&#xff09;&#xff0c;它允许一个类的实例像函数一样被调用。当你在一个对象后面加上 () 并执行时&#xff08;例如 obj()&#xff09;&#xff0c;Python 会自动调用该对象的 __call__ 方法…...

无需布线的革命:电力载波技术赋能楼宇自控系统-亚川科技

无需布线的革命&#xff1a;电力载波技术赋能楼宇自控系统 在楼宇自动化领域&#xff0c;传统控制系统依赖复杂的专用通信线路&#xff0c;不仅施工成本高昂&#xff0c;后期维护和扩展也极为不便。电力载波技术&#xff08;PLC&#xff09;的突破性应用&#xff0c;彻底改变了…...