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

数据结构—栈、队列、链表

一、栈 Stack(存取O(1))

先进后出,进去123,出来321。
基于数组:最后一位为栈尾,用于取操作。
基于链表:第一位为栈尾,用于取操作。

1.1、数组栈 

/*** 基于数组实现的顺序栈; items[0]:表头/栈底;  items[size-1]:表尾/栈顶;*/
public class MyArrayStack {// 存储元素的 数组private String items[];// 栈实际大小private int size =0;// 栈的容量private int capacity = 0;public MyArrayStack(int capacity) {this.size = 0;this.capacity = capacity;this.items = new String[capacity];}/*** 入栈*/public boolean push(String item) {if(size >= capacity){throw new IndexOutOfBoundsException("MyArrayStack 栈的内存满了");}items[size] = item;size++;return true;}/*** 出栈*/public String pop() {if(size<=0){throw new IndexOutOfBoundsException("MyArrayStack 栈的内存空了");}String item = items[size-1];items[size-1] = null;size--;return item;}
}

1.2、链表栈 

/*** 基于链表实现的链式栈  top: 表尾/栈顶;*/
public class MyLinkedStack {// 表尾/栈顶;private Node top = null;/*** 入栈*/public void push(String value) {Node node = new Node(value,null);if(top != null){node.nextNode = top;}top = node;}/*** 出栈*/public String pop() {if(top==null){throw new IndexOutOfBoundsException("MyLinkedStack 栈的内存空了");}String retValue = top.getValue();top = top.nextNode;return retValue;}/*** 节点*/private static class Node{// 存储数据private String value;// 下个节点private Node nextNode;public Node(String value, Node nextNode) {this.value = value;this.nextNode = nextNode;}public String getValue() {return value;}}
}

二、队列 Queue (存取O(1))

先进先出(FIFO)的有序列表 

2.1、数组单向队列 (存取O(1))

/*** 基于数组实现的顺序队列*/
public class MyArrayQueue {private String [] items;// 容量private int capacity = 0;// 队头下标private int head = 0;// 队尾下标private int tail = 0;public MyArrayQueue(int capacity) {this.items = new String [capacity];this.capacity = capacity;}/*** 入队*/public boolean enqueue(String item) {if(capacity == tail){throw new IndexOutOfBoundsException("MyArrayQueue 容量满了");}items[tail] = item;tail++;return true;}/*** 出队*/public String dequeue() {if(head==tail){throw new IndexOutOfBoundsException("MyArrayQueue 容量空了");}String retValue = items[head];head++;return retValue;}
}

2.2、链表单向队列 

/*** 基于链表实现的链式队列*/
public class MyLinkedListQueue {// 队头private Node head = null;// 队尾private Node tail = null;/*** 入队*/public void enqueue(String value) {Node node = new Node(value,null);if(tail==null){head = node;tail = node;}else {tail.next=node;tail=node;}}/*** 出队*/public String dequeue() {if(head==null){throw new IndexOutOfBoundsException("MyLinkedListQueue 队列空了");}String retValue = head.getValue();head = head.next;if (head == null) {tail = null;}return retValue;}private static class Node{private String value;private Node next;public Node(String value, Node next) {this.value = value;this.next = next;}public String getValue() {return value;}}
}

三、链表 LinkedList 

3.1、单向链表 

/*** 单向普通链表*/
public class MyLinkedList {// 链表大小private int size;// 表头private Node head;/*** 插入*/public void insert(int index, String value) {if(index<0){throw new IndexOutOfBoundsException("MyLinkedList 下标越界了");} else {if(head==null){head = new Node(value,null);}else {if(index>=size){index = size-1;}Node prev = head;for(int i=0;i<index;i++){prev = prev.next;}Node node = new Node(value,prev);prev.next =node;}size++;}}/*** 获取*/public String get(int index){if(size<=0){throw new IllegalArgumentException("MyLinkedList 空链表");}if(index<0 || index>=size) {throw new IllegalArgumentException("MyLinkedList 下标越界了");}Node prev = head;for (int i=0;i<index;i++){prev = prev.next;}return prev.getValue();}private class Node{private String value;private Node next;public Node(String value, Node next) {this.value = value;this.next = next;}public String getValue() {return value;}}
}

3.2、双向链表 


