常见数据结构和算法实现(排序/查找/数组/链表/栈/队列/树/递归/海量数据处理/图/位图/Java版数据结构)

常见数据结构和算法实现(排序/查找/数组/链表/栈/队列/树/递归/海量数据处理/图/位图/Java版数据结构…

常见数据结构和算法实现(排序/查找/数组/链表/栈/队列/树/递归/海量数据处理/图/位图/Java版数据结构)

数据结构和算法作为程序员的基本功,一定得稳扎稳打的学习,我们常见的框架底层就是各类数据结构,例如跳表之于redis、B+树之于mysql、倒排索引之于ES,熟悉了底层数据结构,对框架有了更深层次的理解,在后续程序设计过程中就更能得心应手。掌握常见数据结构和算法的重要性显而易见,本文主要讲解了几种常见的数据结构及基础的排序和查找算法,最后对高频算法笔试面试题做了总结。本文会持续补充,希望对大家日常学习或找工作有所帮忙。

  • 程序中数据大致有四种基本逻辑结构:集合(同属一个集合)/线性关系(一对一)/树形结构(一对多)/图状结构或网状结构(多对多)
  • 物理存储结构:顺序存储结构/非顺序结构(链式存储/散列结构)
  • 算法的设计取决于逻辑结构;算法的实现依赖于存储结构

有3点比较重要 (王争)

  • 1、直接好处是能够有写出性能更优的代码;数据结构:存储;算法:计算
    • 算法是程序的灵魂,优秀的程序可以在海量数据计算时,依然保持高速计算。
  • 2、算法,是一种解决问题的思路和方法,有机会应用到生活和事业的其他方面;
  • 3、长期来看,大脑思考能力是个人最重要的核心竞争力,而算法是为数不多的能够有效训练大脑思考能力的途径之一。

推荐的书籍及教程
《大话数据结构 程杰》入门
《算法图解》
数据结构与算法分析:Java语言描述》(大学课本 伪代码)
剑指offer》 使用的C++语言来实现的,现在我不怎么使用了
程序员代码面试指南:IT名企算法与数据结构题目最优解》左程云,现在正在看的书
《编程珠玑》(对大数据量处理的算法)
《编程之美》(超级难)
《算法导论》(很厚很无聊)
《算法第四版》(推荐 本书没有动态规划)
数据结构与算法 极客时间》 王争google
《算法帝国》
《数学之美》
《算法之美》(闲暇阅读) https://github.com/wangzheng0822/algo
《计算机程序设计艺术》面试必刷的宝典
《图解Java数据结构》韩顺平
《数据结构与算法之美》王争

倘若是在日常开发中,算法的基本逻辑,优缺点、适用场景是更为重要的。

如果是考察技术基础,考核的范围应该是算法的基本逻辑,优缺点、适用场景因为这些技术点在后续具体应用中选择合适的算法来解决问题的时候很有用;如果是考察思维能力,考核的方式应该是给一个具体的算法应用题,来看看面试者的分析和思考过程,例如一道业务上曾经用到的“如何快速计算你好友的好友和你的共同好友数”。

由于日常开发使用java居多,因此使用JDK提供的Java版各类数据结构更加符合实际需求

排序算法指标

  • 选择排序(原理:将待排序的元素分为已排序(初始为空)和未排序两组,依次将未排序的元素中值最小的元素放入已排序的组中)

  • 插入排序 n^2 空间O(1) 稳定(每次将一个待排序的元素,按其关键字的大小插入到前面已经排好序的子文件的适当位置) 经常使用

冒泡 n^2 稳定(相邻两元素进行比较,如有需要则进行交换)(两个for循环 一轮比较9次,二轮比较8次)

  • 希尔 nlgn~n^2 (将整个待排元素序列分割成若干个子序列,分别进行直接插入排序,待整个序列的元素基本有序,在对全体元素进行一次直接插入排序)
  • 快排 nlgn 空间复杂度O(lgn) 不稳定 基于分割交换排序的原则,这种类型的算法占用空间较小,他将待排序列表分成三个主要部分:小于基准的元素,基准元素,大于基准的元素
    • (思想:通过一次划分:将待排元素分为左右两个子序列,左侧均小于基准元素排序码,右侧均大于等于基准元素排序码,反复递归,直至每一个序列只有一个元素为止)
    • 快排的优化方法,在选择基准元素时,可以(1、三数取中法(首/尾/中间各取一个数据作为分区点,取中间数作为分区点) 2、随机法)

编程题:用快排思想在O(n)内查找第K大元素?比如,4,2,5,12,3 这样一组数据,第3大元素就是4。

思路:选择数组区间A[0…n-1]的最后一个元素A[n-1]作为pivot,对数组A[0…n-1]原地分区,这样数组就分成了三部分,A[0…p-1]、A[p]、A[p+1…n-1],如果p+1=K,那A[p]就是要求解的元素;如果K>p+1, 说明第K大元素出现在A[p+1…n-1]区间,我们再按照上面的思路递归地在A[p+1…n-1]这个区间内查找

补充:倘若是现在开发“查找第K大元素” 这个需求,我会将这批数据放进List集合里面,然后使用Collections.sort()方法按大小排序好,然后get第K个元素。

  • 堆排 nlgn 不稳定
    可以看做是选择排序的改进,基于比较的排序算法,他将其输入划分为未排序和排序的区域,通过不断消除最小元素并将其移动到排序区域来收缩未排序区域。
  • 归并 nlgn 稳定 jdK1.7之前集合工具包默认使用的排序算法 1.7使用的是TimSort排序方法,还没有研究过 (可分为二路归并/多路归并)
    使用分治思想,将复杂问题分解为较小的子问题,直到分解的足够小,可以轻松解决问题为止。(将两个有序表合并成一个有序表) 由大到小排列

  • 基数排序 O(n) 空间复杂度O(rd) 稳定(基数排序必须依赖于另外的排序方法 实质是多关键字排序)
    是通过比较数字将其分配到不同的“桶里”来排序元素的。他是线性排序算法之一。
    解决方案:1、最高位优先法MSD 2、最低位优先法LSD

  • 桶排序 O(n) 将要排序的数据分到几个有序的桶里,每个桶里的数据再单独进行排序
    适用场景:外部排序中(磁盘中,内存有限,无法将数据全部加载到内存中)

  • 计数排序(桶排序的一种特殊形式:每个桶中的数据相同)

  • 排序方法的选择? n代表数据量
    1、n较小,可以采用直接插入或直接选择排序
    2、若文件初始状态基本有序,应选用直接插入、冒泡或随机的快速排序
    3、n较大,采用复杂度为O(nlgn)的方法:快排/堆排/归并
    4、在实际的软件开发中,为什么我们更倾向于使用插入排序而不是冒泡排序算法?
    从代码实现上来看,冒泡排序的数据交换要比插入排序的数据移动要复杂,冒泡排序需要3个赋值操作,而插入排序只需要1个,所以在对相同数组进行排序时,冒泡排序的运行时间理论上要长于插入排序。

  • 利用快排思想实现在O(n)内查找第K大的元素?

快排核心思想就是分治和分区,选择数组区间A[0…n-1]的最后一个元素A[n-1]作为pivot(基准元素),对数组A[0…n-1]原地分区,这样数组就分成了三部分,A[0…p-1]、A[p]、A[p+1…n-1]。如果p+1=K,那A[p]就是要求解的元素;如果K>p+1, 说明第K大元素出现在A[p+1…n-1]区间,我们再按照上面的思路递归地在A[p+1…n-1]这个区间内查找。同理,如果K<p+1,那我们就在A[0…p-1]区间查找

为什么这个算法的时间复杂度为O(n)?
第一次分区查找,我们需要对大小为n的数组执行分区操作,需要遍历n个元素。第二次分区查找,我们只需要对大小为n/2的数组执行分区操作,需要遍历n/2个元素。
依次类推,分区遍历元素的个数分别为、n/2、n/4、n/8、n/16.……直到区间缩小为1。如果把每次分区遍历的元素个数加起来,就是:n+n/2+n/4+n/8+…+1。这是一个等比数列求和,最后的和等于2n-1。所以,上述解决思路的时间复杂度就为O(n)。

如果数据存储在链表中,这三种排序算法还能工作吗?
一般而言,考虑只能改变节点位置,冒泡排序相比于数组实现,比较次数一致,但交换时操作更复杂;
插入排序,比较次数一致,不需要再有后移操作,找到位置后可以直接插入,但排序完毕后可能需要倒置链表;
选择排序比较次数一致,交换操作同样比较麻烦。综上,时间复杂度和空间复杂度并无明显变化,若追求极致性能,冒泡排序的时间复杂度系数会变大,插入排序系数会减小,选择排序无明显变化。

  • Arrays拥有一组static方法(equals():比较两个array是否相等/fill():将值填入array中/sort():用来对array进行排序/binarySearch():在排好序的array中寻找元素/system.arraycopy():array的复制)
  • Jdk7中Arrays.sort()和Collections.sort()排序方法使用注意: jdk1.6中的arrays.sort()和 collections.sort()使用的是MergeSort; jdk1.7中内部实现转换成了TimSort方法,
  • 对对象间比较的实现
    1、有两个参数,第一个是比较的数据,第二个是比较的规则,如果comparator为空,则使用comparableTimSort的sort实现
    2、传入的待排序数组若小于MIN_MERGE(Java实现中为32)则从数组开始处找到一组连接升序或严格降序(找到后翻转)的数
    BinarySort:使用二分查找的方法将后续的数插入之前的已排序数组
    3、开始真正的TimSort过程(选取minRun大小,之后待排序数组将被分成以minRun大小为区块的一块块子数组)
    Timsort的思想:找到已经排好序的数据子序列,然后对剩余部分排序,最后合并起来
  • java提供的默认排序算法
    1、对于基础数据类型,目前使用的是所谓双轴快速排序(Dual-Pivot QuickSort),是一种改进的快速排序算法,早期版本是相对传统的快速排序;
    2、而对于对象数据类型,目前则是使用TimSort,思想上也是一种归并(Merge)和二分插入排序(binary Sort)结合的优化排序算法。
    思路是查找数据集中已经排好序的分区(这里叫run 连续升或降的序列),然后合并这些分区来达到排序的目的。
  • Java8引入了并行排序算法(直接使用parallelSort方法),这是为了充分利用现代多核处理器的计算能力,底层实现基于fork-join框架,当处理的数据集比较小的时候,差距不明显,甚至还表现差一点;但是,当数据集增长到数万或百万以上时,提高就非常大了,具体还是取决于处理器和系统环境.
  • fork-join框架的适用场景:计算密集型,而非IO密集型,踩过坑
  • 1、二分查找法(考虑好边界条件,不要被面试官抓住漏洞)(使用Arrays工具类的binarySearch方法)
    思路:先确定数组的中间位置,然后将要查询的值与数组中间位置的值进行比较,若小于数组中间值,则要查找的值应位于该中间值之前,依次类推;
    算法: 1、如果关键字小于中央元素,只需继续在数组的前半部分进行搜索;2、如果关键字与中央元素相等,则搜索结束,找到匹配元素;3、如果关键字大于中央元素,只需继续在数组的后半部分进行搜索
    限制:用于顺序链表或排序后的链表
    注意事项:1、循环退出条件low<=high;2、mid的取值(low+(high-low)>>1)因为相比除法运算来说,计算机处理位运算要快得多;3、low和high的更新low=mid+1,high=mid-1
    时间复杂度:O(lgn)

  • 2、4种常见的二分查找变形问题
    第一种:查找第一个值等于给定值的元素

第二种:查找最后一个值等于给定值的元素

第三种:查找第一个大于等于给定值的元素

第四种:查找最后一个小于等于给定值的元素

  • 3、如果有序数组是一个循环有序数组,比如4,5,6,1,2,3。针对这种情况,如何实现一个求“值等于给定值”的二分查找算法呢?

  • 4、x的平方根 LeetCode69 实现int sqrt(int x)函数。计算并返回x的平方根,其中x是非负整数,由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去
  • 方法1:java自带API

  • 方法2:二分搜索

方法3:牛顿迭代法 求c的算术平方根就是求f(x)=x^2-c的正根 迭代公式:xn+1=1/2(xn+c/xn)

常见的时间复杂度?表示的是一个算法执行效率与数据规模增长的变化趋势

空间复杂度:(表示算法的存储空间与数据规模之间的增长关系)
常见的空间复杂度就是O(1)、O(n)、O(n2)

  • 平均时间复杂度(加权平均时间复杂度):加了概率
  • 均摊时间复杂度:对一个数据结构进行一组连续操作中,大部分情况下时间复杂度都很低,只有个别情况下时间复杂度比较高,而且这些操作之间存在前后连贯的时序关系,这个时候,我们就可以将这一组操作放在一块儿分析,看是否能将较高时间复杂度那次操作的耗时,平摊到其他那些时间复杂度比较低的操作上。
  • 算法的最好情况和最坏情况?
    最好情况:算法执行最佳的数据排列。如:二分搜索时,目标值正好位于搜索的数据中心,时间复杂度为0;
    最差情况:给定算法的最差输入。如:快速排序中,如果选择的关键值是列表中最大或最小值,最差情况就会发生,时间复杂度会变成O(n^2)

  • 方法4:Arrays.binarySearch()方法:数组必须是有序的(有序数组时,使用列表或树可达到O(lgn),使用hashset可达到O(1))
  • 1、我们要给电商交易系统中的“订单”排序。订单有两个属性(下单时间,订单金额) 需求是按金额从小到大对订单数据排序。对金额相等的订单,按下单时间从早到晚排序
    稳定性概念:如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变
    思路:先按下单时间给订单排序,排完序之后,使用稳定排序算法,按订单金额重新排序(稳定排序算法可以保持金额相同的两个对象,在排序之后的前后顺序不变)

  • 2、O(n)时间复杂度内求无序数组中的第K大元素?(利用分区的思想) 代码放在eclipse中
    我们选择数组区间A[0…n-1]的最后一个元素A[n-1]作为pivot,对数组A[0…n-1]原地分区,这样数组就分成了三部分,A[0…p-1]、A[p]、A[p+1…n-1]。
    如果p+1=K,那A[p]就是要求解的元素;如果K>p+1, 说明第K大元素出现在A[p+1…n-1]区间,我们再按照上面的思路递归地在A[p+1…n-1]这个区间内查找。同理,如果K<p+1,那我们就在A[0…p-1]区间查找。

  • 3、现在你有10个接口访问日志文件,每个日志文件大小约300MB,每个文件里的日志都是按照时间戳从小到大排序的。你希望将这10个较小的日志文件,合并为1个日志文件,合并之后的日志仍然按照时间戳从小到大排列。如果处理上述排序任务的机器内存只有1GB,你有什么好的解决思路
    answer:先构建十条io流,分别指向十个文件,每条io流读取对应文件的第一条数据,然后比较时间戳,选择出时间戳最小的那条数据,将其写入一个新的文件,然后指向该时间戳的io流读取下一行数据,然后继续刚才的操作,比较选出最小的时间戳数据,写入新文件,io流读取下一行数据,以此类推,完成文件的合并, 这种处理方式,日志文件有n个数据就要比较n次,每次比较选出一条数据来写入,时间复杂度是O(n),空间复杂度是O(1),几乎不占用内存。

定义:是多个相同类型数据按一定顺序排列的集合,bi

  • 1、实现一个支持动态扩容的数组
  • 2、实现一个大小固定的有序数组,支持动态增删改操作 实际开发中我们使用ArrayList,更高效
  • 3、实现两个有序数组合并为一个有序数组
  • 4、数组操作常见问题(数组脚标越界异常(ArrayIndexOutOfBoundsException)/空指针异常(NullPointerException))
  • leetcode15:三数求和
    给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组
    思路:首先对数据进行排序,然后确定第一个数,使用for循环,后两个数使用两指针,依次尝试,如果值大于0-num[i],右指针左移;如果值小于0-num[i],左指针右移。

  • leetcode169:求众数 给定一个大小为n的数组,找到其中的众数。众数是指在数组中出现次数大于?n/2?的元素
    先决条件:给定的数组总是存在众数
    思路:1、利用摩尔投票法 2、利用java的api

  • 第二种解法:使用java的api,排序

  • LeetCode41:求缺失的第一个正数
    给定一个未排序的整数数组,找出其中没有出现的最小的正整数。

Demo 五子棋程序中,有存盘退出和续上盘的功能,因为该二维数组中的很多值默认为0,因此记录了很多没有意义的数据 –》稀疏

循环链表:循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时,就特别适合采用循环链表(比如著名的约瑟夫问题)

在遍历循环链表时得特别小心,否则将会无限地遍历链表,因为循环链表每一个结点都有一个后继结点
双向链表:(需要额外的两个空间来存储后继结点next和前驱结点的地址prev)

使用技巧:
1、理解指针或引用的含义:是存储所指对象的内存地址(将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指针)
2、警惕指针丢失和内存泄漏 java不需考虑(使用jvm自动管理内存)
3、利用哨兵简化实现难度:如果我们引入哨兵结点,在任何时候,不管链表是不是空,head指针都会一直指向这个哨兵结点(插入排序、归并排序、动态规划)
删除最后一个结点和删除其他节点,插入第一个结点和插入其他节点可以统一为相同的代码逻辑。
哨兵的好处:它可以减少特殊情况的判断,比如判空,判越界,因为空可越界可认为是小概率情况,如实每次执行代码都走一遍,大多数情况下是多于的。
比如给一个哨兵节点,以及将key赋值给末尾元素,让数组遍历不用判断越界也可以因为相等停下来。
4、重点留意便捷条件处理:(如果链表为空时,代码是否能正常工作?如果链表只包含一个结点时,代码是否能正常工作?代码逻辑在处理头结点和尾结点的时候,是否能正常工作?)
5、举例画图,辅助思考:(举例法和画图法)

  • 可以用任意一组存储单元来存储单链表中的数据结构(可以不连续),存储每个元素的值a,还必须存储后集结点的信息,这两个信息组成结点。

开发中使用集合工具包,Collecionts.reverse(List<?> list)
原理:i m n相邻,调整指针的指向,调整m的指向,指向结点i,链表会断开,需要在调整之前把n保存起来 代码P236

  • 思路1:蛮力法
    若链表中出现多个结点的后继指针重复,就表明存在环。从第一个结点开始,令其为当前节点,然后看看链表中其他节点的后继指针是否指向当前结点,如果存在,说明链表中存在环。
    缺点:如果不能确定链表的表尾,算法将会出现死循环。

*思路2:使用散列表(时间复杂度O(n),空间复杂度O(n))
从表头节点开始,逐一遍历链表中的每个结点;
对于每个结点,检查该结点的地址是否存在于散列表中;
如果存在,则表明当前访问的结点已经被访问过,出现此情况的原因是给定的链表中存在环;
如果散列表中没有当前节点的地址,那么把该地址插入散列表中;
重复上述过程,直至到达表尾或找到环。

  • 思路3:如果一个单链表中有环,用一个指针去遍历,永远不会结束,所以可以用两个指针,一个指针一次走一步,另一个指针一次走两步,如果存在环,则这两个指针会在环内相遇,时间复杂度为O(n) indeed(无论环的个数是奇数还是偶)被称为Floyd算法

对floyd算法的补充:如果两个指针每次分别移动2个结点和3个结点,而不是移动一个和2个结点,算法仍然有效吗?
可以,算法的复杂度可能增加

思路:在找到链表中的环后,保持slowPtr指针不变,fastPtr指针则继续移动,每次移动fastPtr指针时,计数器变量加1,直至再一次回到slowPtr指针所在的位置,即为环的长度。

补充:此思路可以引申为 求循环小数的开始位置(小数点之后的位数)和循环长度

  • 1、已知单链表的头指针,查找到倒数第K个节点,然后删除这个节点
    思路1:快慢指针法:
    我们定义一个快指针P和慢指针Q,先让P指针走到K个节点位置,然后Q指针从头指针开始和P一起移动,当P移动到尾部的时候,那么此时Q节点所在的位置就是倒数第K个节点

思路2:蛮力法(时间复杂度最高)
从链表的第一个结点开始,统计当前节点后面的结点个数。如果后面的节点个数小于k-1,算法结束;如果大于k-1,则移动到下一个结点,重复该过程
思路3:散列表O(m) 为了减少链表遍历的次数
散列表的条目是<结点的位置,结点地址>,在遍历链表时,可以得到链表的长度,令M表示链表的长度,这样求链表的导师胡第n个结点的问题转变为求链表正数
第M-n+1个结点。返回散列表中主键为M-n+1的值即可。时间复杂度O(m),空间复杂度O(m):创建一个大小为M的散列表。

  • 2、已知单链表的头结点,查找到链表的中间节点(只允许扫描一次)
    一个快指针P和慢指针Q,P和Q同时从头指针出发,快指针P每次移动两步,慢指针每次移动一步,当快指针P到尾部的时候,慢指针Q所在的位置就是中间节点的位置

思路:使用分治的思想,两两归并

方法1:蛮力法
把第一个链表中的每一个结点指针与第二个链表中的每一个结点指针比较,当结点相等时,即为相交结点。时间复杂度为O(mn)
方法2:散列表
选择结点较少的链表(若链表长度未知,那么随便选择一个链表),将其所有结点的指针值保存在散列表中;遍历另一个链表,对于该链表中的每一个结点,检查散列表
中是否已经保存了其结点指针。如果两个链表存在合并点,那么必定会在散列表中找到记录。时间复杂度O(m)+O(n);空间复杂度O(m)或O(n)
方法3:两个栈
创建两个栈,然后遍历两个链表,分别把所有结点存入第一个和第二个栈,两个栈包含了对应链表的结点地址,比较两个栈的栈顶元素,如果相等,则弹出两个栈
的栈顶元素并保存在临时变量中,继续上述操作,直至两个栈的栈顶元素不相等,此时即找到了两个链表的合并点。时间复杂度O(m+n),空间复杂度O(m+n)
方法4:时间复杂度超低的解法
获取两个链表L1/L2的长度,O(max(m,n));计算两个长度的差d,从较长链表的表头开始,移动d步,然后两个链表同时移动,直至出现两个后继指针相等的情况。

1)前提:字符串以单个字符的形式存储在单链表中。
2)遍历链表,判断字符个数是否为奇数,若为偶数,则不是。
3)将链表中的字符倒序存储一份在另一个链表中。
4)同步遍历2个链表,比较对应的字符是否相等,若相等,则是水仙花字串,否则,不是。
思路2:使用快慢两个指针找到链表中点,慢指针每次前进一步,快指针每次前进两步。在慢指针前进的过程中,同时修改其 next 指针,使得链表前半部分反序。最后比较中点两侧的链表是否相等
时间复杂度O(n) 空间复杂度O(1)

