当先锋百科网

首页 1 2 3 4 5 6 7

数据结构基础：堆栈队列

本文讲解的主要内容是堆栈队列，其中：

说明：所有源码均可以在idea上调试。

堆

堆的实现(大小顶堆)

查找第K大的元素

  • 介绍：在一组无序的数组中，查找第K大的元素并输出
  • 设计思路：通过快排和堆排两种方式可以实现。
    • 快排：
      • 在一次快排中，数据会根据中间元素分成了两部分
      • 如果中间元素小于K，递归中间元素的右半部分
      • 如果中间元素大于K，递归中间元素的左半部分
      • 如果中间元素正好K，返回中间元素的左半部分
    • 堆排：
      • 构造一个大小为K的大顶堆
      • 数组中K之外的元素与堆顶元素进行对比
      • 比堆顶元素大的，不发生交换
      • 比堆顶元素小的，发生交换，并进行堆整理
      • 返回大小为K的堆
      • 另一种方式维持一个大小为【数组长度 - K】大小的堆，其他同理，返回非堆的K数据。
  • 代码实现：为简便起见，主要实现代码和注释，都在下方的源码中有，不再赘述，测试用例如需补充，欢迎提commit和issue。
  • 源码和测试案例

优先队列

  • 介绍：将输入的元素按照某种优化级进行存入，每次取出的元素都是优先级最高的。
  • 设计思路：考虑使用堆排序堆元素进行放置。
  • 代码实现：为简便起见，主要实现代码和注释，都在下方的源码中有，不再赘述，测试用例如需补充，欢迎提commit和issue。
  • 源码和测试案例

栈

栈的基本功能包括：入栈(push)、出栈(pop)、获取栈顶元素(peek)、获取栈中实际容量(getrealsize)、获取栈中最大容量(getmaxsize)、判空(empty)、查找值(search)、扩容(resize)

数组栈

链表栈

  • 介绍：使用链表实现栈的功能
  • 设计思路：
  • 代码实现：为简便起见，主要实现代码和注释，都在下方的源码中有，不再赘述，测试用例如需补充，欢迎提commit和issue。
  • 源码和测试案例

双栈实现队列

  • 介绍：使用栈实现队列的功能
  • 设计思路：通过双栈不停出入栈，实现队列的功能。
  • 代码实现：为简便起见，主要实现代码和注释，都在下方的源码中有，不再赘述，测试用例如需补充，欢迎提commit和issue。
  • 源码和测试案例

最小栈

  • 介绍：除了栈本身的功能，还需要提供每次获取最小元素的功能。要求所有操作的时间复杂度是 O(1)。
  • 设计思路：自身建立一个最小栈，每次只存放最小的数。
  • 代码实现：为简便起见，主要实现代码和注释，都在下方的源码中有，不再赘述，测试用例如需补充，欢迎提commit和issue。
  • 源码和测试案例

最小栈优化

  • 介绍：同上
  • 设计思路：优化点在于上述最小栈是额外占用了一个栈来做最小栈，此处将该最小栈优化为一个数，节省了空间复杂度。
  • 代码实现：为简便起见，主要实现代码和注释，都在下方的源码中有，不再赘述，测试用例如需补充，欢迎提commit和issue。
  • 源码和测试案例

单调栈

  • 介绍：将已知数组转化为这样一个数组：对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1。
  • 设计思路：新建一个栈，若存在这样的数，则存入栈中。
  • 代码实现：为简便起见，主要实现代码和注释，都在下方的源码中有，不再赘述，测试用例如需补充，欢迎提commit和issue。
  • 源码和测试案例

计算器

  • 介绍：实现一个可以满足基本运算的计算器（支持小数）
  • 设计思路：中缀表达式转后缀表达式。
  • 代码实现：为简便起见，主要实现代码和注释，都在下方的源码中有，不再赘述，测试用例如需补充，欢迎提commit和issue。
  • 源码和测试案例

队列

  • 队列的基本功能包括：1、元素入队(offer)，2、元素出队(poll)，3、弹出队首元素(peek)，4、队列判空(empty)，5、获取真实队列长度(getrealsize)，6、获取最大队列长度(getmaxsize)，7、队列扩容(resize)，8、查找函数(search)

数组队列【循环队列】

链表队列

  • 介绍：使用链表建立队列
  • 设计思路：
  • 代码实现：为简便起见，主要实现代码和注释，都在下方的源码中有，不再赘述，测试用例如需补充，欢迎提commit和issue。
  • 源码和测试案例

队列实现栈

  • 介绍：使用两个队列实现栈的功能。
  • 设计思路：通过两个队列来回置换原素，达到栈的功能。
  • 代码实现：为简便起见，主要实现代码和注释，都在下方的源码中有，不再赘述，测试用例如需补充，欢迎提commit和issue。
  • 源码和测试案例