使用ArrayList逐步手撕stack
在日常开发中，Stack 是一个非常经典的数据结构，用于实现后进先出（LIFO，Last In First Out）的功能。Java 标准库里已经提供了 Stack 类，但它实际上是基于 Vector 实现的，性能一般，而且不推荐用于高并发场景。那么我们就自己手撕一个！
今天我们就用 ArrayList 来实现一个自定义的轻量级、灵活性更高的栈 Stack，顺便把源码中的一些核心方法拆开理解清除。
1，为什么选择 ArrayList 实现 Stack？
ArrayList 是 Java 中常用的动态数组，它有几个非常适合实现栈功能的特点：
-
动态扩展：
ArrayList会根据需要动态调整容量，避免手动扩容的麻烦。 -
末尾操作快：
ArrayList在尾部的增删操作是 O(1)O(1)O(1)，完全符合栈的需求。 -
够轻量： 相比
Stack（基于线程安全的Vector），ArrayList不带锁，性能更高。
2，所需要实现栈的哪些基本功能
（1）push(E item)：向栈顶添加元素。
（2）pop()：移除并返回栈顶元素。
（3）peek()：获取栈顶元素但不移除。
（4）isEmpty()：判断栈是否为空。
（5）size()：获取栈的大小。
3，实现代码
import java.util.ArrayList;
public class MyStack<E> {
private ArrayList<E> list; // 用来存储栈元素
public MyStack() {
list = new ArrayList<>(); // 初始化 ArrayList
}
// 添加元素到栈顶
public void push(E item) {
list.add(item); // 添加到 ArrayList 的末尾
}
// 移除并返回栈顶元素
public E pop() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty, cannot pop!");
}
return list.remove(list.size() - 1); // 移除并返回最后一个元素
}
// 获取栈顶元素但不移除
public E peek() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty, cannot peek!");
}
return list.get(list.size() - 1); // 返回最后一个元素
}
// 判断栈是否为空
public boolean isEmpty() {
return list.isEmpty(); // ArrayList 自带的方法
}
// 获取栈的大小
public int size() {
return list.size(); // ArrayList 自带的方法
}
// 重写toString来方便测试等等
@Override
public String toString() {
return String.valueOf(list);
}
}
4,逐行拆解源码，知其然更知其所以然
接下来，让我们结合 ArrayList 的源码，拆解一下 MyStack 的核心方法。
1. push：添加元素到栈顶
public void push(E item) {
list.add(item);
}
底层源码（ArrayList 的 add 方法）：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 确保容量足够
elementData[size++] = e; // 将元素添加到数组末尾
return true;
}
扩容机制： 当容量不足时，ArrayList 会扩容为当前容量的 1.5 倍，具体操作：
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩展为 1.5 倍
elementData = Arrays.copyOf(elementData, newCapacity);
}
特点：
绝大多数情况下，添加元素的时间复杂度是 O(1)O(1)O(1)。
当需要扩容时，时间复杂度为 O(n)O(n)O(n)。
2. pop：移除并返回栈顶元素
public E pop() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty, cannot pop!");
}
return list.remove(list.size() - 1);
}
底层源码（ArrayList 的 remove 方法）：
public E remove(int index) {
rangeCheck(index); // 检查索引合法性
modCount++; // 记录结构修改次数（支持快速失败）
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
elementData[--size] = null; // 清理最后一个元素，帮助垃圾回收
return oldValue;
}
分析：
移除操作需要移动数组中的元素。
但因为我们总是移除最后一个元素，所以无需移动其他元素，效率很高。
3. peek：获取栈顶元素但不移除
public E peek() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty, cannot peek!");
}
return list.get(list.size() - 1);
}
底层源码（ArrayList 的 get 方法）：
public E get(int index) {
rangeCheck(index); // 检查索引合法性
return elementData(index);
}
特点：
- 获取最后一个元素的时间复杂度是 O(1)O(1)O(1)。
- 没有对数组进行修改，仅仅返回数据。
4. isEmpty：判断栈是否为空
public boolean isEmpty() {
return list.isEmpty();
}
底层源码（ArrayList 的 isEmpty 方法）：
public boolean isEmpty() {
return size == 0; // 判断大小是否为 0
}
解析：
- 直接读取
size字段，时间复杂度为 O(1)。
5. size：获取栈的大小
底层源码（ArrayList 的 size 方法）：
public int size() {
return size; // 直接返回大小
}
测试实例：
总结
通过手撕一个基于 ArrayList 的栈，我们可以发现：
ArrayList提供的动态扩容和快速访问非常适合栈的实现。- 自定义栈更加灵活，可以根据业务需求进一步扩展功能。
- 当然，如果在多线程环境中使用，还需要手动添加同步机制（比如
Collections.synchronizedList()）。
自己动手实现一遍，既能加深对栈的理解，也能学到 ArrayList 的底层设计精髓！赶紧试试看吧～如果你有更好的思路或者疑问，欢迎在评论区交流～
原文地址：https://blog.csdn.net/ymr1843762281/article/details/143804575
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！