把后一个元素赋值给待删除节点,这样也就相当于是删除了当前元素
1. 如果待删除节点不是最后一个节点,就用他的next节点的value覆盖它的value,然后删掉它的next节点
2、如果是最后一个节点,顺序遍历o(n)

递归的本质 栈
1、递归是函数里调用自身
2、必须有一个明确的递归出口
3、在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储,因此递归次数过多容易造成栈溢出
递归的基本思想:
1、是把规模较大的一个问题,分解成规模较小的多个子问题去解决
2、先解决子问题,再基于子问题来解决当前问题
递归和内存:每次递归调用都在内存中生成一个新的函数副本(仅仅是一些相关的变量),一旦函数结束(即返回某些数据),改返回函数的副本就从内存中删除。
递归一般用于解决三类问题:
1、数据的定义是按递归定义的。(Fibonacci函数,n的阶乘)
2、问题解法按递归实现。(动态规划/分治/回溯)归并排序和快速排序用到了递归的思想
3、数据的结构形式是按递归定义的。(二叉树的/先/中/后序遍历,图的深度/广度优先搜索)

  • 子程序的调用:在跳往子程序前,会先将下个指令的地址存到堆栈中,直到子程序执行完后再将地址取出,以回到原来的程序中
    • JVM中的栈帧
  • 处理递归调用:和子程序的调用类似,只是除了存储下一个指令的地址外,也将参数、区域变量等数据存入堆栈中
  • 表达式的转换和求值
  • 二叉树的遍历
  • 图的深度优先搜索
  • 浏览器的前进、后退功能
  • 字符串反转

