文章目录一、栈Stack后进先出的线性结构1.1 概念与操作特性1.2 Java中Stack类的使用方法1.3 栈的底层模拟实现1.3.1 底层结构选择1.3.2 完整实现代码1.4 概念辨析栈、虚拟机栈、栈帧二、队列Queue先进先出的线性结构2.1 核心概念与操作特性2.2 Java中Queue接口的使用方法2.2.1 接口特性与实现类2.2.2 核心方法与功能2.2.3 代码示例与执行逻辑2.3 队列的底层模拟实现2.3.1 底层结构选择2.3.2 完整实现代码基于双向列表2.5 双端队列Deque灵活的双向操作结构2.5.1 概念与特性2.5.2 Java中的Deque接口使用一、栈Stack后进先出的线性结构1.1 概念与操作特性栈是仅允许在固定一端进行插入和删除操作的特殊线性表关键术语进行数据操作的一端称为栈顶Top另一端称为栈底Bottom。核心原则遵循后进先出LIFOLast In First Out规则即最后进入栈的元素会最先被取出类似日常生活中叠放的盘子——新盘子放在顶端取盘子时也从顶端开始 。基础操作压栈Push又称进栈、入栈指将元素插入栈顶的操作 。出栈Pop指将栈顶元素删除并取出的操作出栈操作仅能在栈顶进行 。1.2 Java中Stack类的使用方法Java中的Stack类提供了栈的完整实现其核心方法及功能如下表所示 方法功能描述返回值/说明Stack()构造一个空的栈空栈对象E push(E e)将元素e入栈操作位置为栈顶返回被入栈的元素eE pop()移除栈顶元素并返回该元素栈顶元素若栈为空可能抛出异常E peek()获取栈顶元素但不删除该元素栈顶元素若栈为空可能抛出异常int size()统计栈中有效元素的个数非负整数代表元素数量boolean empty()检测栈是否为空栈空返回true否则返回false代码示例与执行逻辑publicstaticvoidmain(String[]args){StackIntegersnewStack();s.push(1);// 栈内元素[1]s.push(2);// 栈内元素[1,2]s.push(3);// 栈内元素[1,2,3]s.push(4);// 栈内元素[1,2,3,4]System.out.println(s.size());// 输出4有效元素个数System.out.println(s.peek());// 输出4栈顶元素为4s.pop();// 4出栈栈内剩余[1,2,3]System.out.println(s.pop());// 输出33出栈栈内剩余[1,2]if(s.empty()){System.out.println(栈空);}else{System.out.println(s.size());// 输出2}}1.3 栈的底层模拟实现1.3.1 底层结构选择从Java集合框架的继承关系Stack类继承自Vector类而Vector是线程安全的动态顺序表因此栈的底层本质是基于数组实现的 。基于数组实现栈时需维护两个核心要素存储元素的数组array和记录有效元素个数的size同时作为栈顶指针size-1即为栈顶元素下标。1.3.2 完整实现代码importjava.util.Arrays;publicclassMyStack{int[]array;// 存储栈元素的数组intsize;// 栈中有效元素个数栈顶指针publicMyStack(){arraynewint[3];}// 压栈将元素e入栈返回epublicintpush(inte){ensureCapacity();// 确保数组容量充足不足则扩容array[size]e;// 元素存入栈顶栈顶指针后移returne;}// 出栈移除并返回栈顶元素publicintpop(){intepeek();// 先获取栈顶元素若栈空抛出异常size--;// 栈顶指针前移逻辑删除栈顶元素returne;}// 获取栈顶元素不删除元素仅返回值publicintpeek(){if(empty()){// 检测栈是否为空thrownewRuntimeException(栈为空无法获取栈顶元素);}returnarray[size-1];// 返回栈顶元素size-1为栈顶下标}// 统计有效元素个数publicintsize(){returnsize;}// 检测栈是否为空publicbooleanempty(){returnsize0;}// 动态扩容当元素个数达到数组容量时将容量翻倍privatevoidensureCapacity(){if(sizearray.length){arrayArrays.copyOf(array,size*2);}}}逻辑说明扩容机制通过ensureCapacity方法实现动态扩容当size等于数组长度时使用Arrays.copyOf将数组容量翻倍避免元素溢出 。空栈处理peek方法中添加空栈检测若栈为空则抛出运行时异常保证操作安全性1.4 概念辨析栈、虚拟机栈、栈帧三者分属不同层面极易混淆文档特别强调了其区别 栈本文讨论的数据结构是一种逻辑结构用于存储数据并遵循LIFO规则。虚拟机栈Java虚拟机的内存区域属于运行时数据区用于存储方法调用的相关信息。栈帧虚拟机栈中的基本存储单位每个方法被调用时会创建一个栈帧包含局部变量表、操作数栈、动态链接等信息方法执行完毕后栈帧出栈。二、队列Queue先进先出的线性结构2.1 核心概念与操作特性队列是仅允许在一端插入、另一端删除的特殊线性表其核心要素与规则如下关键术语进行插入操作的一端称为队尾Tail/Rear进行删除操作的一端称为队头Head/Front。核心原则遵循先进先出FIFOFirst In First Out规则即先进入队列的元素会最先被取出类似日常生活中的排队——先排队者先接受服务 。基础操作入队列Enqueue将元素插入队尾的操作 。出队列Dequeue将队头元素删除并取出的操作 。2.2 Java中Queue接口的使用方法2.2.1 接口特性与实现类在Java中Queue是一个接口无法直接实例化其底层通常通过链表实现。由于LinkedList类实现了Queue接口因此实例化时需使用LinkedList。2.2.2 核心方法与功能Queue接口的核心方法及功能如下表所示 方法功能描述返回值/说明boolean offer(E e)将元素e入队列操作位置为队尾入队成功返回true失败返回falseE poll()移除队头元素并返回该元素队头元素若队为空返回nullE peek()获取队头元素但不删除该元素队头元素若队为空返回nullint size()统计队列中有效元素的个数非负整数代表元素数量boolean isEmpty()检测队列是否为空队空返回true否则返回false2.2.3 代码示例与执行逻辑publicstaticvoidmain(String[]args){QueueIntegerqnewLinkedList();q.offer(1);// 队尾入队 [1]q.offer(2);// [1,2]q.offer(3);// [1,2,3]q.offer(4);// [1,2,3,4]q.offer(5);// [1,2,3,4,5]System.out.println(q.size());// 5System.out.println(q.peek());// 1q.poll();// 1出队[2,3,4,5]System.out.println(q.poll());// 22出队[3,4,5]if(q.isEmpty()){System.out.println(队列空);}else{System.out.println(q.size());// 3}}上述代码中入队操作均在队尾进行出队操作均在队头进行完全遵循FIFO原则 。2.3 队列的底层模拟实现2.3.1 底层结构选择队列的底层实现可选择顺序结构或链式结构但链式结构更优。原因在于顺序结构的队头删除操作会导致后续所有元素前移时间复杂度为O(n)链式结构的队头删除、队尾插入操作均可在O(1)时间内完成维护队头first和队尾last指针实现。2.3.2 完整实现代码基于双向列表publicclassMyQueue{publicstaticclassListNode{ListNodenext;ListNodeprev;intvalue;ListNode(intvalue){this.valuevalue;}}ListNodefirst;ListNodelast;intsize0;// 入队列publicvoidoffer(inte){ListNodenewNodenewListNode(e);if(firstnull){firstnewNode;}else{last.nextnewNode;newNode.prevlast;}lastnewNode;size;}// 出队列publicIntegerpoll(){if(firstnull){returnnull;}intvaluefirst.value;if(firstlast){firstnull;lastnull;}else{firstfirst.next;first.prev.nextnull;first.prevnull;}size--;returnvalue;}// 获取队头元素publicIntegerpeek(){if(firstnull){returnnull;}returnfirst.value;}// 有效元素个数publicintsize(){returnsize;}// 判空publicbooleanisEmpty(){returnfirstnull;}}2.5 双端队列Deque灵活的双向操作结构2.5.1 概念与特性双端队列Deque全称“double ended queue”是一种允许在两端进行入队和出队操作的队列兼具栈和队列的特性 。其操作灵活性体现在可从队头入队/出队可从队尾入队/出队。2.5.2 Java中的Deque接口使用接口与实现类Deque是Java中的接口使用时需实例化其实现类常用LinkedList链式实现和ArrayDeque线性实现 。替代栈与队列在实际工程中Deque的使用频率远高于单独的Stack和Queue因其可灵活实现两种结构的功能 用Deque实现栈默认操作栈顶即双端队列的一端DequeIntegerstacknewArrayDeque();用Deque实现队列默认队尾入、队头出DequeIntegerqueuenewLinkedList();