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

一、栈 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、跳表 

1.跳表由很多层结构组成，level是通过一定的概率随机产生的；
2.每一层都是一个有序的链表，默认是升序 ；
3.最底层(Level 1)的链表包含所有元素；
4.如果一个元素出现在Level i 的链表中，则它在Level i 之下的链表也都会出现；
5.每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。


import java.util.Random;public class SkipList {// 跳表中存储的是正整数，并且存储的数据是不重复的private static final int MAX_LEVEL = 16;// 结点的个数private int levelCount = 1;// 索引的层级数private final Node head = new Node();// 头结点private final Random random = new Random();// 查找操作public Node find(int value) {Node p = head;for (int i = levelCount - 1; i >= 0; --i) {while (p.next[i] != null && p.next[i].data < value) {p = p.next[i];}}if (p.next[0] != null && p.next[0].data == value) {return p.next[0];    // 找到，则返回原始链表中的结点} else {return null;}}// 插入操作public void insert(int value) {int level = randomLevel();Node newNode = new Node();newNode.data = value;newNode.maxLevel = level;   // 通过随机函数改变索引层的结点布置Node[] update = new Node[level];for (int i = 0; i < level; ++i) {update[i] = head;}Node p = head;for (int i = level - 1; i >= 0; --i) {while (p.next[i] != null && p.next[i].data < value) {p = p.next[i];}update[i] = p;}for (int i = 0; i < level; ++i) {newNode.next[i] = update[i].next[i];update[i].next[i] = newNode;}if (levelCount < level) {levelCount = level;}}// 删除操作public void delete(int value) {Node[] update = new Node[levelCount];Node p = head;for (int i = levelCount - 1; i >= 0; --i) {while (p.next[i] != null && p.next[i].data < value) {p = p.next[i];}update[i] = p;}if (p.next[0] != null && p.next[0].data == value) {for (int i = levelCount - 1; i >= 0; --i) {if (update[i].next[i] != null && update[i].next[i].data == value) {update[i].next[i] = update[i].next[i].next[i];}}}}// 随机函数private int randomLevel() {int level = 1;for (int i = 1; i < MAX_LEVEL; ++i) {if (random.nextInt() % 2 == 1) {level++;}}return level;}// Node内部类public static class Node {private int data = -1;private final Node[] next = new Node[MAX_LEVEL];private int maxLevel = 0;// 重写toString方法@Overridepublic String toString() {return "{data:" +data +"; levels: " +maxLevel +" }";}}// 显示跳表中的结点public void display() {Node p = head;while (p.next[0] != null) {System.out.println(p.next[0] + " ");p = p.next[0];}System.out.println();}
}

 

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

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

相关文章

【C++】运算符重载 ⑧ ( 左移运算符重载 | 友元函数 / 成员函数 实现运算符重载 | 类对象 使用 左移运算符 )

【C++】运算符重载 ⑧ ( 左移运算符重载 | 友元函数 / 成员函数 实现运算符重载 | 类对象 使用 左移运算符 )

文章目录 一、左移运算符重载1、友元函数 / 成员函数 实现运算符重载2、类对象 使用 左移运算符3、左移运算符 << 重载 二、完整代码示例 一、左移运算符重载 1、友元函数 / 成员函数 实现运算符重载 运算符重载 的正规写法一般都是 使用 成员函数 的形式 实现的 ; 加法…
阅读更多...
Android笔记：Android 组件化方案探索与思考

Android笔记：Android 组件化方案探索与思考

组件化项目&#xff0c;通过gradle脚本&#xff0c;实现module在编译期隔离&#xff0c;运行期按需加载&#xff0c;实现组件间解耦&#xff0c;高效单独调试。 先来一张效果图 组件化初衷 APP版本不断的迭代&#xff0c;新功能的不断增加&#xff0c;业务也会变的越来越复杂…
阅读更多...
速学数据结构 | 手把手教你会单链表的构建方式

速学数据结构 | 手把手教你会单链表的构建方式

