java实现栈通常有两种方式：基于数组和基于链表。1. 基于数组的栈实现简单，访问速度快，但容量固定，可能栈溢出；2. 基于链表的栈容量可动态扩展，不会溢出，但实现较复杂，访问速度稍慢。两者分别适用于容量已知且性能要求高或容量不确定的场景。此外，java自带的stack类因继承vector存在同步开销、容量固定及设计原则问题，建议自定义实现。栈在函数调用、表达式求值、浏览器导航、编辑器撤销重做、深度优先搜索等场景中广泛应用。对于并发访问，可通过synchronized、reentrantlock或使用concurrentlinkeddeque来解决。栈是lifo结构，而队列是fifo结构，二者操作位置不同，适用于不同需求。
Java实现栈，本质上是利用数组或者链表模拟栈的后进先出（LIFO）特性。关键在于维护一个指向栈顶的指针，并实现push（入栈）和pop（出栈）操作。
解决方案：
Java中实现栈，通常有两种方式：基于数组和基于链表。
立即学习“Java免费学习笔记（深入）”；
1. 基于数组的栈：
这种方式的优点是实现简单，访问速度快。缺点是容量固定，可能存在栈溢出的问题。
public class ArrayStack<T> {
private T[] stack;
private int top;
private int capacity;
public ArrayStack(int capacity) {
this.capacity = capacity;
this.stack = (T[]) new Object[capacity]; // 注意类型转换
this.top = -1; // 初始化栈顶指针
}
public boolean isEmpty() {
return top == -1;
}
public boolean isFull() {
return top == capacity - 1;
}
public void push(T data) {
if (isFull()) {
throw new RuntimeException("Stack is full");
}
stack[++top] = data;
}
public T pop() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty");
}
return stack[top--];
}
public T peek() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty");
}
return stack[top];
}
public int size() {
return top + 1;
}
public static void main(String[] args) {
ArrayStack<Integer> stack = new ArrayStack<>(5);
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println("Top element: " + stack.peek()); // Output: 3
System.out.println("Popped element: " + stack.pop()); // Output: 3
System.out.println("Current size: " + stack.size()); // Output: 2
}
}注意点：
- 数组的类型转换
(T[]) new Object[capacity]是必要的，因为Java泛型在运行时会被擦除。 - 需要处理栈满和栈空的异常情况。
2. 基于链表的栈：
这种方式的优点是容量可以动态扩展，不会出现栈溢出的问题。缺点是实现相对复杂，访问速度稍慢。
public class LinkedStack<T> {
private static class Node<T> {
T data;
Node<T> next;
Node(T data) {
this.data = data;
}
}
private Node<T> top;
private int size;
public LinkedStack() {
this.top = null;
this.size = 0;
}
public boolean isEmpty() {
return top == null;
}
public void push(T data) {
Node<T> newNode = new Node<>(data);
newNode.next = top;
top = newNode;
size++;
}
public T pop() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty");
}
T data = top.data;
top = top.next;
size--;
return data;
}
public T peek() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty");
}
return top.data;
}
public int size() {
return size;
}
public static void main(String[] args) {
LinkedStack<String> stack = new LinkedStack<>();
stack.push("A");
stack.push("B");
stack.push("C");
System.out.println("Top element: " + stack.peek()); // Output: C
System.out.println("Popped element: " + stack.pop()); // Output: C
System.out.println("Current size: " + stack.size()); // Output: 2
}
}注意点：
- 使用了内部类
Node来表示链表的节点。 - push操作在链表头部插入新节点，pop操作移除链表头部的节点。
自定义栈结构，其实就是自己实现一个栈，而不是直接使用Java提供的Stack类。
Java自带的Stack类有什么问题？
Java的Stack类继承自Vector，而Vector是线程安全的，这意味着Stack的很多方法都进行了同步，这在单线程环境下会造成性能损耗。此外，Vector底层使用数组实现，也存在容量固定的问题。更重要的是，从设计角度来看，Stack的设计并不符合单一职责原则。它既包含了栈的逻辑，又包含了Vector的特性。
栈的应用场景有哪些？
栈在计算机科学中应用广泛，例如：
- 函数调用栈： 存储函数调用的信息，用于实现递归和函数返回。
- 表达式求值： 将中缀表达式转换为后缀表达式，并进行求值。
- 浏览器的前进/后退功能： 使用两个栈分别存储前进和后退的页面。
- 编辑器中的撤销/重做功能： 使用栈存储操作历史。
- 深度优先搜索（DFS）： 在图的遍历中使用栈来存储待访问的节点。
如何选择基于数组还是链表的栈实现？
选择哪种实现方式取决于具体的需求。如果事先知道栈的容量大小，并且对性能要求较高，那么基于数组的栈可能更适合。如果栈的容量大小不确定，或者需要频繁进行扩容操作，那么基于链表的栈可能更合适。实际上，很多情况下，使用链表实现的栈更为灵活。
如何处理栈的并发访问问题？
如果多个线程需要同时访问栈，那么需要考虑线程安全问题。可以使用synchronized关键字或者ReentrantLock等机制来保证线程安全。当然，也可以使用线程安全的ConcurrentLinkedDeque来代替手写的栈结构，它在并发环境下有更好的性能。
栈和队列的区别是什么？
栈是后进先出（LIFO）的数据结构，而队列是先进先出（FIFO）的数据结构。栈只允许在栈顶进行插入和删除操作，而队列允许在队尾进行插入操作，在队头进行删除操作。它们是两种不同的数据结构，适用于不同的场景。
