用Java打造高效栈数据结构
栈（Stack）是一种遵循后进先出（LIFO，Last In First Out）原则的线性数据结构。在Java中，我们可以通过接口抽象其行为，再分别用数组或链表实现。以下展示完整实现，包含两个版本：数组栈和链表栈。
1. 定义栈接口
首先定义一个泛型接口，明确栈的核心操作：
public interface IStack<E> {
boolean add(E item); // 入栈
E remove(); // 出栈
E top(); // 查看栈顶
boolean empty(); // 判空
int length(); // 元素个数
void reset(); // 清空
}
2. 基于数组的栈实现
使用动态数组存储，支持自动扩容，避免固定容量限制。
public class ArrayBasedStack<T> implements IStack<T> {
private static final int INIT_CAPACITY = 10;
private T[] data;
private int count;
@SuppressWarnings("unchecked")
public ArrayBasedStack() {
data = (T[]) new Object[INIT_CAPACITY];
count = 0;
}
@SuppressWarnings("unchecked")
public ArrayBasedStack(int capacity) {
if (capacity <= 0) throw new IllegalArgumentException("容量必须大于0");
data = (T[]) new Object[capacity];
count = 0;
}
@Override
public boolean add(T item) {
ensureCapacity();
data[count++] = item;
return true;
}
@Override
public T remove() {
if (empty()) throw new RuntimeException("栈为空");
T value = data[--count];
data[count] = null; // 避免内存泄漏
return value;
}
@Override
public T top() {
if (empty()) throw new RuntimeException("栈为空");
return data[count - 1];
}
@Override
public boolean empty() {
return count == 0;
}
@Override
public int length() {
return count;
}
@Override
public void reset() {
for (int i = 0; i < count; i++) data[i] = null;
count = 0;
}
private void ensureCapacity() {
if (count >= data.length) {
@SuppressWarnings("unchecked")
T[] newData = (T[]) new Object[data.length * 2];
System.arraycopy(data, 0, newData, 0, count);
data = newData;
}
}
// 从栈底到栈顶输出
public void printStack() {
System.out.print("栈内容: [");
for (int i = 0; i < count; i++) {
System.out.print(data[i]);
if (i < count - 1) System.out.print(", ");
}
System.out.println("]");
}
}
3. 基于链表的栈实现
使用单向链表，元素动态分配，无容量限制。
public class LinkedStack<T> implements IStack<T> {
private Node<T> head; // 栈顶节点
private int size;
private static class Node<E> {
E value;
Node<E> next;
Node(E value) { this.value = value; }
}
public LinkedStack() {
head = null;
size = 0;
}
@Override
public boolean add(T item) {
Node<T> newNode = new Node<>(item);
newNode.next = head;
head = newNode;
size++;
return true;
}
@Override
public T remove() {
if (empty()) throw new RuntimeException("栈为空");
T result = head.value;
head = head.next;
size--;
return result;
}
@Override
public T top() {
if (empty()) throw new RuntimeException("栈为空");
return head.value;
}
@Override
public boolean empty() {
return size == 0;
}
@Override
public int length() {
return size;
}
@Override
public void reset() {
head = null;
size = 0;
}
// 借助临时栈实现从底到顶的输出
public void printStack() {
System.out.print("栈内容: [");
LinkedStack<T> temp = new LinkedStack<>();
Node<T> current = head;
while (current != null) {
temp.add(current.value);
current = current.next;
}
while (!temp.empty()) {
System.out.print(temp.remove());
if (!temp.empty()) System.out.print(", ");
}
System.out.println("]");
}
}
4. 测试两种实现
编写测试代码验证功能：
public class StackDemo {
public static void main(String[] args) {
System.out.println("=== 数组栈测试 ===");
runTests(new ArrayBasedStack<>());
System.out.println("\n=== 链表栈测试 ===");
runTests(new LinkedStack<>());
}
static void runTests(IStack<Integer> stack) {
stack.add(10);
stack.add(20);
stack.add(30);
stack.add(40);
// 输出栈内容
if (stack instanceof ArrayBasedStack) {
((ArrayBasedStack<Integer>) stack).printStack();
} else {
((LinkedStack<Integer>) stack).printStack();
}
System.out.println("栈顶元素: " + stack.top());
System.out.println("元素个数: " + stack.length());
System.out.println("移除元素: " + stack.remove());
System.out.println("移除元素: " + stack.remove());
if (stack instanceof ArrayBasedStack) {
((ArrayBasedStack<Integer>) stack).printStack();
} else {
((LinkedStack<Integer>) stack).printStack();
}
System.out.println("是否为空: " + stack.empty());
stack.reset();
System.out.println("清空后是否为空: " + stack.empty());
}
}
关键操作说明
- 入栈：将元素压入栈顶。
- 出栈：弹出并返回栈顶元素。
- 查看栈顶：仅返回不删除。
- 判空与大小：检查栈是否为空及元素数量。
- 清空：重置栈状态。
数组栈适合随机访问频繁的场景，链表栈适合插入删除操作多的场景。两种实现都遵循LIFO原则，可根据需求灵活选用。