&#x1f3ac; 鸽芷咕&#xff1a;个人主页 &#x1f525; 个人专栏: 《初阶数据结构》《C语言进阶篇》 ⛺️生活的理想&#xff0c;就是为了理想的生活! 文章目录 &#x1f4cb; 前言1. 什么是链表1.1 链表的物理结构1.2 链表的种类 2. 链表的实现一. SList.h 单链表的声明3.…
阅读更多...
React antd Table点击下一页后selectedRows丢失之前页选择内容的问题

React antd Table点击下一页后selectedRows丢失之前页选择内容的问题

一、问题 使用了React antd 的<Table>标签&#xff0c;是这样记录选中的行id与行内容的&#xff1a; <TabledataSource{data.list}rowSelection{{selectedRowKeys: selectedIdsInSearchTab,onChange: this.onSelectChange,}} // 表格是否可复选&#xff0c;加 type: …
阅读更多...
智慧公厕：将科技融入日常生活的创新之举

智慧公厕：将科技融入日常生活的创新之举

智慧公厕是当今社会中一项备受关注的创新项目。通过将科技融入公厕设计和管理中&#xff0c;这些公厕不仅能够提供更便利、更卫生的使用体验&#xff0c;还能够极大地提升城市形象和居民生活质量。本文将以智慧公厕领先厂家广州中期科技有限公司&#xff0c;大量的精品案例项目…
阅读更多...
vue3中使用return语句返回this.$emit()，在同一行不执行,换行后才执行，好奇怪！

vue3中使用return语句返回this.$emit()，在同一行不执行,换行后才执行，好奇怪！

今天练习TodoList任务列表案例,该案例效果如图所示&#xff1a; 此案例除了根组件App.vue&#xff0c;还有TodoList、TodoInput、TodoButton三个子组件。 因为有视频讲解&#xff0c;在制作TodoList、TodoInput时很顺利&#xff0c;只是在完成TodoButton这个组件时出了点问题…
阅读更多...
网络爬虫——urllib（1）

网络爬虫——urllib（1）

前言&#x1f36d; ❤️❤️❤️网络爬虫专栏更新中&#xff0c;各位大佬觉得写得不错&#xff0c;支持一下&#xff0c;感谢了&#xff01;❤️❤️❤️ 前篇简单介绍了什么是网络爬虫及相关概念&#xff0c;这篇开始讲解爬虫中的第一个库——urllib。 urllib&#x1f36d; …
阅读更多...
UG\NX二次开发 用程序修改“用户默认设置”

UG\NX二次开发 用程序修改“用户默认设置”

文章作者：里海 来源网站：《里海NX二次开发3000例专栏》 感谢粉丝订阅 感谢 wuguoyana、duanxheng 两位粉丝订阅本专栏，非常感谢。 简介 可以用程序修改“用户默认设置”吗？下面是用代码修改“用户默认设置->基本环境->用户界面->操作记录->操作记录语言”的例子…
阅读更多...
【Python+requests+unittest+excel】实现接口自动化测试框架

【Python+requests+unittest+excel】实现接口自动化测试框架

一、框架结构&#xff1a; 工程目录 二、Case文件设计 三、基础包 base3.1 封装get/post请求&#xff08;runmethon.py&#xff09; 1 import requests2 import json3 class RunMethod:4 def post_main(self,url,data,headerNone):5 res None6 if header …
阅读更多...
【AI视野·今日Robot 机器人论文速览 第四十六期】Tue, 3 Oct 2023

【AI视野·今日Robot 机器人论文速览 第四十六期】Tue, 3 Oct 2023

AI视野今日CS.Robotics 机器人学论文速览 Tue, 3 Oct 2023 Totally 76 papers &#x1f449;上期速览✈更多精彩请移步主页 Interesting: &#x1f4da;Aerial Interaction with Tactile, 无人机与触觉的结合&#xff0c;实现空中交互与相互作用。(from CMU) website&#…
阅读更多...
10.3倒水问题（几何图论建模）

10.3倒水问题（几何图论建模）

坐标图中每一个位置都对应一个合法的状态&#xff0c;BC对5升杯子做出限制&#xff0c;AD对9升杯子作出限制 每次倒水&#xff0c;都只能把目标杯子装满&#xff0c;否则无法确定倒出水的多少与目标杯子此时水的容量 所以例如&#xff0c;倒5升杯子时&#xff0c;只能要么把5…
阅读更多...
Python逐日填补Excel中的日期并用0值填充缺失日期的数据

