文章目录1.栈 Stack1.1 栈1.2 队列的三种实现1.3 Stack 典型 Oj 题有效的括号逆波兰表达式求值1.4 栈、虚拟机栈、栈帧的区分2.队列 Queue2.1 什么叫队列2.2 如何使用队列2.3 模拟实现队列 Queue1.数组实现2.单链表实现3.双链表实现2.4 循环队列2.5 双端队列 Deque1.栈 Stack1.1 栈栈是一种特殊的线性表他只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的元素遵循先进后出的原则。压栈数据进入栈中称为进栈/压栈/入栈出栈栈的删除操作叫做出栈其概念图如下1.2 队列的三种实现栈的方法不多我们可以查看查看 Stack 源码中的方法其方法说明如下方法返回类型功能push(E e)E将 e 入栈并返回 epop()E将栈顶元素出栈并返回peek()E获取栈顶元素size()int获取栈中有效元素个数empty()boolean检测栈是否为空Java 中栈的常见实现有三种实现方式备注Stack老旧但线程安全带锁性能相对较低ArrayDeque非线程安全性能极高LinkedList可当作栈使用但作为栈使用时性能通常略逊于ArrayDeque要想了解栈模拟栈的实现是很有必要的packagemyStack;importexception.EmptyStackException;importjava.util.Arrays;publicclassMyStack{publicint[]elem;publicintusedSize;publicMyStack(){this.elemnewint[10];}publicvoidpush(intval){if(isFull()){this.elemArrays.copyOf(elem,2*elem.length);}elem[usedSize]val;}publicbooleanisFull(){returnusedSizeelem.length;}publicintpop(){if(isEmpty()){thrownewEmptyStackException(栈中元素为空);}intvalelem[usedSize-1];//取得栈中的最后值usedSize--;//取消对最后值的索引returnval;}publicintpeek(){if(isEmpty()){thrownewEmptyStackException(栈中元素为空);}returnelem[usedSize-1];}publicbooleanisEmpty(){returnusedSize0;}publicintsearch(intval){for(intiusedSize-1;i0;i--){if(elem[i]val){// 返回距离栈顶的距离。栈顶本身返回 1其下方返回 2以此类推returnusedSize-i;}}return-1;}}代码可详见于远程仓库1.3 Stack 典型 Oj 题20. 有效的括号 - 力扣LeetCode150. 逆波兰表达式求值 - 力扣LeetCodeLeecode 最小栈Leecode 用队列实现栈Leecode 用栈实现队列有效的括号对于此题我们可以先创建几个例子如([])、([)]、(()据此可以构建该模型。既然是要左括号匹配右括号我们可以思考假设先遇到左括号正常返回 true 的例子并能够以最近遇到的左括号去匹配右括号只能是通过**栈Stack**这个数据结构来完成了从左至右如图 1遍历字符串if {先遇到左括号push 压栈}else {遇到右括号if{ stack 为空返回 false 结束}else {栈不为空,peek()匹配如匹配则 pop()弹出否则 false}}注以上为此题抽象思路,但稍有不足假设左括号过多如图三我们还需最后检查栈是否为空// 有效的括号publicbooleanisValid(Strings){StackCharacterstacknewStack();for(inti0;is.length();i){charchs.charAt(i);if(ch(||ch[||ch{){// 如果匹配进行压栈stack.push(ch);}else{if(stack.empty()){returnfalse;}// 若不为空继续判断是否匹配charch2stack.peek();// 从栈中取出元素,即不走上面的if了为右括号if(ch)ch2(||ch}ch2{||ch]ch2[){stack.pop();}else{// 若不匹配上述returnfalse;}}}//处理匹配完右括号后左括号是否多出来if(!stack.empty()){returnfalse;}returntrue;}逆波兰表达式求值我们先简单了解以下波兰表达式概念如下给出一个中缀表达式a b * c (d * e f) * g,转换为后缀表达式a b c * d e * f g * .其转换过程如下将以下每个运算符号都放在括号中随后将每个运算符号移除当前所处的括号外得到将括号去掉便得到我们的后缀表达式了而如何按照原先规则运算就是我们这次讲的题了输入tokens [“2”,“1”,“”,“3”,“*”]输出9解释该算式转化为常见的中缀算术表达式为((2 1) * 3) 9题目给出这样一个示例可以想到每遍历到操作数就提取两个数字根据上述思路我们可以想到用栈来存储每次遍历时遇到的数字当遇到运算符时就弹出栈顶的两个元素进行该运算符的计算注注意两个数字的位置不要搞错第一个数字是右操作数第二个数字是左操作数由上述思路得出// 逆波兰表达式求值publicintevalRPN(String[]tokens){StackIntegerstacknewStack();// 遍历字符串for(Stringx:tokens){// 匹配是否是操作符号if(!isOperator(x)){// 如果是数字就压栈intnumInteger.parseInt(x);stack.push(num);}else{// 不是数字就运算intval2stack.pop();intval1stack.pop();switch(x){case:stack.push(val1val2);break;case-:stack.push(val1-val2);break;case*:stack.push(val1*val2);break;case/:stack.push(val1/val2);break;}}}returnstack.pop();}privatebooleanisOperator(Stringch){if(ch.equals()||ch.equals(-)||ch.equals(*)||ch.equals(/)){returntrue;}returnfalse;}1.4 栈、虚拟机栈、栈帧的区分栈由本节知道栈是一种数据结构遵循先进后出的原则虚拟机栈虚拟机栈是 JVM 的一块运行时内存区域其中虚拟机栈 每个线程私有的调用栈虚拟机栈主要存的就是我们要说的栈帧栈帧栈帧是方法运行时的数据结构即每次方法调用产生的数据单元也就是说每调用一个方法 - 创建一个栈帧一个栈帧里通常包含局部变量表、操作数栈、动态链表、方法返回地址2.队列 Queue2.1 什么叫队列队列只允许在队尾进行元素插入在队头进行元素删除的一种特殊线性表队列遵循先进先出的原则。对于队列的概念我们可以抽象理解为如下图类似倒置的栈但与栈不同2.2 如何使用队列java 中队列与栈不同的是栈是一个类而队列是一个接口。因此我们实现队列的时候就不能像栈一样 new 一个它本身而是要通过常用的** LinkedList**(双向链表)、ArrayDeque(动态数组)、PriorityQueue(堆)…实现类来实现。QueueIntegerqnewLinkedList();QueueIntegerqnewArrayDeque();QueueIntegerqnewPriorityQueue();...队列 Queue 的结构如下队列的基本操作方法方法功能boolean offer(E e)/add(E e)入队 enqueuepoll()/remove(): E出队 dequeuepeek()/element(): E查看队头boolean isEmpty()检查队列是否为空int size()获取队列中的有效元素个数其中isEmpty()size()这两个方法是定义在父类 Collection 中。另外上面存在两种一样功能的方法区别差异不大2.3 模拟实现队列 Queue在了解完队列的方法后进一步学习其方法加深对队列的理解补充顺序结构数据在内存中连续存储链式结构数据在内存中不需要连续每个元素通过指针应用连接起来在前面学习完的顺序结构数组、ArrayList…和 链式结构LinkedList、单链表…之后对于队列的实现我们在后面会说明使用哪个实现会更好队列的方法十分简单代码如下没有很复杂的逻辑。publicclassMyQueue{staticclassListNode{publicintval;publicListNodeprev;publicListNodenext;publicListNode(intval){this.valval;}}publicListNodefirstnull;publicListNodelastnull;publicintusedSize0;// 入队列尾入publicvoidoffer(intval){ListNodenodenewListNode(val);if(isEmpty()){firstlastnode;}else{last.nextnode;node.prevlast;lastlast.next;}usedSize;}// 出队列头出publicintpoll(){if(isEmpty()){return-1;}intvalfirst.val;firstfirst.next;if(first!null){// 将first的前驱置空first.prevnull;}usedSize--;returnval;}// 获取队头元素publicintpeek(){if(isEmpty()){return-1;}returnfirst.val;}publicbooleanisEmpty(){returnusedSize0;}从逻辑上顺序结构数组、链式结构单、双链表都可以实现队列 Queue。我们可以对比一下1.数组实现队头需要 front 标记队尾需要 rear 标记必须使用循环数组才能充分利用空间时间复杂度入队 O(1)出队 O(1)随机访问O(1)可以发现其优/缺点优内存连续空间占用少、随机访问快缺必须事先指定数组容量或动态扩容2.单链表实现队头 head 指向队头节点last 指向队尾节点入队采用尾插法出队可删除头节点注就算有尾节点的标记也不能从头节点入队因为删除还是需要找对后一个节点的前一个节点时间复杂度入队 O(1)出队 O(1)随机访问O(n)3.双链表实现与单链表相同队头 head 指向队头节点last 指向队尾节点入队采用尾插法出队可删除头节点时间复杂度入队 O(1)出队 O(1)随机访问O(n)但是双链表可以双向遍历支持在两端操作特性数组单链表双链表存储连续不连续不连续内存占用少中多入队/出队O(1)O(1)O(1)随机访问O(1)O(n)O(n)是否需要扩容是或固定容量否否CPU缓存友好高低低适用场景高性能、容量固定或可扩容容量不确定、出入队灵活双端操作、容量不确定2.4 循环队列循环队列是顺序队列的一种优化它解决了顺序队列出对后空间浪费的问题。普通顺序队列出队后队头向后移动数组前面出现空闲空间但无法复用循环队列把数组看作环形当rear到达数组末尾时如果前面有空余位置就可以回到数组开头继续存放元素对于循环队列我们给出以下定义队列用数组存储front 指向队头rear 指向队尾的下一个位置由此我们可以得到循环公式入队时rear (rear 1) % capacity出队时front (front 1) % capacity队列满条件(rear 1) % capacity front队列空条件rear front对于循环数组判断是否已满有三种方法通过添加 usedSize 属性记录保留一个位置使用标记定义 boolean 类型元素我们拿第三个标记法举例// 使用不浪费空间方法classMyCircularQueue{publicintfront;publicintrear;publicint[]elem;privatebooleanisFullFlg;publicMyCircularQueue(intk){elemnewint[k];front0;rear0;isFullFlgfalse;}// 入队publicbooleanenQueue(intvalue){if(isFull()){returnfalse;}elem[rear]value;rear(rear1)%elem.length;// rear往后移一位if(rearfront){isFullFlgtrue;}returntrue;}// 出队publicbooleandeQueue(){if(isEmpty()){returnfalse;}front(front1)%elem.length;// front往后移一位isFullFlgfalse;// 只要成功出队则队列不可能满returntrue;}// 返回front指向的元素publicintFront(){if(isEmpty())return-1;returnelem[front];}// 返回rear指向的元素publicintRear(){if(isEmpty())return-1;intindex(rear0)?elem.length-1:rear-1;returnelem[index];}publicbooleanisEmpty(){return(rearfront)!isFullFlg;}publicbooleanisFull(){returnisFullFlg;}}622. 设计循环队列 - 力扣LeetCode2.5 双端队列 DequeDequeDoubleEndedQueue双端队列是指允许两端都可以进行入队和出队操作的队列。即说明元素可从队头出入队也可以从队尾出入队。双端队列可以用顺序结构或链式结构实现DequeIntegerstacknewArrayDeque();//双端队列的线性实现DequeIntegerqueuenewLinkedList();//双端队列的链式实现以上是我关于Java的笔记分享感谢你读到这里这也是我学习路上的一个小小记录。希望以后回头看时能看到自己的成长~