壹｜什么是栈

栈是一种操作受限的线性表，只允许在一端插入和删除数据，后进先出，先进后出。「叠盘子」

贰｜栈的属性方法

  • peek：返回头节点的值。
  • isEmpty：是否含有头节点。
  • push(value)：插入头节点。

  • pop：删除头节点，返回删除的头节点。

    叁｜栈的问题拓展

    栈的应用场景

  • 函数调用

  • 表达式求值
  • 括号匹配

  • 浏览器前进后退

    肆｜栈的题目

  • 用栈实现队列：https://leetcode-cn.com/problems/implement-queue-using-stacks/

  • 最小栈：https://leetcode-cn.com/problems/min-stack/

  • 有效的括号：https://leetcode-cn.com/problems/valid-parentheses/

    伍｜什么是队列

    队列是一种操作受限的线性表，入队从队尾放数据，出队从队头取数据，先进先出。「排队买票」

    陆｜队列的属性方法

  • peek：返回头节点的值。

  • isEmpty：是否含有头节点。
  • enquene(value)：从尾部插入节点。

  • dequene：删除头节点，返回删除的头节点。

    柒｜队列的问题拓展

    队列的应用场景

    对于大部分资源有限的场景，没有空闲资源时，基本可以通过队列来实现请求排队。

  • 优先级队列

  • 线程池

    捌｜队列的题目

  • 用队列实现栈：https://leetcode-cn.com/problems/implement-stack-using-queues/

  • 滑动窗口最大值：https://leetcode-cn.com/problems/sliding-window-maximum/

    拾｜什么是堆

    堆是一个完全二叉树，堆中每一个节点都必须大于等于或小于等于其子树中每个节点的值。

    拾壹｜堆的方法属性

    属性

  • heapContainer

    方法

  • getLeftChildIndex(parentIndex)：返回 (2 * parentIndex) + 1。

  • getRightChildIndex(parentIndex)：返回 (2 * parentIndex) + 2。
  • getParentIndex(childIndex)：返回 Math.floor((childIndex - 1) /2)。
  • hasParent(childIndex)：返回父节点下标是否 ≥ 0。
  • hasLeftChild(parentIndex)：返回子节点下标是否小于堆的长度。
  • hasRightChild(parentIndex)：返回子节点下标是否小于堆的长度。
  • leftChild(parentIndex)：返回对应子节点下标的值。
  • rightChild(parentIndex)：返回对应子节点下标的值。
  • parent(childIndex)：返回对应父节点下标的值。
  • swap(indexOne, indexTwo)：交换两个节点。
  • peek：返回堆顶。
  • poll：干掉堆顶；替换最后一个节点和堆顶，向下堆化。
  • add(item)：堆尾添加一个元素，向上堆化。
  • remove(item)：遍历找到删除的节点，并进行堆化。
  • find(item)：遍历堆，找到相同的值放进数组，返回数组。
  • isEmpty：是否有堆的长度。
  • heapifyUp(customStartIndex)：如果有父节点，和父节点不断向上交换。

  • heapifyDown(customStartIndex)：如果有子节点「有右节点取右节点」，和子节点不断向下交换。

    拾贰｜堆的问题拓展

    堆排序的应用

  • 优先级队列

  • 求 Top K

  • 求中位数

    拾叁｜堆的题目

  • 数组中第k大的数：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

  • 寻找中位数：https://leetcode-cn.com/problems/find-median-from-data-stream/