1、栈在表达式求值中的应用:(一个保存操作符的栈,另一个是保存运算符的栈)
我们从左向右遍历表达式,当遇到数字,我们就直接压入操作数栈;当遇到运算符,就与运算符栈的栈顶元素进行比较(栈顶元素优先级高就取出运算符,从操作数栈取两个操作数,结果压入操作数栈)

  • LeetCode150 逆波兰表示式求值(后缀表达式)(逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构,它执行先进后出的顺序)

栈在括号匹配中的应用:(我们用栈来保存未匹配的左括号,从左到右依次扫描字符串。当扫描到左括号时,则将其压入栈中;当扫描到右括号时,从栈顶取出一个左括号)

  • LeetCode20:有效的括号 给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串,判断字符串是否有效

变体1:给定一个只包含 ‘(’ 和 ‘)’ 的字符串,找出最长的包含有效括号的子串的长度 例如:输入: "(()"输出: 2 输入: “)()())” 输出: 4
对于这种括号匹配问题,一般都是使用栈,我们先找到所有可以匹配的索引号,然后找出最长连续数列!O(nlogn)

思路2:动态规划

编程题5:如何实现浏览器的前进、后退功能?
我们使用两个栈,X和Y,我们把首次浏览的页面依次压入栈X,当点击后退按钮时,再依次从栈X中出栈,并将出栈的数据依次放入栈Y.当我们点击前进按钮时,
我们依次从栈Y中取出数据,放入栈X中。当栈X中没有数据时,那就说明没有页面可以继续后退浏览了。当栈Y中没有数据,那就说明没有页面可以点击前进按钮浏览了。
递归需要满足的三个条件:1、一个问题的解可以分解为几个问题的解;2、这个问题与分解后的子问题,除了数据规模不同,求解思路完全一样;3、存在递归终止条件
首先是定义ListNode,最基础的数据结构(包含int value,指向下一个结点点的指针),然后有结点构成栈(包含pop/push/print/clear等功能),最后实现浏览器功能()

