诊所网站建设临沂网站建设培训班

张

张建站

2026/5/4 14:13:21

10分钟阅读

诊所网站建设,临沂网站建设培训班,广告主平台,东莞保安公司一览表1.00 栈(Stack) 1.01 概念 Java 中的栈#xff08;Stack#xff09;全称是Java 虚拟机栈#xff08;JVM Stack#xff09;#xff0c;可以把它理解成一个「单人储物柜」—— 每个线程启动时都会单独分配一个栈#xff0c;栈里只存当前线程执行方法所需的临时数据#xf…1.00 栈(Stack)1.01 概念Java 中的栈Stack全称是Java 虚拟机栈JVM Stack可以把它理解成一个「单人储物柜」—— 每个线程启动时都会单独分配一个栈栈里只存当前线程执行方法所需的临时数据线程之间的栈完全隔离互不干扰。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。出栈栈的删除操作叫做出栈。出数据在栈顶。1.02 栈的使用方法描述Stack()构造一个空的栈E push(E e)将e入栈并返回eE pop()将栈顶元素出栈并返回E peek()获取栈顶元素int size()获取栈中有效元素个数boolean empty()检测栈是否为空public static void main(String[] args) { StackInteger s new Stack(); s.push(1); s.push(2); s.push(3); s.push(4); System.out.println(获取栈中有效元素个数为 s.size()); // 获取栈中有效元素个数--- 4 System.out.println(获取栈顶元素 s.peek()); // 获取栈顶元素--- 4 s.pop(); // 4出栈栈中剩余1 2 3栈顶元素为3 System.out.println(出栈元素为 s.pop()); // 3出栈栈中剩余1 2 栈顶元素为3 if(s.empty()){ System.out.println(栈空); }else{ System.out.println(获取栈顶元素 s.size()); } }获取栈中有效元素个数为4 获取栈顶元素4 出栈元素为3 获取栈顶元素21.03 栈的应用一个简单的应用class MyStack { int[] array; int size; public MyStack() { array new int[3]; } public int push(int e) { ensureCapacity(); array[size] e; return e; } public int pop() { int e peek(); size--; return e; } public int peek() { if (empty()) { throw new RuntimeException(栈为空无法获取栈顶元素); } return array[size - 1]; } public int size() { return size; } public boolean empty() { return 0 size; } private void ensureCapacity() { if (size array.length) { array Arrays.copyOf(array, size * 2); } } public static void main(String[] args) { MyStack stack new MyStack(); stack.push(1); // 数组[1,0,0]size1 stack.push(2); // 数组[1,2,0]size2 stack.push(3); // 数组[1,2,3]size3数组满 stack.push(4); // 触发扩容数组变为[1,2,3,4,0,0]size4 System.out.println(stack.peek()); // 输出4栈顶 System.out.println(stack.pop()); // 输出4size3 System.out.println(stack.size()); // 输出3 System.out.println(stack.empty()); // 输出false } }1.04 概念区分经典面试题栈、虚拟机栈、栈帧有什么区别呢概念解释栈Stack通用数据结构概念抽象数据结构虚拟机栈JVM StackJVM 的内存区域栈帧Stack Frame虚拟机栈的最小单位层级关系代码解释public class StackDemo { public static int add(int a, int b) { // ② add方法对应一个栈帧 return a b; } public static void main(String[] args) { // ① main方法对应一个栈帧 int result add(1, 2); // ③ 调用addadd栈帧压入虚拟机栈顶 } // ④ add执行完add栈帧出栈main执行完main栈帧出栈 }执行过程 - 当主线程启动时JVM 为其创建虚拟机栈执行main方法创建main栈帧并压入虚拟机栈调用add方法创建add栈帧并压入虚拟机栈顶add执行完毕add栈帧出栈销毁main执行完毕main栈帧出栈销毁整个过程遵循「栈」的先进后出规则。2.02. 队列(Queue)2.01 概念队列Queue是和「栈」相对的线性数据结构核心规则是「先进先出FIFOFirst In First Out」—— 就像日常生活中排队买东西先排队的人先结账后排队的人后结账。2.02 队列的使用在Java中Queue是个接口底层是通过链表实现的.方法功能boolean offer(E e)入队列E poll()出队列peek()获得对头元素int size()获得队列有效的元素个数boolean isEmpty()检测队列是否为空public static void main(String[] args) { QueueInteger q new LinkedList(); q.offer(1); q.offer(2); q.offer(3); q.offer(4); q.offer(5); // 从队尾入队列 System.out.println(获取队列中有效元素个数为 q.size()); System.out.println(获取队头元素为 q.peek()); // 获取队头元素 q.poll(); System.out.println(获取队头出队列元素为 q.poll()); // 从队头出队列并将删除的元素返回 if(q.isEmpty()){ System.out.println(获取队列中有效元素个数为队列空); }else{ System.out.println(获取队列中有效元素个数为 q.size()); } 获取队列中有效元素个数为5 获取队头元素为1 获取队头出队列元素为2 获取队列中有效元素个数为32.03 队列模拟实现队列中既然可以存储元素那底层肯定要有能够保存元素的空间通过前面线性表了解到常见的空间类型有两种顺序结构和链式结构。队列的实现使用顺序结构还是链式结构好简单记「小而固定用数组大而动态用链表」。class Queue { // 双向链表节点 public static class ListNode{ ListNode next; ListNode prev; int value; ListNode(int value){ this.value value; } } ListNode first; // 队头 ListNode last; // 队尾 int size 0; // 入队列---向双向链表位置插入新节点 public void offer(int e){ ListNode newNode new ListNode(e); if(first null){ first newNode; // last newNode; }else{ last.next newNode; newNode.prev last; // last newNode; } last newNode; size; } // 出队列---将双向链表第一个节点删除掉 public Object poll(){ // 1. 队列为空 // 2. 队列中只有一个元素----链表中只有一个节点---直接删除 // 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除 int value 0; if(first null){ return null; }else if(first last){ last null; first null; }else{ value first.value; first first.next; first.prev.next null; first.prev null; } --size; return value; } // 获取队头元素---获取链表中第一个节点的值域 public Object peek(){ if(first null){ return null; } return first.value; } public int size() { return size; } public boolean isEmpty(){ return first null; } }2.04 循环队列实际应用中有时还会使用一种队列叫循环队列。数组下标循环的小技巧下标最后再往后(offset 小于 array.length): index (index offset) % array.length![[Pasted image 20260312221416.png]]2. 下标最前再往前(offset 小于 array.length): index (index array.length - offset) % array.length![[Pasted image 20260312221509.png]]如何区分空与满① 通过添加 size 属性记录 ②保留一个位置 ③使用标记![[Pasted image 20260312221812.png]]2.05双端队列 (Deque)Deque 是Double Ended Queue的缩写直译是「双端队列」—— 它打破了普通队列「只能队尾入、队头出」的限制允许在队列的头部和尾部同时进行入队 / 出队操作。![[Pasted image 20260312222009.png]]2.051Deque 的核心特点双向操作队头First和队尾Last都支持add/remove/get操作接口定位Java 中Deque是接口继承自Queue同时兼容Queue队列和Stack栈的核心功能操作分类和Queue类似Deque 的操作也分「抛异常」和「返回特殊值」两类推荐用返回特殊值的更安全。2.502、Deque 核心操作按功能分类1. 作为「普通队列」使用操作抛异常返回特殊值说明队尾入队add(e)offer(e)等价于addLast(e)/offerLast(e)队头出队remove()poll()等价于removeFirst()/pollFirst()查看队头element()peek()等价于getFirst()/peekFirst()2. 作为「栈」使用操作抛异常返回特殊值说明栈顶入栈push(e)-无对应等价于addFirst(e)栈顶出栈pop()-无对应等价于removeFirst()查看栈顶peek()peekFirst()栈为空时peek()返回null3. 纯双端操作队头 / 队尾自由操作操作抛异常返回特殊值说明队头入队addFirst(e)offerFirst(e)队头添加元素队尾入队addLast(e)offerLast(e)队尾添加元素同普通队列队头出队removeFirst()pollFirst()移除并返回队头元素队尾出队removeLast()pollLast()移除并返回队尾元素查看队头getFirst()peekFirst()仅查看队头不移除查看队尾getLast()peekLast()仅查看队尾不移除双端队列的线性实现public class test { public static void main(String[] args) { DequeString deque new ArrayDeque(); // 1. 作为普通队列使用队尾入、队头出 deque.offerLast(A); // 队尾入队 → [A] deque.offerLast(B); // 队尾入队 → [A, B] System.out.println(deque.pollFirst()); // 队头出队 → 输出 A队列变为 [B] // 2. 作为栈使用队头入、队头出 deque.push(C); // 入栈等价于 addFirst→ [C, B] deque.push(D); // 入栈 → [D, C, B] System.out.println(deque.pop()); // 出栈 → 输出 D队列变为 [C, B] // 3. 双端操作队尾出队 System.out.println(deque.pollLast()); // 输出 B队列变为 [C] // 4. 查看队头/队尾 System.out.println(deque.peekFirst()); // 输出 C } }双端队列的链式实现public class test { public static void main(String[] args) { DequeInteger deque new LinkedList(); // 队头入队 deque.addFirst(1); // [1] // 队尾入队 deque.addLast(2); // [1, 2] // 移除队尾 deque.removeLast(); // [1] // 查看队头 System.out.println(deque.getFirst()); // 输出 1 } }