public class MyDoubleLinkedList {// 链表大小private int size;// 表头private Node head;// 表尾private Node tail;/*** 插入*/public void insert(int index,String data) {if(index < 0) {throw new IndexOutOfBoundsException("MyDoubleLinkedList  insert 下标越界");}Node node = new Node(data,null,null);if(index == 0) {head.next = node.next;head= node;return;}if(index >= size) {tail.prev = node.prev;tail= node;return;}Node cur = this.head;while(index != 0) {cur = cur.next;index--;}node.next = cur;cur.prev.next = node;node.prev = cur.prev;cur.prev = node;}public String get(int index){if(index<0||index>size){throw new IndexOutOfBoundsException("MyDoubleLinkedList get 下标越界了");}if(index<=(size/2)){Node cur = head;for(int i = 0;i<index-1;i++){cur = head.next;}return cur.getValue();}else {index = size-index;Node cur = tail;for (int i=size;i>index;i--){cur = cur.prev;}return cur.getValue();}}private class Node{public String value;public Node prev;public Node next;public Node(String value, Node prev, Node next) {this.value = value;this.prev = prev;this.next = next;}public String getValue() {return value;}}
}

3.3、跳表 

相关文章:

数据结构—栈、队列、链表

一、栈 Stack&#xff08;存取O(1)&#xff09; 先进后出&#xff0c;进去123&#xff0c;出来321。 基于数组&#xff1a;最后一位为栈尾&#xff0c;用于取操作。 基于链表&#xff1a;第一位为栈尾&#xff0c;用于取操作。 1.1、数组栈 /*** 基于数组实现的顺序栈&#…...

2023年4月到7月工作经历

2023年4 有同事说程序崩溃一起分析得结果 unsigned uNum 2; std::string str "abc" uNum; std::cout << str; 结果是c 。如果uNum 很大的话&#xff0c;就可能崩溃。 unsigned uNum 2; //std::string str "abc" uN…...

嵌入式Linux应用开发-驱动大全-同步与互斥③

