【LeetCode解题总结】栈/队列篇

基础数据结构

栈

特点

栈的最大特点就是后进先出（LIFO）。对于栈中的数据来说，所有操作都是在栈的顶部完成的，只可以查看栈顶部的元素，只能够向栈的顶部压?数据，也只能从栈的顶部弹出数据。

实现

利用一个单链表来实现栈的数据结构。而且，因为我们都只针对栈顶元素进行操作，所以借用单链表的头就能让所有栈的操作在 O(1) 的时间内完成。

应用场景

在解决某个问题的时候，只要求关心最近一次的操作，并且在操作完成了之后，需要向前查找到更前一次的操作。

队列

特点

和栈不同，队列的最大特点是先进先出（FIFO），就好像按顺序排队一样。对于队列的数据来说，我们只允许在队尾查看和添加数据，在队头查看和删除数据。

实现

可以借助双链表来实现队列。双链表的头指针允许在队头查看和删除数据，而双链表的尾指针允许我们在队尾查看和添加数据。

应用场景

直观来看，当我们需要按照一定的顺序来处理数据，而该数据的数据量在不断地变化的时候，则需要队列来帮助解题。在算法面试题当中，广度优先搜索（Breadth-First Search）是运用队列最多的地方。

常见解题思路

栈

注意事项

• 出栈前要判空
• 考虑将什么东西压栈
• 考虑什么条件下压栈与出

解法总结

高级数据结构

双端队列

特点

双端队列和普通队列最大的不同在于，它允许我们在队列的头尾两端都能在 O(1) 的时间内进行数据的查看、添加和删除。

实现

与队列相似，我们可以利用一个双链表实现双端队列。

应用场景

双端队列最常用的地方就是实现一个长度动态变化的窗口或者连续区间，而动态窗口这种数据结构在很多题目里都有运用。

优先队列

特点

能保证每次取出的元素都是队列中优先级别最高的。优先级别可以是自定义的，例如，数据的数值越大，优先级越高；或者数据的数值越小，优先级越高。优先级别甚至可以通过各种复杂的计算得到。

实现

优先队列的本质是一个二叉堆结构。堆在英文里叫 Binary Heap，它是利用一个数组结构来实现的完全二叉树。换句话说，优先队列的本质是一个数组，数组里的每个元素既有可能是其他元素的父节点，也有可能是其他元素的子节点，而且，每个父节点只能有两个子节点，很像一棵二叉树的结构。

性质

1. 数组里的第一个元素 array[0] 拥有最高的优先级别。
2. 给定一个下标 i，那么对于元素 array[i] 而言：
   • 它的父节点所对应的元素下标是 (i-1)/2
   • 它的左孩子所对应的元素下标是 2×i + 1
   • 它的右孩子所对应的元素下标是 2×i + 2
3. 数组里每个元素的优先级别都要高于它两个孩子的优先级别。

基本操作

放入元素（向上筛选）

1. 当有新的数据加入到优先队列中，新的数据首先被放置在二叉堆的底部。
2. 不断进行向上筛选的操作，即如果发现该数据的优先级别比父节点的优先级别还要高，那么就和父节点的元素相互交换，再接着往上进行比较，直到无法再继续交换为止。

取出元素（向下筛选）

1. 当堆顶的元素被取出时，要更新堆顶的元素来作为下一次按照优先级顺序被取出的对象，需要将堆底部的元素放置到堆顶，然后不断地对它执行向下筛选的操作。
2. 将该元素和它的两个孩子节点对比优先级，如果优先级最高的是其中一个孩子，就将该元素和那个孩子进行交换，然后反复进行下去，直到无法继续交换为止。

时间复杂度

整个过程就是沿着树的高度爬，所以时间复杂度也是 O(logk)。

应用场景

从一堆杂乱无章的数据当中按照一定的顺序（或者优先级）逐步地筛选出部分乃至全部的数据。题目中有”前 k 个“这样的字眼，应该很自然地联想到优先队列。

【LeetCode解题总结】栈/队列篇

原文：https://www.cnblogs.com/JasonBUPT/p/11867666.html