❝没有最好的数据结构,只有最合适的数据结构。 ❞
栈和队列都是操作受限的数据结构,那么为什么不直接用数组和链表呢?事实上,从功能上来说,数组或链表确实可以替代栈,因为栈其实就是通过数组和链表来实现的,但是,特定的数据结构是对特定场景的抽象,而且,数组或链表暴露了太多的操作接口,操作上的确灵活自由,但使用时就比较不可控,自然也就更容易出错,所谓能力越大责任越大就是这个道理。
栈只允许在一端进行插入和删除数据,满足先进后出,后进先出的特点,有数组实现的顺序栈和链表实现的链栈两种。
顺序栈
链栈
栈应用:
操作系统给每个线程分配了一块独立的内存空间,这块内存被组织成“栈”这种结构,用来存储函数调用时的临时变量。每进入一个函数,就会将临时变量作为一个栈帧入栈,当被调用函数执行完成,返回之后,将这个函数对应的栈帧出栈。
这个应用是最广泛的,因为实际开发过程中,我们到处都在写函数,函数的调用过程其实就是不断的入栈出栈的过程。
如下的例子,两个函数对应两个栈帧,main函数先入栈,然后调用了add函数将其入栈。
两个栈帧
给一个运算 34+13*9+44-12/3,用脚都能算出来这个结果是多少,但是要让编译器给我们算还得想办法,我们写一套规则让编译器实现,因为运算符是有优先级的。
实际上,编译器就是通过两个栈来实现的,编译器实现步骤:
表达式实现过程分解
这个应用也是比较广泛的吧,算数喽~
具体的场景,我拿力扣的括号题来举例,这道题就是对栈典型的应用,实际开发中括号也是用的很多的场景。
leetcode栈典型应用
这个功能,想必大家经常用吧,现在就来看看怎么用栈实现吧。
浏览器前进后退跳新页面示意图
队列也是一种操作受限的结构,仅允许在表的一端进行插,而在表的另一端进行删除,插入的一端称做队尾(rear),进行删除的一端称做队首(front),满足先进先出原则。同样分为顺序队列和链式队列两种
顺序队列入队出队:
a1出队,front指向a1
链式队列入队出队:
链队列
链式队列入队出队
阻塞队列
阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说,就是在队列为空的时候,从队头取数据会被阻塞。因为此时还没有数据可取,直到队列中有了数据才能返回;
如果队列已经满了,那么插入数据的操作就会被阻塞,直到队列中有空闲位置后再插入数据,然后再返回。
这种场景,就是典型的生产者消费者模型。
生产者消费者模型
基于阻塞队列,我们还可以通过协调“生产者”和“消费者”的个数,来提高数据的处理效率。比如前面的例子,我们可以多配置几个“消费者”,来应 对一个“生产者”。
多个消费者应对一个生产者
用过中间件rabbitmq的朋友,想必对这些东西很熟悉。
队列本身其实就是个排队的过程,实际中很多场景都会进行排队,前几天吃了顿牛蛙也是取票排队来着,因此这种场景用队列这种数据结构就特别的合适。
上篇链表的算法题一:
反转链表
首先最开始想到的还是暴力递归,
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,极客时间算法训练营