队列和栈的实现

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

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

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

独立游戏之路 -- 获取OAID提升广告收益

Unity 之 获取手机&#xff1a;OAID、IMEI、ClientId、GUID 前言一、Oaid 介绍1.1 Oaid 说明1.2 移动安全联盟(MSA) 二、站在巨人的肩膀上2.1 本文实现参考2.2 本文实现效果2.3 本文相关插件 三、Unity 中获取Oaid3.1 查看实现源码3.2 工程配置3.3 代码实现3.4 场景搭建 四、总…

Linux卸载残留MySQL【带图文命令巨详细】

Linux卸载残留MySQL 1、检查残留mysql2、检查并删除残留mysql依赖3、检查是否自带mariadb库 1、检查残留mysql 如果残留mysql组件&#xff0c;使用命令 rpm -e --nodeps 残留组件名 按顺序进行移除操作 #检查系统是否残留过mysql rpm -qa | grep mysql2、检查并删除残留mysql…

香橙派 Orange AIpro 测评记录视频硬件解码

香橙派 Orange AIpro 测评记录视频硬件解码 香橙派官网&#xff1a;http://www.orangepi.cn/ 收到了一块Orange Pi AIpro开发板&#xff0c;记录一下我的测评~测评简介如下&#xff1a;1.连接网络2.安装流媒体进行硬件解码测试3.安装IO测试 简介 Orange Pi AI Pro 是香橙派联合…

Web安全:Web体系架构存在的安全问题和解决方案

「作者简介」:2022年北京冬奥会网络安全中国代表队,CSDN Top100,就职奇安信多年,以实战工作为基础对安全知识体系进行总结与归纳,著作适用于快速入门的 《网络安全自学教程》,内容涵盖系统安全、信息收集等12个知识域的一百多个知识点,持续更新。 这一章节我们需要了解w…

Git【版本控制和Git的安装介绍】

01 【版本控制和Git的安装介绍】 工程设计领域中&#xff0c;使用“版本控制”管理工程蓝图的设计过程。在 IT 开发中也可以使用版本控制思想管理代码的版本迭代。 1.目的 协同修改&#xff1a;支持在服务器对同一个文件多人协同地修改&#xff1b; 数据备份&#xff1a;同时…

力扣hot100:138. 随机链表的复制(技巧,数据结构)

LeetCode&#xff1a;138. 随机链表的复制 这是一个经典的数据结构题&#xff0c;当做数据结构来学习。 1、哈希映射 需要注意的是&#xff0c;指针也能够当做unordered_map的键值&#xff0c;指针实际上是一个地址值&#xff0c;在unordered_map中&#xff0c;使用指针的实…

M1Pro 使用跳板机

Mac (M1 Pro) 通过Iterm2 使用跳板机 1、由于堡垒机&#xff08;跳板机&#xff09;不能支持mac系统终端工具&#xff0c;只支持xshell等win生态。所以我们需要先安装iterm2 装iterms教程 这里头对rz、sz的配置不详细。我们可以这样配置&#xff1a; where iterm2-send-zmod…

Stable diffusion采样器详解

在我们使用SD web UI的过程中&#xff0c;有很多采样器可以选择&#xff0c;那么什么是采样器&#xff1f;它们是如何工作的&#xff1f;它们之间有什么区别&#xff1f;你应该使用哪一个&#xff1f;这篇文章将会给你想要的答案。 什么是采样&#xff1f; Stable Diffusion模…

Spring Boot通过自定义注解和Redis+Lua脚本实现接口限流

&#x1f604; 19年之后由于某些原因断更了三年&#xff0c;23年重新扬帆起航&#xff0c;推出更多优质博文&#xff0c;希望大家多多支持&#xff5e; &#x1f337; 古之立大事者&#xff0c;不惟有超世之才&#xff0c;亦必有坚忍不拔之志 &#x1f390; 个人CSND主页——Mi…

社区物资交易互助平台的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;管理员管理&#xff0c;基础数据管理&#xff0c;论坛管理&#xff0c;公告信息管理 前台账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;论坛&#xff0c;求助留言板&#xff0c;公…

