数据结构与算法之美 王争 学习笔记-3 [MD]
2021/8/2 11:05:58
本文主要是介绍数据结构与算法之美 王争 学习笔记-3 [MD],对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
博文地址
我的GitHub | 我的博客 | 我的微信 | 我的邮箱 |
---|---|---|---|
baiqiantao | baiqiantao | bqt20094 | baiqiantao@sina.com |
目录
目录- 目录
- 08 | 栈:如何实现浏览器的前进和后退功能?
- 如何实现一个“栈”?
- 基于数组实现的顺序栈
- 支持动态扩容的顺序栈
- 栈的应用场景
- 栈在函数调用中的应用
- 栈在表达式求值中的应用
- 栈在括号匹配中的应用
- 解答开篇
- 内容小结
- 如何实现一个“栈”?
- 09 | 队列:队列在线程池等有限资源池中的应用
- 如何理解“队列”?
- 顺序队列和链式队列
- 用数组实现的队列
- 用链表实现的队列
- 循环队列
- 阻塞队列和并发队列
- 内容小结
- 如何实现无锁并发队列?
08 | 栈:如何实现浏览器的前进和后退功能?
栈是一种操作受限
的线性表
,只允许在一端插入和删除数据。
从功能上来说,数组或链表也可以替代栈,但特定的数据结构是对特定场景的抽象,数组或链表暴露了太多的操作接口,操作上的确灵活自由,但使用时就比较不可控,自然也就更容易出错。
当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出
、先进后出
的特性,这时我们就应该首选栈这种数据结构。
如何实现一个“栈”?
栈既可以用数组
来实现,也可以用链表
来实现。用数组实现的栈,我们叫作顺序栈
,用链表实现的栈,我们叫作链式栈
。
基于数组实现的顺序栈
public class ArrayStack { private String[] items; // 数组 private int count; // 栈中元素个数 private int n; //栈的大小 // 初始化数组,申请一个大小为n的数组空间 public ArrayStack(int n) { this.items = new String[n]; this.n = n; this.count = 0; } // 入栈操作 public boolean push(String item) { // 数组空间不够了,直接返回false,入栈失败。 if (count == n) return false; // 将item放到下标为count的位置,并且count加一 items[count] = item; ++count; return true; } // 出栈操作 public String pop() { // 栈为空,则直接返回null if (count == 0) return null; // 返回下标为 count-1 的数组元素,并且栈中元素个数count减一 String tmp = items[count-1]; --count; return tmp; } }
在入栈和出栈过程中,只需要一两个临时变量存储空间,所以空间复杂度是
O(1)
入栈、出栈只涉及栈顶个别数据的操作,所以时间复杂度是O(1)
支持动态扩容的顺序栈
要实现一个支持动态扩容的栈,我们只需要底层依赖一个支持动态扩容的数组
就可以了。当栈满了之后,我们就申请一个更大的数组,将原来的数据搬移到新数组中。
均摊时间复杂度为
O(1)
栈的应用场景
栈在函数调用中的应用
操作系统给每个线程
分配了一块独立的内存空间,这块内存被组织成栈这种结构,用来存储函数调用时的临时变量
。每进入一个函数,就会将临时变量作为一个栈帧
入栈,当被调用函数执行完成,返回之后,将这个函数对应的栈帧
出栈。
为什么函数调用要用栈来保存临时变量呢?用其他数据结构不行吗?
其实,我们不一定非要用栈来保存临时变量,只不过如果这个函数调用符合后进先出
的特性,用栈这种数据结构来实现,是最顺理成章的选择。
从调用函数进入被调用函数,对于数据来说,变化的是什么呢?是作用域
。所以根本上,只要能保证每进入一个新的函数,都是一个新的作用域就可以。而要实现这个,用栈就非常方便。在进入被调用函数的时候,分配一段栈空间给这个函数的变量,在函数结束的时候,将栈顶复位,正好回到调用函数的作用域内。
栈在表达式求值中的应用
编译器是如何利用栈来实现表达式求值的?
比如:3+5*8-6
。实际上,编译器就是通过两个栈来实现的。其中一个保存操作数
的栈,另一个是保存运算符
的栈。
我们从左向右遍历表达式,当遇到数字
,我们就直接压入操作数栈;当遇到运算符
,就与运算符栈的栈顶元素进行比较:
- 如果比运算符栈顶元素的优先级高
,就将当前运算符压入栈
- 如果比运算符栈顶元素的优先级低
或者相同,从运算符栈
中取栈顶运算符,从操作数栈
的栈顶取 2 个操作数,然后进行计算,再把计算完的结果压入操作数栈,继续比较
栈在括号匹配中的应用
可以借助栈来检查表达式中的括号
是否匹配。
解答开篇
用两个栈就可以非常完美的实现浏览器的前进、后退功能
- 我们使用两个栈,X 和 Y,我们把
首次
浏览的页面依次压入栈 X- 当点击
后退
按钮时,再依次从栈 X 中出栈,并将出栈的数据依次放入栈 Y - 当我们点击
前进
按钮时,我们依次从栈 Y 中取出数据,放入栈 X 中
- 当点击
- 当栈 X 中没有数据时,那就说明没有页面可以继续
后退
浏览了 - 当栈 Y 中没有数据,那就说明没有页面可以点击
前进
按钮浏览了
内容小结
栈是一种操作受限的数据结构,只支持入栈和出栈操作。后进先出
是它最大的特点。栈既可以通过数组实现,也可以通过链表来实现。不管基于数组还是链表,入栈、出栈的时间复杂度都为 O(1)
。除此之外,我们还讲了一种支持动态扩容的顺序栈,你需要重点掌握它的均摊时间复杂度分析方法。
09 | 队列:队列在线程池等有限资源池中的应用
CPU 资源是有限的,任务的处理速度与线程个数并不是线性正相关。相反,过多的线程反而会导致 CPU 频繁切换
,处理性能下降。所以,线程池
的大小一般都是综合考虑要处理任务的特点和硬件环境来设置的。
对于大部分资源有限的场景,当没有空闲资源时,基本上都可以通过
队列
这种数据结构来实现请求排队。
如何理解“队列”?
队列跟栈一样,也是一种操作受限
的线性表
数据结构。
栈只支持两个基本操作:入栈 push()
和出栈 pop()
。
队列跟栈非常相似,支持的操作也很有限,最基本的操作也是两个:入队 enqueue()
,放一个数据到队列尾部;出队 dequeue()
,从队列头部取一个元素。
作为一种非常基础的数据结构,队列的应用也非常广泛,特别是一些具有某些额外特性的队列,比如循环队列
、阻塞队列
、并发队列
。它们在很多偏底层系统、框架、中间件的开发中,起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存,都用到了循环并发队列;Java concurrent 并发包利用 ArrayBlockingQueue
来实现公平锁等。
顺序队列和链式队列
跟栈一样,队列可以用数组来实现,也可以用链表来实现。用数组实现的栈叫作顺序栈
,用链表实现的栈叫作链式栈
。同样,用数组实现的队列叫作顺序队列
,用链表实现的队列叫作链式队列
。
用数组实现的队列
public class ArrayQueue { // 数组:items,数组大小:n private String[] items; private int n = 0; // head表示队头下标,tail表示队尾下标 private int head = 0; private int tail = 0; // 申请一个大小为capacity的数组 public ArrayQueue(int capacity) { items = new String[capacity]; n = capacity; } // 入队操作,将item放入队尾 public boolean enqueue(String item) { // tail == n表示队列末尾没有空间了 if (tail == n) { // tail ==n && head==0,表示整个队列都占满了 if (head == 0) return false; // 数据搬移 for (int i = head; i < tail; ++i) { items[i-head] = items[i]; } // 搬移完之后重新更新head和tail tail -= head; head = 0; } items[tail] = item; ++tail; return true; } // 出队 public String dequeue() { // 如果head == tail 表示队列为空 if (head == tail) return null; // 为了让其他语言的同学看的更加明确,把--操作放到单独一行来写了 String ret = items[head]; ++head; return ret; } }
均摊复杂度的使用的前提条件是,最好时间复杂的和最坏时间复杂度出现的频率很有规律,且有一定的前后时序关系。但这里,他的出现频率完全取决于调用者如何去在代码中进行出栈入栈操作,因此无法对均摊和平均进行复杂度分析。
用链表实现的队列
基于链表的实现,我们同样需要两个指针:head 指针和 tail 指针。它们分别指向链表的第一个结点和最后一个结点。
如图所示,入队时,tail.next= new_node
, tail = tail.next
;出队时,head = head.next
。
循环队列
我们刚才用数组来实现队列的时候,在 tail==n
时,会有数据搬移操作,这样入队操作性能就会受到影响。使用循环队列就能够避免数据搬移。
当队列满时,图中的 tail 指向的位置实际上是没有存储数据的。所以,循环队列会浪费数组的一个存储空间。
最关键的是,确定好队空和队满的判定条件
- 队列为空的判断条件是
head == tail
- 队列满的判断条件是
(tail+1)%n=head
public class CircularQueue { // 数组:items,数组大小:n private String[] items; private int n = 0; // head表示队头下标,tail表示队尾下标 private int head = 0; private int tail = 0; // 申请一个大小为capacity的数组 public CircularQueue(int capacity) { items = new String[capacity]; n = capacity; } // 入队 public boolean enqueue(String item) { // 队列满了 if ((tail + 1) % n == head) return false; items[tail] = item; tail = (tail + 1) % n; return true; } // 出队 public String dequeue() { // 如果head == tail 表示队列为空 if (head == tail) return null; String ret = items[head]; head = (head + 1) % n; return ret; } }
阻塞队列和并发队列
队列这种数据结构很基础,平时的业务开发不大可能从零实现一个队列,甚至都不会直接用到。而一些具有特殊特性的队列应用却比较广泛,比如阻塞队列和并发队列。
阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说,就是在队列为空的时候,从队头取数据会被阻塞。因为此时还没有数据可取,直到队列中有了数据才能返回;如果队列已经满了,那么插入数据的操作就会被阻塞,直到队列中有空闲位置后再插入数据,然后再返回。
你应该已经发现了,上述的定义就是一个生产者 - 消费者模型
!是的!
线程安全的队列
我们叫作并发队列
。最简单直接的实现方式是直接在 enqueue()
、dequeue()
方法上加锁,但是锁粒度大并发度会比较低,同一时刻仅允许一个存或者取操作。实际上,基于数组的循环队列,利用 CAS
原子操作,可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。
内容小结
队列最大的特点就是先进先出
,主要的两个操作是入队和出队
。跟栈一样,它既可以用数组来实现,也可以用链表来实现。用数组实现的叫顺序队列,用链表实现的叫链式队列。在数组实现队列的时候,会有数据搬移操作,要想解决数据搬移的问题,我们就需要像环一样的循环队列
。
阻塞队列就是入队、出队操作可以阻塞,并发队列就是队列的操作多线程安全。
如何实现无锁并发队列?
考虑使用CAS
实现无锁队列
- 在入队前,获取 tail 位置,入队时比较 tail 是否发生变化,如果否,则允许入队,反之,本次入队失败
- 出队则是获取 head 位置,进行 cas
这篇关于数据结构与算法之美 王争 学习笔记-3 [MD]的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-22项目:远程温湿度检测系统
- 2024-12-21《鸿蒙HarmonyOS应用开发从入门到精通(第2版)》简介
- 2024-12-21后台管理系统开发教程:新手入门全指南
- 2024-12-21后台开发教程:新手入门及实战指南
- 2024-12-21后台综合解决方案教程:新手入门指南
- 2024-12-21接口模块封装教程:新手必备指南
- 2024-12-21请求动作封装教程:新手必看指南
- 2024-12-21RBAC的权限教程:从入门到实践
- 2024-12-21登录鉴权实战:新手入门教程
- 2024-12-21动态权限实战入门指南