java实现栈通常有两种方式：基于数组和基于链表。1. 基于数组的栈实现简单，访问速度快，但容量固定，可能栈溢出；2. 基于链表的栈容量可动态扩展，不会溢出，但实现较复杂，访问速度稍慢。两者分别适用于容量已知且性能要求高或容量不确定的场景。此外，java自带的stack类因继承vector存在同步开销、容量固定及设计原则问题，建议自定义实现。栈在函数调用、表达式求值、浏览器导航、编辑器撤销重做、深度优先搜索等场景中广泛应用。对于并发访问，可通过synchronized、reentrantlock或使用concurrentlinkeddeque来解决。栈是lifo结构，而队列是fifo结构，二者操作位置不同，适用于不同需求。
Java实现栈，本质上是利用数组或者链表模拟栈的后进先出（LIFO）特性。关键在于维护一个指向栈顶的指针，并实现push（入栈）和pop（出栈）操作。
解决方案：
Java中实现栈，通常有两种方式：基于数组和基于链表。
立即学习“Java免费学习笔记（深入）”；
1. 基于数组的栈：
这种方式的优点是实现简单，访问速度快。缺点是容量固定，可能存在栈溢出的问题。
public class ArrayStack{ 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 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{ private static class Node { T data; Node next; Node(T data) { this.data = data; } } private Node top; private int size; public LinkedStack() { this.top = null; this.size = 0; } public boolean isEmpty() { return top == null; } public void push(T data) { Node 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 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）的数据结构。栈只允许在栈顶进行插入和删除操作，而队列允许在队尾进行插入操作，在队头进行删除操作。它们是两种不同的数据结构，适用于不同的场景。