Go微服务: 分布式之通过本地消息实现最终一致性和最大努力通知方案

通过本地消息实现最终一致性 1 &#xff09;概述 我们的业务场景是可以允许我们一段时间有不一致的消息的状态的&#xff0c;并没有说必须特别高的这个消息的一致性比如说在TCC这个架构中&#xff0c;如果采用了消息的最终一致性&#xff0c;整体架构设计要轻松好多即便我们库…

例54:Draw使用

建立一个控制台工程&#xff0c;输入代码&#xff1a; Screen 13 移动到&#xff08;50,50&#xff09;而不绘图 Draw "BM 50,50" B:移动但不绘制,M:移动到指定位置 将绘图颜色设置为2&#xff08;绿色&#xff09; Draw "C2" C将颜色改为n …

酒店旅游API服务汇总

各大旅游平台常用API服务汇总&#xff1a; 实时房源服务【Airbnb】飞猪旅行开放服务途牛旅行开放平台API华为云数字差旅【差旅管理】动态信息接口【美团酒店】旅行商城商家管理API【马蜂窝】交易流程接口【美团酒店】电子导游【携程旅行】

如何提高网站收录?

GSI服务就是专门干这个的&#xff0c;这个服务用的是光算科技自己研发的GPC爬虫池系统。这个系统通过建立一个庞大的站群和复杂的链接结构&#xff0c;来吸引谷歌的爬虫。这样一来&#xff0c;你的网站就能更频繁地被谷歌的爬虫访问&#xff0c;从而提高被收录的机会。 说到效…

CGS与MGS的矩阵正交化-C语言实现

格拉姆-施密特正交化和改进的格拉姆-施密特正交化 格拉姆-施密特正交化CGS 数学公式 代码实现&#xff1a; 过程版 矩阵运算实现的难点在于每次运算都是一个向量&#xff0c;需要for循环进行&#xff0c;会带来运算时在代码中的复杂&#xff0c;进而难以理解代码的过程 Q矩阵…

python爬虫入门教程(一)

上一篇文章讲了爬虫的工作原理&#xff0c;这篇文章以后就要重点开始讲编程序了。 简单爬虫的的两个步骤&#xff1a; 使用HTTPRequest工具模拟HTTP请求&#xff0c;接收到返回的文本。用于请求的包有: requests、urllib等。 对接收的文本进行筛选,获取想要的内容。用户筛选文…

【C++题解】1265. 爱因斯坦的数学题

问题&#xff1a;1265. 爱因斯坦的数学题 类型&#xff1a;简单循环 题目描述&#xff1a; 爱因斯坦出了一道这样的数学题&#xff1a;有一条长阶梯&#xff0c;若每步跨 2 阶&#xff0c;则最最后剩一阶&#xff0c;若每步跨 3 阶&#xff0c;则最后剩 2 阶&#xff0c;若每…

【CS.DB】深度解析:ClickHouse与Elasticsearch在大数据分析中的应用与优化

文章目录 《深入对比&#xff1a;在大数据分析中的 ClickHouse和Elasticsearch》 1 介绍 2 深入非关系型数据库的世界2.1 非关系型数据库的种类2.2 列存储数据库&#xff08;如ClickHouse&#xff09;2.3 搜索引擎&#xff08;如Elasticsearch&#xff09;2.4 核心优势的归纳 3…

【MYSQL系列】mysql中text,longtext,mediumtext区别

【MYSQL系列】mysql中text,longtext,mediumtext区别 在MySQL数据库中&#xff0c;TEXT、LONGTEXT和MEDIUMTEXT都是用于存储大量文本数据的字段类型。它们之间的主要区别在于可存储的数据大小和性能方面的差异。本文将探讨这些字段类型的特点、使用场景和一些最佳实践。 TEXT类…

在UI界面中实现3d人物展示

简要原理&#xff08;设置双摄像机&#xff09;&#xff1a; 为需要展示的3D人物单独设置一个摄像机&#xff08;只设置为渲染人物层级&#xff09;&#xff0c;主要摄像机的方向与人物方向一致&#xff0c;但摄像机需要需要旋转180&#xff0c;设置的角度自行进行微调创建一个…