当前位置: 首页 > 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;包括佳能、…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...