廊坊建站网站三要

廊坊建站,网站三要,老山网站建设,wordpress 计算器插件前言 今天接着和大家分享数据结构中栈相关的知识,特别是与java集合框架相关的内容,如果有了顺序表与链表的基础,接触今天分享的会是相当容易上手的,话不多说,让我们开始吧一、java集合框架与StackJava 集合框架是 Java 中用于存储和操作一组对象的体系#xff0c;核心分为 Col…前言今天接着和大家分享数据结构中栈相关的知识,特别是与java集合框架相关的内容,如果有了顺序表与链表的基础,接触今天分享的会是相当容易上手的,话不多说,让我们开始吧一、java集合框架与StackJava 集合框架是 Java 中用于存储和操作一组对象的体系核心分为Collection单列集合和Map双列集合核心接口与分类Collection单列集合是所有单列集合的根接口定义了集合的基本操作增删改查、遍历等。子接口List有序可重复、Set无序不可重复、Queue队列。Map双列集合存储键值对Key-ValueKey 唯一、Value 可重复。子接口SortedMap键有序。StackStack 的继承关系从提供的类图看从类图可知Stack 继承自 Vector属于 List 分支而Vector又继承自AbstractList、实现了List接口。因此Stack本质是基于动态数组实现的同时继承了Vector的线程安全特性方法被synchronized修饰。Stack 的核心特性LIFO后进先出新元素从 “栈顶” 加入取出元素也只能从栈顶操作最后加入的元素最先被取出。动态扩容底层基于Vector的动态数组容量不足时会自动扩容默认扩容为原容量的 2 倍。线程安全由于继承自VectorStack的方法如push、pop都被synchronized修饰多线程环境下不会出现并发问题但性能较低。二、啥是栈从数据结构的角度来说栈Stack是一种遵循后进先出Last In First Out简称 LIFO原则的线性数据结构只允许在一端进行元素的插入和删除操作这个操作端被称为栈顶另一端则被称为栈底。就是说栈就是一种线性的数据结构,比如数组,链表.后面会具体说一下这两个的实现形式.其中是满足先进后出的原则,大家可以想象一下手枪弹夹装弹的场景.核心概念栈顶Top栈的操作端所有的插入入栈、删除出栈、查看操作都只能在这一端进行。栈底Bottom栈的固定端元素从栈顶入栈后会依次向栈底方向排列栈底元素是最先入栈且最后出栈的元素。空栈没有任何元素的栈此时进行出栈或查看栈顶操作通常会触发异常。核心操作栈的操作非常简洁只有两个核心基础操作以及两个常用辅助操作操作名称功能描述注意事项入栈Push将元素添加到栈顶若栈已满顺序栈会触发“栈溢出”出栈Pop移除并返回栈顶元素若栈为空会触发“下溢”异常查看栈顶Peek/Top返回栈顶元素但不移除若栈为空触发异常判空IsEmpty判断栈中是否有元素无说明栈不支持在中间位置插入、删除或访问元素这是它区别于数组、链表等线性结构的关键特征。栈的两种实现方式从数据结构的底层存储来看栈有两种常见实现方式顺序栈基于数组实现原理用一段连续的内存空间数组存储栈元素用一个变量标记栈顶的位置如top指针初始值为-1表示空栈。入栈top指针加 1将元素存入数组对应下标位置。出栈返回数组top下标对应的元素top指针减 1。优缺点访问速度快但存在固定容量限制满栈后扩容需要额外开销。典型例子Java 中遗留的Stack类、ArrayDeque类。链式栈基于链表实现原理用链表存储栈元素一般选用带头结点的单链表栈顶对应链表的头结点之后的第一个节点避免复杂的尾操作。入栈将新节点插入到链表头部栈顶。出栈删除链表头部的节点返回其值。优缺点容量可以动态增长不存在溢出问题但每个元素需要额外存储指针空间开销略大。典型例子自定义链式栈结构。三、常用代码手动实现(数组类型实现)这一部分的逻辑是较为简单的,小伙伴们如果是第一次接触,非常建议大家上手实现一下~我就都分成一个一个小的代码块了 大家在学习的时候也可以分成基本成员变量,成员方法,**辅助方法(在成员方法中被调用的小方法)**进行学习基本方法publicclassMyStackE{publicObject[]elem;//标记最后一个publicintusedSize;publicstaticfinalintDEFAULT_CAPACITY5;publicMyStack(){this.elemnewObject[DEFAULT_CAPACITY];}//入栈方法publicvoidpush(Eval){if(isFull()){elemArrays.copyOf(elem,2*elem.length);}elem[usedSize]val;usedSize;}publicbooleanisFull(){returnusedSizeDEFAULT_CAPACITY;}publicEpop(){if(isEmpty()){returnnull;}Eret(E)elem[usedSize-1];usedSize--;returnret;}publicbooleanisEmpty(){returnusedSize0;}publicEpeek(){if(isEmpty()){returnnull;}return(E)elem[usedSize-1];}四、逆波兰表达式逆波兰表达式Reverse Polish Notation简称 RPN也叫后缀表达式是一种不需要括号来标识运算优先级的算术表达式表示方法。它的核心特点是运算符位于其对应的所有操作数之后。与之相对的我们日常使用的3 4、(2 3) × 5这类表达式叫中缀表达式——运算符位于两个操作数中间。中缀转后缀一、 中缀表达式 vs 逆波兰表达式通过表格可以更直观地理解两者的转换关系中缀表达式逆波兰表达式计算逻辑3 43 4 先取 3 和 4再执行加法(2 3) × 52 3 5 ×先算 23结果再和 5 相乘3 4 × 23 4 2 × 先算 4×2结果再和 3 相加(3 4) × (5 - 2)3 4 5 2 - ×先算 34 和 5-2再将两个结果相乘二、 逆波兰表达式的计算规则逆波兰表达式的计算非常适合用栈来实现步骤如下从左到右扫描表达式中的每个元素数字或运算符。遇到数字直接压入栈中。遇到运算符从栈中弹出两个元素注意顺序先弹出的是右操作数后弹出的是左操作数用该运算符对两个数进行计算再将计算结果压入栈中。扫描结束后栈中剩余的唯一元素就是表达式的最终结果。四、 逆波兰表达式的优势无需括号完全通过运算符的位置来体现运算优先级没有歧义。计算高效用栈实现的计算过程时间复杂度为O(n)O(n)O(n)逻辑简单适合计算机处理。编译器常用很多编译器在处理算术表达式时会先将中缀表达式转为逆波兰表达式再进行计算避免了复杂的括号和优先级判断。五、根据逆波兰表达式求值publicintevalRPN(String[]tokens){StackIntegerstacknewStack();for(Stringx:tokens){//判断是运算符号还是数值if(!isOperations(x)){//不是运算符stack.push(Integer.parseInt(x));}else{//是运算符intrightstack.pop();intleftstack.pop();//直到具体的操作符switch(x){case:stack.push(leftright);break;case-:stack.push(left-right);break;case*:stack.push(left*right);break;case/:stack.push(left/right);break;}}}returnstack.pop();}publicbooleanisOperations(Stringx){if(x.equals()||x.equals(-)||x.equals(*)||x.equals(/)){returntrue;}returnfalse;}五、 总结虽然栈的方法不是很多,但是栈这种独特的思想在编程题目中有着不少的应用,大家可以找两个感受感受~到这里我的分享就先结束了~,希望对你有帮助我是dylan 下次见~无限进步