编程题3:用数组实现一个顺序栈

编程题4:用链表实现一个链式栈

java concurrent并发包利用ArrayBlockingQueue来实现公平锁等)
分类:顺序队列和链式队列(用数组实现的队列和链表实现的队列) 基于链表实现的无界队列(可能会导致过多的请求排队,响应时间较长),基于数组实现的有界队列(大小有限)

  • 排队请求;
  • 数据库连接池;
  • 高性能队列Disruptor

Disruptor(线程之间用于消息传递的队列)(应用apache Storm/canal/log4j2) 性能比常用的内存消息队列ArrayblockingQueue要高出一个数量级,它还因此获得过Oracle官方的Duke大奖
1、Disruptor详解?
基于循环队列保证数据被消费的顺序性。(实现了一个最简单的“生产者-消费者模型”)在这个模型中,“生产者”生产数据,并且将数据放到一个中心存储容器中。之后,“消费者”从中心存储容器中,取出数据消费。而存储数据的中心存储容器,是用什么样的数据结构来实现的呢?(1、基于链表实现的链式队列;2、基于数组实现的顺序队列(循环队列))
基于循环队列的生产者/消费者模型:思路(当队列满了之后,生产者就轮询等待,当队列空了后,消费者就轮训等待)

上述代码存在的问题:多线程下,多个生产者写入的数据可能会互相覆盖,多个消费者可能会读取重复的数据
解决方法:1、加锁(同一时间只允许一个线程执行add()函数,相当于并行改成了串行),可以使用CAS乐观锁机制减少加锁的粒度。
基于无锁的并发“生产者-消费者模型”

  • 对于生产者来说,它往队列中添加数据之前,先申请可用空闲存储单元,并且是批量地申请连续的n个(n≥1)存储单元。后续往队列中添加元素,就可以不用加锁了;
  • 对于消费者来说,处理的过程跟生产者是类似的。它先去申请一批连续可读的存储单元,当申请到这批存储单元之后,后续的读取操作就可以不用加锁了。
    源码中,Disruptor采用的是RingBuffer和AvailableBuffer这两个结构
    需要注意的地方:生产者A申请到一组连续的存储单元,假设下标是3到6的存储单元,生产者B紧跟着申请到下标是7到9的存储单元,那么3-6没有完全写入数据之前,7-9的数据是无法读取的,这是Disruptor实现思路的一个弊端。实际上,不管架构设计还是产品设计,往往越简单的设计思路,越能更好地解决问题。
    4、实现一个消息队列系统

编程题1:用数组实现一个顺序队列

编程题2:用链表实现一个链式队列

编程题3:实现一个循环队列(最关键的是,确定好队空和队满的判定条件)(我使用数组实现)
队列为空的判断条件仍然是head == tail,当队满时,(tail+1)%n=head,循环队列会浪费一个数组的存储空间。

编程题4:实现一个双端队列 java中有工具包Deque

编程题5:滑动窗口最大值

  • 编程题6:两个栈实现队列
    思路:用栈a栈b模拟队列q,a为插入栈,b为弹出栈,栈a提供入队功能,栈b提供出队功能。入队时,入栈a即可,出队时,分两种情况:
    *1、栈b不为空,直接弹出栈b的数据 *2、栈b为空,则依次弹出栈a的数据,放入栈b中,再弹出栈b的数据。

编程题7:使用两个队列实现栈
思路:确保有一个队列总是空的, 入栈:在任何一个非空队列中插入元素,检查队列q1是否为空,如果q1为空,那么对q2执行入队操作;
出栈:如果队列q1非空,那么从q1移n-1个元素到q2中,然后对q1中的最后一个元素执行出队操作并返回该元素。