Python逐日填补Excel中的日期并用0值填充缺失日期的数据

本文介绍基于Python语言&#xff0c;读取一个不同的列表示不同的日期的.csv格式文件&#xff0c;将其中缺失的日期数值加以填补&#xff1b;并用0值对这些缺失日期对应的数据加以填充的方法。 首先&#xff0c;我们明确一下本文的需求。现在有一个.csv格式文件&#xff0c;其第…
阅读更多...
Pyhon-每日一练(1)

Pyhon-每日一练(1)

&#x1f308;write in front&#x1f308; &#x1f9f8;大家好&#xff0c;我是Aileen&#x1f9f8;.希望你看完之后&#xff0c;能对你有所帮助&#xff0c;不足请指正&#xff01;共同学习交流. &#x1f194;本文由Aileen_0v0&#x1f9f8; 原创 CSDN首发&#x1f412; 如…
阅读更多...
竞赛选题 深度学习 opencv python 实现中国交通标志识别_1

竞赛选题 深度学习 opencv python 实现中国交通标志识别_1

文章目录 0 前言1 yolov5实现中国交通标志检测2.算法原理2.1 算法简介2.2网络架构2.3 关键代码 3 数据集处理3.1 VOC格式介绍3.2 将中国交通标志检测数据集CCTSDB数据转换成VOC数据格式3.3 手动标注数据集 4 模型训练5 实现效果5.1 视频效果 6 最后 0 前言 &#x1f525; 优质…
阅读更多...
拆解常见的6类爆款标题写作技巧！

拆解常见的6类爆款标题写作技巧！

究竟是先写好文章再拟标题还是先确定标题再写文章呢&#xff1f;很多写稿小白都会有这样的疑惑。 在“人人皆可新媒体”的时代&#xff0c;公众号推文类型琳琅满目&#xff0c;每个人都可以建立自己的公众号&#xff0c;写出自己想写的文章。 但怎样起标题、起什么样的标题&a…
阅读更多...
Linux CentOS7 vim宏操作

Linux CentOS7 vim宏操作

vim的macro就是用来解决重复的问题。在vim寄存器的文章里面已经对macro有所涉及&#xff0c;macro的操作都是以文本的方式存放在寄存器中。 宏是一组命令的集合&#xff0c;应用极其广泛&#xff0c;包括MS Office中的word编辑器&#xff0c;excel编辑器和各种文本编辑器&…
阅读更多...
MySQL复制，约束条件，查询与安全控制

MySQL复制，约束条件，查询与安全控制

MySQL之复制 复制表 我有一个表 mysql> show tables; ------------------ | Tables_in_school | ------------------ | student | ------------------mysql> select * from student; -------------------------------------------- | id | name | sec |…
阅读更多...
asp.net班级管理系统VS开发sqlserver数据库web结构c#编程Microsoft Visual Studio

asp.net班级管理系统VS开发sqlserver数据库web结构c#编程Microsoft Visual Studio

一、源码特点 asp.net班级管理系统 是一套完善的web设计管理系统&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为vs2010&#xff0c;数据库为sqlserver2008&#xff0c;使用c#语言开发 asp.net班级管理系统 二、功能介绍 1…
阅读更多...
LVS负载均衡集群

LVS负载均衡集群

一.LVS集群基本介绍 1.1.群集的含义 Cluster&#xff0c;集群、群集 由多台主机构成&#xff0c;但对外只表现为一个整体&#xff0c;只提供一个访问入口&#xff08;域名或IP地址&#xff09;&#xff0c;相当于一台大型计算机。 1.2.群集的作用 对于企业服务的的性能提升…
阅读更多...
【Spring篇】Bean的三种配置和实例化方法

【Spring篇】Bean的三种配置和实例化方法

&#x1f38a;专栏【Spring】 &#x1f354;喜欢的诗句&#xff1a;天行健&#xff0c;君子以自强不息。 &#x1f386;音乐分享【如愿】 &#x1f384;欢迎并且感谢大家指出小吉的问题&#x1f970; 文章目录 &#x1f33a;bean基本配置&#x1f33a;bean别名配置&#x1f33a…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023