算法经典题一（栈，队列，堆）

算法经典题一（栈，队列，堆）

一.预备知识:栈，队列，堆

栈 stack：先进后出的线性表
相关方法操作：
1.判断是否为空S.empty()
2.进栈S.push()
3.出栈S.pop()
4.返回栈顶元素S.top()
5.存储元素个数S.size()

队列 queue：先进先出的线性表
相关方法操作：
1.判断队列是否为空Q.empty()
2.进队Q.push()
3.出队Q.pop()
4.返回队首元素Q.front()
5.返回队尾元素Q.back()
6.存储元素个数Q.size()

堆 二叉堆属性
最（大）小二叉堆，最（大）小值先出的完全二叉树(线性表存储的，第一个元素即为最大值)

说明：即父结点相对于两个子结点，是最小或最大的，那么根节点就是最小或最大的。

相关操作（最大堆）：
1.判断堆是否为空big_heap.empty()
2.弹出堆顶元素big_heap.pop(),即最大值
3.将元素添加进堆big_heap.push()
4.返回堆顶元素big_heap.top()，即最大值
5.返回堆中个数big_heap.size()

二.应用示例：

例1.使用队列实现栈

描述：只能使用队列来实现栈

分析：使用临时队列将每次push进来的元素调换位置，将元素添加至队首，重点修改push()方法

操作：
1.将新元素push进入临时队列，那么新元素就会进入队首
2.将原队列元素push进临时队列，原有的元素依次在新元素后面，就实现了栈的元素排列和添加结构
3.将临时队列push进入原队列

例2.使用栈实现队列

描述：只能使用栈来实现队列的操作

分析：队列需要先进先出，栈是先进后出，基于栈的访问方法，只能每次访问栈顶元素，那么就需要对每次push进栈的元素调换位置，使每次栈的元素添加至栈底。使用临时栈，将原来的栈的元素push进入临时栈，再把新元素也push进临时栈，最后将临时栈中的元素push进原栈。

操作：
1.将原栈的元素push进临时栈
2.将新元素push进临时栈
3.将临时栈中的元素push到原栈

例3 包含min函数的栈

描述：设计一个栈，对栈的操作算法复杂度都是常数级O（1），且能返回栈内最小元素

分析：不能使用临时排序等方法，一个变量也不能记录最小值，在push操作下，一个变量可以与添加的元素进行比较更新最小值，但若使用pop操作时，便无法保证记录的最小值是有效的。每个状态，都需要一个变量记录最小值，空间换时间。
操作：
1.建立一个最小值栈
2.每进行pop 或push操作时，更新最小栈栈顶的值

例4 合法的出栈序列

描述：已知从1至n的数字序列，按顺序入栈，每个数字入栈后即可出栈，也可在栈中停留，验证给定的出栈的数字队列是否合法

分析：利用栈模拟进出栈，每进栈一个元素，验证出栈的元素能否与队首元素匹配，若匹配，则出栈，队首元素弹出，若不匹配，则继续入栈，循环判断，若最后栈为空，则说明出栈队列合法。

操作：
1.将出栈结果保存到队列中
2.按照元素顺序，将元素进栈
3.每进栈一个元素，判断是否与队首元素相同，相同，弹出队首与栈顶元素，直到不相等结束
4.判断最终栈是否为空，为空则说明该出栈序列合法

例5 简单的计算器

描述：设计一个计算器，输入一个字符串存储的的数学表达式，可以计算包括“（”，“）”，“+”，“-”四种符号的数学表达式，输入的数学表达式保证合法。输入的数学表达式可能存在空格。

分析：使用栈来计算（方便处理括号优先级），建立两个栈，数字栈（存储数字和运算结果）和操作符栈（存储操作符）

例6 数组中第K大的数

备注：先了解堆的数据结构和相关知识

描述：已知一个未排序的数组，求这个数组中第K大的数字

分析：常规解法为将数组进行排序，返回相对应的索引的值，但时间复杂度较高。可建立一个含有K个元素的最小堆，当堆中元素小于K时，直接进堆，当堆顶小于新元素时，弹出堆顶，将新元素添加进堆，其最小值即为堆顶的值 。设数组长度为N，其时间复杂度为N*logK，相比于之前有一定的优化

操作
1.根据参数建立堆
2.遍历数组，添加新元素，堆中元素个数小于K时，直接进堆
3.维护更新最小堆，堆中元素个数大于K时，与堆顶比较，若堆顶小于新元素，弹出堆顶，将新元素添加进堆
4.遍历结束，取出堆顶元素即为第K大的值

例7 寻找中位数

描述：设计一个数据结构，该数据结构动态维护一组数据，支持如下操作：
1.添加元素，将一个整型元素添加至该数据结构中
2.返回数据的中位数，中位数定义，对于已排序的数组，数据个数为奇数个时，中位数即为中间的数，数据个数为偶数个时，为中间的两个数的平均值。

分析：常规直观的方法便是使用数组这种存储结构，每次添加元素或查找中位数时，对数组进行排序，再结算结果。
优化： 巧妙应用堆的性质，动态维护一个最大堆与最小堆，最大堆存放一半数据，最小堆存放一半数据，维持最大堆的堆顶比最小堆的堆顶小。
操作：
1.建立最大最小堆
2.维持最大堆的堆顶小于最小堆的堆顶，维护两个堆的数据元素个数相差<=1

case1:
最大堆与最小堆元素个数相同时，元素小于最大堆的堆顶，将其push进最大堆，反之push进最小堆。
case2:
最大堆比最小堆多一个元素
a.新元素小于最大堆的堆顶，将最大堆的堆顶push进最小堆，将最大堆的堆顶pop，将新元素push进最大堆
b.新元素大于最大堆堆顶，至今将其push进最小堆
case3:
最大堆比最小堆少一个元素
a.新元素小于最小堆的堆顶，直接将其push进入最大堆
b.新元素大于最小堆的堆顶，将最小堆的堆顶push进入最大堆，pop最小堆的堆顶，将新元素push进最小堆

3.获取中位数，当最大堆与最小堆的个数相同时，返回两个堆顶的均值，反之谁多一个就返回谁的堆顶

总结：这些都是一些非常基础的经典题，都是对一些常用数据结构性质的的灵活运用，还是比较有趣，灵活掌握了这些算法才算是对这些数据结构的基本性质有了认识与应用。现在的算法题基本不会出现考基本性质的应用，但万变不离其宗，把这些玩熟了，才对一些比较复杂的算法做到心中有数，找到合适的数据结构与相应的算法来解决实现。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！