嵌入式Linux应用开发-驱动大全-同步与互斥③ 第一章 同步与互斥③1.4 Linux锁的介绍与使用1.4.1 锁的类型1.4.1.1 自旋锁1.4.1.2 睡眠锁 1.4.2 锁的内核函数1.4.2.1 自旋锁1.4.2.2 信号量1.4.2.3 互斥量1.4.2.4 semaphore和 mutex的区别 1.4.3 何时用何种锁1.4.4 内核抢占(pree…...

力扣-383.赎金信

Idea 使用一个hashmap 或者一个int数组存储第二次字符串中每一个字符及其出现的次数 遍历第一个字符串&#xff0c;讲出现的重复字符减1&#xff0c;若该字符次数已经为0&#xff0c;则返回false AC Code class Solution { public:bool canConstruct(string ransomNote, strin…...

计算机网络 第二章物理层

计算机网络第二章知识点速刷 其中重要的是信源和信宿&#xff0c;以及调制解调器在通信模型当中起到的作用。...

uniapp:动态修改页面标题

我们经常遇到这种情况&#xff0c;点击新增按钮&#xff0c;进入一个空白表单页面&#xff0c;点击修改按钮&#xff0c;其实也是进入这个表单页面&#xff0c;只是表单内容已经被数据库的记录反显了&#xff0c;为了区别页面&#xff0c;我们还需要动态设置页面的标题&#xf…...

java学生管理系统

一、项目概述 本学生管理系统旨在提供一个方便的界面&#xff0c;用于学校或机构管理学生信息&#xff0c;包括学生基本信息、课程成绩等。 二、系统架构 系统采用经典的三层架构&#xff0c;包括前端使用JavaSwing&#xff0c;后端采用Java Servlet&#xff0c;数据库使用M…...

Docker和容器化:简介和使用案例

Docker和容器化&#xff1a;简介和使用案例 引言 容器化技术在近年来变得越来越流行&#xff0c;为开发人员和运维团队提供了更加灵活、高效的软件部署和管理方式。其中&#xff0c;Docker是最为知名和广泛使用的容器化平台之一。本篇博客文章将介绍Docker和容器化的基本概念…...

(高阶) Redis 7 第18讲 RedLock 分布式锁

🌹 以下分享 RedLock 分布式锁,如有问题请指教。🌹🌹 如你对技术也感兴趣,欢迎交流。🌹🌹🌹 如有对阁下帮助,请👍点赞💖收藏🐱‍🏍分享😀 问题 分布式锁问题从(高阶) Redis 7 第17讲 分布式锁 实战篇_PJ码匠人的博客-CSDN博客 这篇文章来看,…...

嵌入式软件架构基础设施设计方法

大家好&#xff0c;今天分享一篇嵌入式软件架构设计相关的文章。 软件架构这东西&#xff0c;众说纷纭&#xff0c;各有观点。在我看来&#xff0c;软件架构是软件系统的基本结构&#xff0c;包含其组件、组件之间的关系、组件设计与演进的规则&#xff0c;以及体现这些规则的基…...

MySQL进阶_3.性能分析工具的使用

文章目录 第一节、数据库服务器的优化步骤第二节、查看系统性能参数第三节、 慢查询日志第四节、 查看 SQL 执行成本第五节、 分析查询语句&#xff1a;EXPLAIN5.1 基本语法5.2 EXPLAIN各列作用 第一节、数据库服务器的优化步骤 当我们遇到数据库调优问题的时候&#xff0c;可…...

Scala第十三章节

Scala第十三章节 1. 高阶函数介绍 2. 作为值的函数 3. 匿名函数 4. 柯里化 5. 闭包 6. 控制抽象 7. 案例: 计算器 scala总目录 文档资料下载...

Nginx高级 第一部分:扩容

Nginx高级 第一部分&#xff1a;扩容 通过扩容提升整体吞吐量 1.单机垂直扩容&#xff1a;硬件资源增加 云服务资源增加 整机&#xff1a;IBM、浪潮、DELL、HP等 CPU/主板&#xff1a;更新到主流 网卡&#xff1a;10G/40G网卡 磁盘&#xff1a;SAS(SCSI) HDD&#xff08;机械…...

vue项目上线后去除控制台所有console.log打印-配置说明

方式一 npm i babel-plugin-transform-remove-console --save-dev babel.config.js文件中添加 // 然后在babel.config.js中添加判断 const prodPlugin []if (process.env.NODE_ENV production) { // 如果是生产环境&#xff0c;则自动清理掉打印的日志&#xff0c;但保留…...

《XSS-Labs》02. Level 11~20

XSS-Labs 索引Level-11题解 Level-12题解 Level-13题解 Level-14题解 Level-15题解 Level-16题解 Level-17题解 Level-18~20题解 靶场部署在 VMware - Win7。 靶场地址&#xff1a;https://github.com/do0dl3/xss-labs 只要手动注入恶意 JavaScript 脚本成功&#xff0c;就可以…...

Java中处理千万级数据的最佳实践:性能优化指南

在今天的数字化时代&#xff0c;处理大规模数据已经成为许多Java应用程序的核心任务。无论您是构建数据分析工具、实现实时监控系统&#xff0c;还是处理大规模日志文件&#xff0c;性能优化都是确保应用程序能够高效运行的关键因素。本指南将介绍一系列最佳实践&#xff0c;帮…...

LCR 069.山峰数组的峰顶索引

​​题目来源&#xff1a; leetcode题目&#xff0c;网址&#xff1a;LCR 069. 山脉数组的峰顶索引 - 力扣&#xff08;LeetCode&#xff09; 解题思路&#xff1a; 二分查找即可。 解题代码&#xff1a; class Solution {public int peakIndexInMountainArray(int[] arr) {…...

AtCoder Beginner Contest 233 (A-Ex)

A.根据题意模拟即可 B.根据题意模拟即可 C.直接用map 进行dp即可 D.用前缀和进行模拟&#xff0c;用map统计前缀和&#xff0c;每次计算当前前缀和-k的个数就是以当前点为右端点答案。 E - Σ[k0..10^100]floor(X&#xff0f;10^k) (atcoder.jp) &#xff08;1&#xff09;…...

解决caffe中的python环境安装的问题

由于caffe&#xff08;GitHub - BVLC/caffe: Caffe: a fast open framework for deep learning.&#xff09;使用的python版本是2.7&#xff0c;而非python3&#xff0c;所以安装的时候使用命令&#xff1a;sudo apt install python2.7进行安装。 而在安装python的各种包时&am…...

专业图像处理软件DxO PhotoLab 7 mac中文特点和功能

DxO PhotoLab 7 mac是一款专业的图像处理软件&#xff0c;它为摄影师和摄影爱好者提供了强大而全面的照片处理和编辑功能。 DxO PhotoLab 7 mac软件特点和功能 强大的RAW和JPEG格式处理能力&#xff1a;DxO PhotoLab 7可以处理来自各种相机的RAW格式图像&#xff0c;包括佳能、…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

中南大学无人机智能体的全面评估!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.…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...