java如何实现栈
实现栈的基本方法
Java中可以通过数组或链表实现栈。栈是一种后进先出（LIFO）的数据结构，主要操作包括push（入栈）、pop（出栈）、peek（查看栈顶元素）和isEmpty（判断栈是否为空）。
使用数组实现栈
数组实现的栈需要动态调整容量，适合对性能要求较高的场景。
public class ArrayStack {
private int[] stack;
private int top;
private int capacity;
public ArrayStack(int capacity) {
this.capacity = capacity;
this.stack = new int[capacity];
this.top = -1;
}
public void push(int item) {
if (top == capacity - 1) {
resize();
}
stack[++top] = item;
}
public int pop() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty");
}
return stack[top--];
}
public int peek() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty");
}
return stack[top];
}
public boolean isEmpty() {
return top == -1;
}
private void resize() {
int newCapacity = capacity * 2;
int[] newStack = new int[newCapacity];
System.arraycopy(stack, 0, newStack, 0, capacity);
stack = newStack;
capacity = newCapacity;
}
}使用链表实现栈
链表实现的栈不需要处理容量问题，适合动态增长和缩小的场景。
public class LinkedListStack {
private static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
private Node top;
public void push(int item) {
Node newNode = new Node(item);
newNode.next = top;
top = newNode;
}
public int pop() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty");
}
int item = top.data;
top = top.next;
return item;
}
public int peek() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty");
}
return top.data;
}
public boolean isEmpty() {
return top == null;
}
}使用Java内置类实现栈
Java提供了java.util.Stack类，可以直接使用。
import java.util.Stack;
public class BuiltInStackExample {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
System.out.println(stack.pop()); // 输出2
System.out.println(stack.peek()); // 输出1
}
}性能比较
- 数组实现：适合固定容量或需要动态扩容的场景，访问速度快，但扩容时可能产生额外开销。
- 链表实现：适合动态增长和缩小的场景，内存利用率高，但访问速度稍慢。
- 内置类：使用方便，但性能可能不如自定义实现。
选择哪种实现方式取决于具体需求，如性能、内存使用和开发效率。
