数据结构学习--逆波兰计算器
数据结构学习--逆波兰计算器完成一个逆波兰计算器，要求完成如下任务：（1）输入一个逆波兰表达式（后缀表达式），使用栈 (Stack),计算其结果 （2）支持小括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算。思路分析：例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:(1). 从左至右扫描，将3和4压入堆栈；(2). 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；(3). 将5入栈；(4). 接下来是×运算符，因此弹出5和7，计算出7×5=...
数据结构学习--逆波兰表达式
数据结构学习--逆波兰表达式一、前缀表达式（1）前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前 （2）举例说明： (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6前缀表达式的计算机求值从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素和次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果例如：(3+4) X 5-6对应的前缀表达式就是- X + 3 4 5 6, 针对前缀表达式求值步骤如下： 1. 从右至左扫描，将6、5、4、3压入堆栈 2. 遇到+运算符，因...
数据结构学习--栈实现综合计算器（中缀表达式）
数据结构学习--栈实现综合计算器（中缀表达式）使用栈来实现综合计算器思路图解使用栈完成表达式的计算 思路通过一个 index 值（索引），来遍历我们的表达式如果我们发现是一个数字,就直接入数栈如果发现扫描到是一个符号, 就分如下情况3.1 如果发现当前的符号栈为 空，就直接入栈3.2 如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符， 就需要从数栈中pop出两个数,在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈， 如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈.当表达式扫描完毕，就顺序的从 数栈和符号栈...
数据结构学习--栈（一）
数据结构学习--栈（一）一、栈的一个实际需求请输入一个表达式计算式:[7*2*2-5+1-5+3-3] 点击计算【如下图】请问: 计算机底层是如何运算得到结果的？ 注意不是简单的把算式列出运算,因为我们看这个算式 7 2 2 - 5, 但是计算机怎么理解这个算式的(对计算机而言，它接收到的就是一个字符串)，我们讨论的是这个问题。-> 栈二、栈的介绍（1）栈的英文为(stack)（2）栈是一个先入后出(FILO-First In Last Out)的有序列表。（3）栈（stack）是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化...
数据结构学习--单向环形链表
数据结构学习--单向环形链表一、单向环形链表的应用场景Josephu(约瑟夫、约瑟夫环) 问题Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。提示：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。二、单向环...
数据结构学习--双向链表
数据结构学习--双向链表一、管理单向链表的缺点分析（1）单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找（2）单向链表不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除，所以前面我们在单链表删除节点时，总是找到temp,temp是待删除节点的前一个节点二、双向链表如何完成遍历，添加，修改和删除示意图思路：1.遍历方法和单链表一样，只是可以向前，也可以向后查找2.添加（默认添加到双向链表的最后）先找到双向链表的最后这个节点temp.next=newHeroNodenewHeroNode.pre=temp;3.修改思路和原来的单向链表一样4.删除因为是双向链表，因此，...
数据结构学习--单链表面试题
数据结构学习--单链表面试题前言本篇将讲述之前新浪、百度、腾讯的单链表的面试题单链表面试题（1）求单链表中有效节点的个数代码//方法：获取到单链表的节点的个数（如果是带头节点的链表，需求不统计头节点） public static int getLength(HeroNode head){ if(head.next == null){//空链表 return 0; } int length = 0; //定义一个辅助的变量，这里我们没有统计头节点 HeroNode cur = head.next; while(cur != n...
数据结构学习--链表
数据结构学习--链表一、链表(Linked List)介绍链表是有序的列表，但是它在内存中是存储如下：上图总结（1）链表是以节点的方式来存储，是链式存储（2）每个节点包含data域，next域：指向下一个节点。（3）如图：发现链表的各个节点不一定是连续存储（4）链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定单链表（带头节点）逻辑结构示意图如下二、单链表的应用实例使用带head头的单向链表实现 水浒英雄排行榜管理完成对英雄人物的增删改查操作。（1）第一种方法在添加英雄时，直接添加到链表的尾部思路分析示意图：添加（创建）思路：1.先创建一个head头节点，作用就是表示单链表的头...
数据结构学习--环形队列（二）
数据结构学习--环形队列（二）前言上篇中，使用数组来模拟队列会出现数组使用一次就不能使用，没有达到复用效果的问题，本篇通过数组模拟环形队列来解决该问题。概述数组模拟环形队列对前面的数组模拟队列的优化，充分利用数据，因此将数组看做是一个环形的。（通过取模的方式来实现即可）分析说明：尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定，这个在做判断队列满的时候需要注意(rear+1)%maxSize==front [满]rear==front[空]分析示意图：思路如下：front变量的含义做一个调整：front就指向队列的第一个元素，也就是说arr[front]就是队列的第一个元...
数据结构学习--队列（一）
数据结构学习--队列（一）前言在队列开篇之前使用一个小案例来感受一下生活中队列的使用场景：去银行办业务，然后取挂号排队。概述队列介绍1.队列是一个有序的列表，可以用数组或 链表来实现。2.遵循先入先出的原则，即：先存入队列的数据，要先取出。后存入的要后取出示意图：使用数组模拟队列的示意图数组模拟队列思路1.队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。 2.因为队列的输出、输入是分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着...