栈（Stack）核心概念

栈（Stack）核心概念

什么是栈？

栈是一种**后进先出（LIFO - Last In First Out）**的线性数据结构。想象一摞盘子，你只能从顶部放盘子，也只能从顶部取盘子。

栈的核心操作

图解：栈的工作流程

初始状态：空栈 ┌─────────┐ │ │ ← 栈顶 (Top) └─────────┘ push(10): ┌─────────┐ │ 10 │ ← 栈顶 └─────────┘ push(20): ┌─────────┐ │ 20 │ ← 栈顶 ├─────────┤ │ 10 │ └─────────┘ push(30): ┌─────────┐ │ 30 │ ← 栈顶 ├─────────┤ │ 20 │ ├─────────┤ │ 10 │ └─────────┘ pop() → 返回 30: ┌─────────┐ │ 20 │ ← 栈顶 ├─────────┤ │ 10 │ └─────────┘ peek() → 返回 20 (不移除): ┌─────────┐ │ 20 │ ← 栈顶 ├─────────┤ │ 10 │ └─────────┘

Java 实现栈的三种方式

方式一：基于数组实现（手动实现）

publicclassArrayStack<T>{privateObject[]elements;privateinttop;// 栈顶指针privateintcapacity;// 容量publicArrayStack(intcapacity){this.capacity=capacity;this.elements=newObject[capacity];this.top=-1;// -1 表示空栈}// 入栈publicvoidpush(Titem){if(isFull()){thrownewRuntimeException("栈已满");}elements[++top]=item;}// 出栈@SuppressWarnings("unchecked")publicTpop(){if(isEmpty()){thrownewRuntimeException("栈为空");}Titem=(T)elements[top];elements[top--]=null;// 防止内存泄漏returnitem;}// 查看栈顶@SuppressWarnings("unchecked")publicTpeek(){if(isEmpty()){thrownewRuntimeException("栈为空");}return(T)elements[top];}publicbooleanisEmpty(){returntop==-1;}publicbooleanisFull(){returntop==capacity-1;}publicintsize(){returntop+1;}// 测试publicstaticvoidmain(String[]args){ArrayStack<Integer>stack=newArrayStack<>(5);System.out.println("=== 入栈操作 ===");stack.push(10);stack.push(20);stack.push(30);System.out.println("栈大小: "+stack.size());// 3System.out.println("\n=== 查看栈顶 ===");System.out.println("栈顶元素: "+stack.peek());// 30System.out.println("\n=== 出栈操作 ===");while(!stack.isEmpty()){System.out.println("弹出: "+stack.pop());// 30, 20, 10}}}

方式二：基于链表实现（动态扩容）

publicclassLinkedStack<T>{privatestaticclassNode<T>{Tdata;Node<T>next;Node(Tdata){this.data=data;}}privateNode<T>top;// 栈顶节点privateintsize;// 入栈（头插法）publicvoidpush(Titem){Node<T>newNode=newNode<>(item);newNode.next=top;top=newNode;size++;}// 出栈publicTpop(){if(isEmpty()){thrownewRuntimeException("栈为空");}Tdata=top.data;top=top.next;size--;returndata;}publicTpeek(){if(isEmpty()){thrownewRuntimeException("栈为空");}returntop.data;}publicbooleanisEmpty(){returntop==null;}publicintsize(){returnsize;}}

方式三：使用 Java 内置 Stack 类（不推荐用于新项目）

importjava.util.Stack;publicclassBuiltInStackDemo{publicstaticvoidmain(String[]args){Stack<String>stack=newStack<>();// 入栈stack.push("Java");stack.push("Python");stack.push("Go");// 出栈while(!stack.isEmpty()){System.out.println(stack.pop());// Go, Python, Java}}}

⚠️注意：java.util.Stack是遗留类，官方推荐使用Deque接口的实现类（如ArrayDeque）代替。

推荐方式：使用 ArrayDeque（现代 Java 最佳实践）

importjava.util.ArrayDeque;importjava.util.Deque;publicclassModernStackDemo{publicstaticvoidmain(String[]args){// Deque 作为栈使用（官方推荐）Deque<Integer>stack=newArrayDeque<>();// 入栈stack.push(100);stack.push(200);stack.push(300);System.out.println("栈顶: "+stack.peek());// 300// 出栈while(!stack.isEmpty()){System.out.println("弹出: "+stack.pop());// 300, 200, 100}}}

栈的应用场景

经典例题：括号匹配检测

publicclassBracketMatch{publicstaticbooleanisValid(Strings){Deque<Character>stack=newArrayDeque<>();for(charc:s.toCharArray()){if(c=='('||c=='['||c=='{'){stack.push(c);}else{if(stack.isEmpty())returnfalse;chartop=stack.pop();if((c==')'&&top!='(')||(c==']'&&top!='[')||(c=='}'&&top!='{')){returnfalse;}}}returnstack.isEmpty();}publicstaticvoidmain(String[]args){System.out.println(isValid("()"));// trueSystem.out.println(isValid("()[]{}"));// trueSystem.out.println(isValid("(]"));// falseSystem.out.println(isValid("([)]"));// false}}

总结对比

栈是最基础且重要的数据结构之一，掌握它的原理和实现对于理解递归、算法设计都至关重要！