【Java】从源码深入理解 Stack

从源码深入理解 StackStack的整体架构Stack的成员变量Stack的构造函数Stack的常用方法源码解读压栈push()出栈pop()获取栈顶元素peek()判断是否为空empty()查找元素search()存储的元素个数size()Stack的设计缺陷破坏封装性线程安全的代价Stack vs Deque常见面试题Q1Stack的底层数据结构是什么Q2Stack是线程安全的吗Q3为什么官方不推荐使用Stack?Q4Stack和ArrayDeque的区别Q5Stack的search方法返回值为什么从1开始Stack的整体架构Stack类的继承关系如下publicclassStackEextendsVectorE从继承结构可以看出VectorStack继承自Vector这意味着Stack拥有Vector的所有方法由于继承VectorStack本质上是一个数组实现的栈Stack的成员变量Stack类本身没有定义任何成员变量所有数据存储都来自父类Vector// Vector类中的核心成员变量protectedObject[]elementData;// 存储元素的数组protectedintelementCount;// 实际元素个数protectedintcapacityIncrement;// 容量增长系数Stack的构造函数// Stack只有一个无参构造器publicStack(){}注意Stack没有指定初始容量的构造器完全依赖Vector的默认行为。// Vector的无参构造器publicVector(){this(10);// 默认初始容量为10}Stack的常用方法源码解读压栈push()publicEpush(Eitem){addElement(item);// 调用父类Vector的方法returnitem;}查看Vector的addElement方法publicsynchronizedvoidaddElement(Eobj){modCount;// 记录修改次数用于迭代器快速失败ensureCapacityHelper(elementCount1);// 确保容量足够elementData[elementCount]obj;// 在数组末尾添加元素}addElement是synchronized的所以Stack是线程安全的栈顶对应数组的末尾最后一个元素当容量不足时会触发动态扩容容量扩容逻辑privatevoidensureCapacityHelper(intminCapacity){if(minCapacity-elementData.length0)grow(minCapacity);// 需要扩容}privatevoidgrow(intminCapacity){intoldCapacityelementData.length;// 如果capacityIncrement 0则增加capacityIncrement// 否则容量翻倍这是Vector与ArrayList的主要区别intnewCapacityoldCapacity((capacityIncrement0)?capacityIncrement:oldCapacity);if(newCapacity-minCapacity0)newCapacityminCapacity;if(newCapacity-MAX_ARRAY_SIZE0)newCapacityhugeCapacity(minCapacity);elementDataArrays.copyOf(elementData,newCapacity);}出栈pop()publicsynchronizedEpop(){Eobj;intlensize();// size()返回elementCountobjpeek();// 先获取栈顶元素removeElementAt(len-1);// 删除最后一个元素returnobj;}获取栈顶元素peek()查看peek()方法publicsynchronizedEpeek(){intlensize();if(len0)thrownewEmptyStackException();// 栈空抛异常returnelementAt(len-1);// 返回数组最后一个元素}查看removeElementAt方法publicsynchronizedvoidremoveElementAt(intindex){modCount;if(indexelementCount){thrownewArrayIndexOutOfBoundsException(index elementCount);}elseif(index0){thrownewArrayIndexOutOfBoundsException(index);}intjelementCount-index-1;if(j0){// 将index后面的元素向前移动对于栈来说j0不会执行System.arraycopy(elementData,index1,elementData,index,j);}elementCount--;elementData[elementCount]null;// 帮助GC}关键点对于栈来说removeElementAt总是删除最后一个元素所以System.arraycopy不会执行j0性能为O(1)。判断是否为空empty()publicbooleanempty(){returnsize()0;}查找元素search()publicsynchronizedintsearch(Objecto){intilastIndexOf(o);// 从后往前找if(i0){returnsize()-i;// 转换为从1开始的位置}return-1;}查看Vector的lastIndexOf方法publicsynchronizedintlastIndexOf(Objecto){returnlastIndexOf(o,elementCount-1);}publicsynchronizedintlastIndexOf(Objecto,intindex){if(indexelementCount)thrownewIndexOutOfBoundsException(index elementCount);if(onull){for(intiindex;i0;i--)if(elementData[i]null)returni;}else{for(intiindex;i0;i--)if(o.equals(elementData[i]))returni;}return-1;}search是从栈顶数组末尾向栈底数组开头搜索返回的位置从1开始栈顶位置为1而不是从0开始找不到返回-1存储的元素个数size()// Stack类本身没有定义size()方法继承自Vectorpublicsynchronizedintsize(){returnelementCount;}Stack的设计缺陷破坏封装性由于Stack继承Vector它拥有了Vector的所有公开方法StackIntegerstacknewStack();stack.push(1);stack.push(2);stack.push(3);// 这些操作破坏了栈的LIFO特性stack.add(0,100);// 在底部插入stack.get(1);// 随机访问stack.remove(0);// 删除中间元素stack.set(1,999);// 修改非栈顶元素问题栈本应只提供push/pop/peek操作但继承导致暴露了所有List操作栈的语义被破坏。线程安全的代价Stack的所有方法都是synchronized的但在大多数单线程场景下这个同步是不必要的开销。Stack vs Deque从Java 1.6开始官方推荐使用Deque接口的实现类如ArrayDeque作为栈的替代// 推荐做法DequeIntegerstacknewArrayDeque();// 栈操作对应关系// Stack.push() → Deque.push() / addFirst()// Stack.pop() → Deque.pop() / removeFirst()// Stack.peek() → Deque.peek() / peekFirst()// Stack.empty() → Deque.isEmpty()// Stack.search() → 无直接对应需要自己实现特性StackArrayDeque底层实现数组Vector循环数组线程安全是synchronized否阻塞操作不支持不支持容量限制无动态扩容无动态扩容额外List操作有破坏封装无内存效率较低Vector有capacityIncrement较高2的幂次扩容性能较慢同步开销较快推荐程度❌ 不推荐✅ 推荐// 使用 Stack不推荐StackIntegerstack1newStack();stack1.push(1);stack1.push(2);Integertop1stack1.pop();// 使用 ArrayDeque推荐DequeIntegerstack2newArrayDeque();stack2.push(1);// 等价于 addFirst()stack2.push(2);Integertop2stack2.pop();// 等价于 removeFirst()// 也可以使用 LinkedList但性能不如ArrayDequeDequeIntegerstack3newLinkedList();常见面试题Q1Stack的底层数据结构是什么A数组继承自Vector。Q2Stack是线程安全的吗A是所有核心方法都是synchronized的。Q3为什么官方不推荐使用Stack?A1继承Vector破坏了封装性暴露了不该有的List操作2同步开销在不必要场景下影响性能3推荐使用ArrayDeque替代。Q4Stack和ArrayDeque的区别AStack继承Vector数组实现线程安全但性能较差ArrayDeque使用循环数组非线程安全但性能更好且只暴露栈操作。Q5Stack的search方法返回值为什么从1开始A为了符合栈的语义——栈顶距离为1栈底距离为栈深度。这样设计使得位置与距离概念统一。