极客算法训练笔记(四)，栈和队列，从实际应用看数据结构
- 栈
- 顺序栈和链栈
- 1. 栈应用之函数调用栈
- 2. 栈应用之表达式求值
- 3. 栈应用之括号匹配
- 4. 栈应用之浏览器前进后退功能
- 队列
- 顺序队列和链式队列
- 队列应用之生产者消费者模型
- 算法 链表反转
- 算法 链表环检测
- 算法 接雨水
❝没有最好的数据结构，只有最合适的数据结构。 ❞
栈和队列都是操作受限的数据结构，那么为什么不直接用数组和链表呢？事实上，从功能上来说，数组或链表确实可以替代栈，因为栈其实就是通过数组和链表来实现的，但是，特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错，所谓能力越大责任越大就是这个道理。
栈
顺序栈和链栈
栈只允许在一端进行插入和删除数据，满足先进后出，后进先出的特点，有数组实现的顺序栈和链表实现的链栈两种。
顺序栈
链栈
栈应用：
1. 栈应用之函数调用栈
操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构，用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。
这个应用是最广泛的，因为实际开发过程中，我们到处都在写函数，函数的调用过程其实就是不断的入栈出栈的过程。
如下的例子，两个函数对应两个栈帧，main函数先入栈，然后调用了add函数将其入栈。
两个栈帧
2. 栈应用之表达式求值
给一个运算 34+13*9+44-12/3，用脚都能算出来这个结果是多少，但是要让编译器给我们算还得想办法，我们写一套规则让编译器实现，因为运算符是有优先级的。
实际上，编译器就是通过两个栈来实现的，编译器实现步骤：
- 一个保存操作数的栈，另一个是保存运算符的栈；
- 从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈;当遇到运算符，就与运算符栈的栈顶元素进行比较。
- 如果比运算符栈顶元素的优先级高，就将当前运算符压入栈;
- 如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取2个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。
表达式实现过程分解
这个应用也是比较广泛的吧，算数喽～
3. 栈应用之括号匹配
具体的场景，我拿力扣的括号题来举例，这道题就是对栈典型的应用，实际开发中括号也是用的很多的场景。
leetcode栈典型应用
4. 栈应用之浏览器前进后退功能
这个功能，想必大家经常用吧，现在就来看看怎么用栈实现吧。
- 我们使用两个栈，X和Y，我们把首次浏览的页面依次压入栈X；
- 当点击后退按钮时，再依次从栈X中出栈，并将出栈的数据依次放入栈Y。
- 当我们点击前进按钮时，我们依次从栈Y中取出数据，放入栈X中。
- 当栈X中没有数据时，那就说明没有页面可以继续后退浏览了。当栈Y中没有数据，那就说明没有页面可以点击前进按钮浏览了。
浏览器前进后退跳新页面示意图
队列
队列也是一种操作受限的结构，仅允许在表的一端进行插，而在表的另一端进行删除，插入的一端称做队尾(rear),进行删除的一端称做队首(front)，满足先进先出原则。同样分为顺序队列和链式队列两种
顺序队列和链式队列
顺序队列入队出队：
a1出队，front指向a1
链式队列入队出队：
链队列
链式队列入队出队
队列应用之生产者消费者模型
阻塞队列
阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回;
如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。
这种场景，就是典型的生产者消费者模型。
生产者消费者模型
基于阻塞队列，我们还可以通过协调“生产者”和“消费者”的个数，来提高数据的处理效率。比如前面的例子，我们可以多配置几个“消费者”，来应 对一个“生产者”。
多个消费者应对一个生产者
用过中间件rabbitmq的朋友，想必对这些东西很熟悉。
队列本身其实就是个排队的过程，实际中很多场景都会进行排队，前几天吃了顿牛蛙也是取票排队来着，因此这种场景用队列这种数据结构就特别的合适。
算法 链表反转
上篇链表的算法题一：
反转链表
首先最开始想到的还是暴力递归，
- 使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 ret
- 此后，每次函数在返回的过程中，让当前结点的下一个结点的 nextnext 指针指向当前节点。
- 同时让当前结点的 next 指针指向 NULL，从而实现从链表尾部开始的局部反转
- 当递归函数全部出栈后，链表反转完成。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode* ret = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return ret;
}
};
算法 链表环检测
上篇链表的算法题二：
链表环检测
- 哈希表实现
利用 hashSet 中，每个元素都不重复的特点，我们遍历所有结点并在哈希表中存储每个结点的引用（或内存地址）。如果当前结点为空结点 null（即已检测到链表尾部的下一个结点），那么我们已经遍历完整个链表，并且该链表不是环形链表。如果当前结点的引用已经存在于哈希表中，那么返回 true（即该链表为环形链表）。
public boolean hasCycle(ListNode head) {
Set<ListNode> nodesSeen = new HashSet<>();
while (head != null) {
if (nodesSeen.contains(head)) {
return true;
} else {
nodesSeen.add(head);
}
head = head.next;
}
return false;
}
- 快慢指针
通过使用具有不同速度的快、慢两个指针遍历链表，空间复杂度可以被降低至 O(1)O(1)。慢指针每次移动一步，而快指针每次移动两步。
如果列表中不存在环，最终快指针将会最先到达尾部，此时我们可以返回 false。
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
算法 接雨水
超哥给的这道题看着就‘好看’啊，给hard题一点面子，下一篇就只写这一题吧，万一写不出来还很尴尬～
接雨水
参考资料：数据结构与算法之美，leetcode，极客时间算法训练营