算法分析与数据结构心得体会（极客算法训练笔记）
算法分析与数据结构心得体会（极客算法训练笔记）实际上，编译器就是通过两个栈来实现的，编译器实现步骤：给一个运算 34 13*9 44-12/3，用脚都能算出来这个结果是多少，但是要让编译器给我们算还得想办法，我们写一套规则让编译器实现，因为运算符是有优先级的。操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构，用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。这个应用是最广泛的，因为实际开发过程中，我们到处都在写函数，函数的调用过程其实就是不断的入栈出栈的过程。如下的例子，两个函数对应两个栈帧，main函数先入栈，然后调用了add函数将其入栈。
- 栈
- 顺序栈和链栈
- 1. 栈应用之函数调用栈
- 2. 栈应用之表达式求值
- 3. 栈应用之括号匹配
- 4. 栈应用之浏览器前进后退功能
- 队列
- 顺序队列和链式队列
- 队列应用之生产者消费者模型
- 算法 链表反转
- 算法 链表环检测
- 算法 接雨水
❝ 没有最好的数据结构，只有最合适的数据结构。
❞
栈和队列都是操作受限的数据结构，那么为什么不直接用数组和链表呢？事实上，从功能上来说，数组或链表确实可以替代栈，因为栈其实就是通过数组和链表来实现的，但是，特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错，所谓能力越大责任越大就是这个道理。
栈顺序栈和链栈栈只允许在一端进行插入和删除数据，满足先进后出，后进先出的特点，有数组实现的顺序栈和链表实现的链栈两种。
栈应用：
1. 栈应用之函数调用栈操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构，用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。
这个应用是最广泛的，因为实际开发过程中，我们到处都在写函数，函数的调用过程其实就是不断的入栈出栈的过程。
如下的例子，两个函数对应两个栈帧，main函数先入栈，然后调用了add函数将其入栈。
给一个运算 34 13*9 44-12/3，用脚都能算出来这个结果是多少，但是要让编译器给我们算还得想办法，我们写一套规则让编译器实现，因为运算符是有优先级的。
实际上，编译器就是通过两个栈来实现的，编译器实现步骤：
- 一个保存操作数的栈，另一个是保存运算符的栈；
- 从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈;当遇到运算符，就与运算符栈的栈顶元素进行比较。
- 如果比运算符栈顶元素的优先级高，就将当前运算符压入栈;
- 如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取2个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。
这个应用也是比较广泛的吧，算数喽～
3. 栈应用之括号匹配具体的场景，我拿力扣的括号题来举例，这道题就是对栈典型的应用，实际开发中括号也是用的很多的场景。
这个功能，想必大家经常用吧，现在就来看看怎么用栈实现吧。
- 我们使用两个栈，X和Y，我们把首次浏览的页面依次压入栈X；
- 当点击后退按钮时，再依次从栈X中出栈，并将出栈的数据依次放入栈Y。
- 当我们点击前进按钮时，我们依次从栈Y中取出数据，放入栈X中。
- 当栈X中没有数据时，那就说明没有页面可以继续后退浏览了。当栈Y中没有数据，那就说明没有页面可以点击前进按钮浏览了。
队列也是一种操作受限的结构，仅允许在表的一端进行插，而在表的另一端进行删除，插入的一端称做队尾(rear) 进行删除的一端称做队首(front)，满足先进先出原则。同样分为顺序队列和链式队列两种
顺序队列和链式队列顺序队列入队出队：
链式队列入队出队：
阻塞队列
阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回;
如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。
这种场景，就是典型的生产者消费者模型。
基于阻塞队列，我们还可以通过协调“生产者”和“消费者”的个数，来提高数据的处理效率。比如前面的例子，我们可以多配置几个“消费者”，来应 对一个“生产者”。
用过中间件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，极客时间算法训练营
