萝卜建站下载购物链接

萝卜建站下载,购物链接,校园二手网站开发的意义,wordpress的alt属性插件一、什么是栈#xff1f;栈#xff08;Stack#xff09;:是一种 后进先出#xff08;LIFO#xff0c;Last In First Out#xff09; 的数据结构。栈的核心特性只能在一端操作#xff08;称为 栈顶 top#xff09;基本操作#xff1a;入栈#xff08;push#xff09;…一、什么是栈栈Stack:是一种后进先出LIFOLast In First Out的数据结构。栈的核心特性只能在一端操作称为栈顶 top基本操作入栈push出栈pop查看栈顶peek二、栈的逻辑结构 vs 物理结构逻辑结构栈顶 ┌───┐ │ 3 │ ├───┤ │ 2 │ ├───┤ │ 1 │ └───┘ 栈底物理实现方式数组实现顺序栈链表实现链式栈三、手写一个顺序栈数组实现1. 栈的基本结构public class ArrayStack { private int[] data; // 存放元素 private int top; // 栈顶指针 private int capacity; public ArrayStack(int capacity) { this.capacity capacity; data new int[capacity]; top -1; // 栈空 } }2. 入栈pushpublic void push(int value) { if (top capacity - 1) { throw new RuntimeException(栈满无法入栈); } data[top] value; }关键点top capacity - 1→ 栈满先top再赋值3. 出栈poppublic int pop() { if (top -1) { throw new RuntimeException(栈空无法出栈); } return data[top--]; }关键点先取值再top--4. 查看栈顶peekpublic int peek() { if (top -1) { throw new RuntimeException(栈空); } return data[top]; }5. 测试代码public static void main(String[] args) { ArrayStack stack new ArrayStack(5); stack.push(1); stack.push(2); stack.push(3); System.out.println(stack.pop()); // 3 System.out.println(stack.peek()); // 2 }四、链式栈链表实现优势不需要扩容不受数组大小限制1. 节点定义class Node { int value; Node next; Node(int value) { this.value value; } }2. 栈结构public class LinkedStack { private Node top; public LinkedStack() { top null; } }3. 入栈头插法public void push(int value) { Node node new Node(value); node.next top; top node; }4. 出栈public int pop() { if (top null) { throw new RuntimeException(栈空); } int value top.value; top top.next; return value; }五、栈的经典应用 ①括号匹配问题描述输入 {[()]} 输出 true解题思路左括号 → 入栈右括号 → 弹栈匹配代码实现public static boolean isValid(String s) { DequeCharacter stack new ArrayDeque(); for (char c : s.toCharArray()) { if (c ( || c [ || c {) { stack.push(c); } else { if (stack.isEmpty()) return false; char top stack.pop(); if (c ) top ! () return false; if (c ] top ! [) return false; if (c } top ! {) return false; } } return stack.isEmpty(); }六、栈的经典应用 ②表达式求值逆波兰示例输入[2,1,,3,*] 输出9代码实现public static int evalRPN(String[] tokens) { DequeInteger stack new ArrayDeque(); for (String token : tokens) { if (-*/.contains(token)) { int b stack.pop(); int a stack.pop(); switch (token) { case : stack.push(a b); break; case -: stack.push(a - b); break; case *: stack.push(a * b); break; case /: stack.push(a / b); break; } } else { stack.push(Integer.parseInt(token)); } } return stack.pop(); }七、栈在系统层面的真实应用1. JVM 虚拟机栈每个线程一个栈栈帧包含局部变量表操作数栈返回地址递归本质 不断入栈2. 函数调用过程void a() { b(); } void b() { c(); }调用顺序a 入栈 b 入栈 c 入栈 c 出栈 b 出栈 a 出栈八、栈常见面试问题总结题型关键词括号匹配栈单调栈下一个更大元素表达式求值操作数栈DFS / 回溯系统栈中序 → 后序栈九、总结一句话栈的本质延迟处理 最近优先掌握栈你会突然发现递归不再神秘表达式计算有迹可循很多“看起来复杂”的问题本质只是一个栈