数据结构与算法 —— Java 实现（线性表）
数据结构与算法 （Java 语言实现） —— 线性表
- 一、Java 数组的回顾学习
- 二、使用 OOP 编写变长数组 - 2.0 准备 - 2.1 实现 add 动态添加一个元素 - 2.2 实现 delete 删除任意一个位置的元素 - 2.3 实现 size 方法获取当前数组的长度 - 2.4 实现 get 获取指定下标的元素 - 2.5 实现 insert 在任意位置插入一个元素 - 2.6 实现 set 替换任意一个元素
- 三、栈的实现 （Stack） - 3.1 栈的基本特点 - 3.2 栈的实现之准备工作 - 3.3 栈的实现之入栈 （push） - 3.4 栈的实现之出栈（pop） - 3.5 栈的实现之查看栈顶元素（peek） - 3.6 栈的实现之判断栈为空（isEmpty）
- 四、队列的实现 （Queue） - 4.1 队列的基本特点 - 4.2 队列之入队（add） - 4.3 队列之出队 （pull） - 4.4 队列之判断队列是否为空（isEmpty）
一、Java 数组的回顾学习
在学 java 基础的时候，我们会经常用到数组来存储相同类型的数据，下面我们就来简单回顾一下 Java 数组的简单使用，实在忘记怎么使用 java 数组的同学可以查看这篇文章 Java 数组的使用
import java.util.Arrays;
public class TestArray {
public static void main(String[] args) {
// 创建一个数组
int[] arr = new int[5];
// 获取数组长度
int len = arr.length;
// 循环给数组赋值
for (int i=0;i<len;i++) {
arr[i] = i*i;
}
// 遍历数组
for (int i=0; i<len; i++)
System.out.println(arr[i]);
// 显示数组中的所有元素
System.out.println(Arrays.toString(arr));
}
}以上便是系统给我们提供的 数组 api ，基于此我们可以我们就可以完成很多常规操作。但是内置的数组有时候也会带来极大的局限性？
- 数组是定长的，我们需要动态的修改数据要怎么解决呢？
- 比如往数组添加一个元素？可以使用 List ArrayList 等等现成的数据结构
- 删除一个元素又要如何来做呢？
- 修改元素很简单，直接替换对应的下标的值即可
- 在任意位置插入一个元素该怎么处理呢？
但是如果能够出现一个变长数组的话，这些问题就可以很轻松的解决了。
二、使用 OOP 编写变长数组
注意：如果要实现传入任意数据类型的话，我们就可以把 int 数组 改为 object即可
2.0 准备
定义一个 MyArray 的 Java 类，然后添加一个私有的数组属性，并使用 无参的构造方法把数组初始化为长度为0的一个数组
/**
* 封装数组
* */
public class MyArray {
private int[] elements;// 存储数据的数组，如果存储其他类型，声明为 Object
public MyArray() {
elements=new int[0];
}
}2.1 实现 add 动态添加一个元素
我们使用定长数组的时候，要实现往数组中添加一个元素，这时候我们想到的一个方式就是创建一个新的数组来实现扩容，顺着这个思路就这往下想，是不是轻松很多了呢？
思路有了，我们就用代码实现
// 我们要实现新增一个元素，所以需要传一个要新增元素的参数
public void add(int element) {
// 创建一个比元素组容量多一个元素的数组空间
int[] newArr = new int[elements.length+1];
// 使用循环给新数组赋值
for(int i=0;i<elements.length;i++) {
newArr[i] = elements[i];
}
// 赋值完毕之后，把新增的元素放在数组的最后一个位置, 这里填写 elements.length 大家可以仔细思考以下 下标和 长度的位置关系
newArr[elements.length] = element;
// 把数组更新即可
elements = newArr;
}2.2 实现 delete 删除任意一个位置的元素
删除一个元素，分为两种情况：
- 一种是删除末尾元素
- 一种是删除中间的元素
删除末尾的元素比较容易，直接把数组的长度减一，然后把剩下的元素重新赋值给一个新的元素就 OK 了
删除中间的元素，要考虑一个元素，就是是否越界的情况要考虑在内，如果没有越界，就把删除的元素的前面的元素重新赋值，删除的元素的后面的元素也直接赋值的新数组当中就可以了
// 删除数组中的元素
public void delete(int index) {
// 判断下标是否越界
if (index<0 || index>elements.length-1) {
throw new RuntimeException("下标越界");
}
int newArr[] = new int[elements.length-1];
// 复制原有数据到新数组
for (int i=0; i<newArr.length; i++) {
if (i<index) {
newArr[i] = elements[i];
} else {
// 想要删除之后的元素
newArr[i] = elements[i+1];
}
}
// 新数组替换就数组
elements = newArr;
}2.3 实现 size 方法获取当前数组的长度
直接返回当前数组的长度即可
public int size() {
return elements.length;
}2.4 实现 get 获取指定下标的元素
用户传入一个下标值，然后判断传入的值是否合理，不合理则返回异常。反之就正常返回数据
public int get(int index) {
if (index<0 || index >elements.length)
throw new RuntimeException("下标越界");
return elements[index];
}2.5 实现 insert 在任意位置插入一个元素
和删除元素是一样的道理，只不过是在任意位置增加一个元素
// 插入元素到一个指定位置
public void insert(int index, int element) {
// 创建一个新数组
int[] newArr = new int[elements.length + 1];
for (int i=0;i<newArr.length;i++) {
// 前面的数据保持一致
if (i<index) {
newArr[i] = elements[i];
} else {
// 后面的数据在插入的位置留出来
newArr[i+1] = elements[i];
}
}
// 实现插入操作
newArr[index] = element;
// 数组替换
elements = newArr;
}2.6 实现 set 替换任意一个元素
替换只需要用户传入下标值，以及要替换的元素即可
// 替换指定位置的元素
public void set(int index, int element) {
elements[index] = element;
}三、栈的实现 （Stack）
3.1 栈的基本特点
栈是一个 单进单出的数据结构，栈只能在一端进，一端出。下面画一个图给大家加深一下印象
- 栈具有栈底 以及 栈顶两部分
- 每次入栈 和 出栈 都是从栈顶进入和出去的
- 第一个入栈的元素会直接压入栈底，然后慢慢的往栈顶堆，直到栈被装满
- 栈是具有 先进后出， 后进显出的特点
3.2 栈的实现之准备工作
我是使用动态数组完成栈的操作的，当然一个栈的空间应该一开始就指定好的。
/**
* 实现栈，使用数组存储数据
* 每次往栈顶添加元素
* */
public class MyStack {
int[] elements;
// 栈的初始化
public MyStack() {
elements = new int[0];
}
}3.3 栈的实现之入栈 （push）
// 入栈 push， 把数据放进栈的最后
public void push(int element) {
int newArr[] = new int[elements.length+1];
for (int i=0;i<elements.length-1;i++) {
newArr[i] = elements[i];
}
//
newArr[elements.length] = element;
// 更新数组
elements = newArr;
}3.4 栈的实现之出栈（pop）
// 出栈 pop， 取栈顶元素
public int pop() {
if (elements.length == 0) {
throw new RuntimeException("tack is empty!");
}
// 去最后一个元素
int element = elements[elements.length-1];
// 创建一个新数组
int newArr[] = new int[elements.length-1];
for (int i=0;i<elements.length-1;i++) {
newArr[i] = elements[i];
}
elements = newArr;
// 返回栈顶元素
return element;
}3.5 栈的实现之查看栈顶元素（peek）
//查看栈顶元素
public int peek() {
if (elements.length == 0) {
throw new RuntimeException("stack is empty!");
}
return elements[elements.length-1];
}3.6 栈的实现之判断栈为空（isEmpty）
// 判断栈是否为空
public boolean isEmpty() {
return elements.length == 0;
}四、队列的实现 （Queue）
4.1 队列的基本特点
- 队列有两端，一段是队首，另一端就是队尾
- 队列进入元素一般是从队首进入
- 队列出元素一般是从队尾出
- 队列的特点，先进先出，后进后出
4.2 队列之入队（add）
第一次用 PPT 动画做
// 入队
public void add(int element) {
int newArr[] = new int[elements.length + 1];
// 数组拷贝
for (int i=0;i<elements.length;i++) {
newArr[i] = elements[i];
}
newArr[elements.length] = element;
this.elements = newArr;
}4.3 队列之出队 （pull）
// 出队
public int pull() {
int element = elements[0]; // 取出第一个数
int newArr[] = new int[elements.length-1];
// 这里使用新数组的长度来拷贝
for (int i=0;i<newArr.length;i++) {
newArr[i] = elements[i+1];
}
this.elements = newArr;
return element;
}4.4 队列之判断队列是否为空（isEmpty）
// 判断队列是否为空
public boolean isEmpty() {
return this.elements.length == 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/03/20 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
