Java 数据结构之 Java 实现栈
Java 数据结构实现栈是 Java 编程语言中的一种基础数据结构。栈是一种抽象数据类型，遵循 FILO（First In Last Out，先进后出）原则，即最后入栈的元素最先出栈。栈的实现有多种方式，包括数组实现、链表实现等。本文将介绍 Java 中使用数组实现栈的方法。
栈的基本操作
栈的基本操作包括 push、pop、peek、isEmpty、size 等。
* push：向栈中添加元素。
* pop：从栈中删除元素。
* peek：查看栈顶元素。
* isEmpty：判断栈是否为空。
* size：获取栈中的元素个数。
Java 实现栈的代码
以下是使用 Java 实现栈的代码：
```java
import java.util.Arrays;
public class Stack<T> {
private int size; // 栈中元素的个数
private Object[] arr; // 底层数组
private final int defaultLength = 200; // 默认长度
public Stack() {
arr = new Object[defaultLength];
size = 0;
}
public Stack(int length) {
arr = new Object[length];
size = 0;
}
public void push(T element) {
if (size >= arr.length) {
extendCapacity(size + 1);
}
arr[size++] = element;
}
@SuppressWarnings("unchecked")
public T pop() {
if (size == 0) {
return null;
}
T t = (T) arr[size - 1];
arr[--size] = null;
return t;
}
public void clear() {
for (int i = 0; i < size; i++) {
arr[i] = null;
}
size = 0;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
@SuppressWarnings("unchecked")
public void printStack() {
for (int i = 0; i < size; i++) {
System.out.print(((T) arr[i]).toString());
}
System.out.println();
}
private void extendCapacity(int length) {
int minCapacity = Math.max(arr.length, length);
if (minCapacity - arr.length > 0) {
int newLength = arr.length + arr.length / 2;
if (newLength < minCapacity) {
newLength = minCapacity;
}
if (newLength > Integer.MAX_VALUE - 8) {
newLength = Integer.MAX_VALUE;
}
arr = Arrays.copyOf(arr, newLength);
}
}
}
```
栈的实现原理
栈的实现原理是使用数组来存储元素。数组的索引表示栈中的元素的位置。push 操作时，将元素添加到数组的末尾，并将 size 变量加 1。pop 操作时，将数组的最后一个元素删除，并将 size 变量减 1。
栈的应用
栈的应用非常广泛，例如：
* 解析表达式
* 实现递归算法
* 解析 XML 和 HTML 文档
* 实现 undo 和 redo 操作
结论
本文介绍了 Java 中使用数组实现栈的方法，包括栈的基本操作、实现原理和应用场景。栈是一种基础数据结构，掌握栈的实现和应用是 Java 开发者的必备技能。
