数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

08 | 栈:如何实现浏览器的前进和后退功能?

王争 2018-10-08
浏览器的前进、后退功能,我想你肯定很熟悉吧?
当你依次访问完一串页面 a-b-c 之后,点击浏览器的后退按钮,就可以查看之前浏览过的页面 b 和 a。当你后退到页面 a,点击前进按钮,就可以重新查看页面 b 和 c。但是,如果你后退到页面 b 后,点击了新的页面 d,那就无法再通过前进、后退功能查看页面 c 了。
假设你是 Chrome 浏览器的开发工程师,你会如何实现这个功能呢?
这就要用到我们今天要讲的“栈”这种数据结构。带着这个问题,我们来学习今天的内容。

如何理解“栈”?

关于“栈”,我有一个非常贴切的例子,就是一摞叠在一起的盘子。我们平时放盘子的时候,都是从下往上一个一个放;取的时候,我们也是从上往下一个一个地依次取,不能从中间任意抽出。后进者先出,先进者后出,这就是典型的“栈”结构。
从栈的操作特性上来看,栈是一种“操作受限”的线性表,只允许在一端插入和删除数据。
我第一次接触这种数据结构的时候,就对它存在的意义产生了很大的疑惑。因为我觉得,相比数组和链表,栈带给我的只有限制,并没有任何优势。那我直接使用数组或者链表不就好了吗?为什么还要用这个“操作受限”的“栈”呢?
事实上,从功能上来说,数组或链表确实可以替代栈,但你要知道,特定的数据结构是对特定场景的抽象,而且,数组或链表暴露了太多的操作接口,操作上的确灵活自由,但使用时就比较不可控,自然也就更容易出错。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(264)

  • 阿杜S考特 置顶
    内存中的堆栈和数据结构堆栈不是一个概念,可以说内存中的堆栈是真实存在的物理区,数据结构中的堆栈是抽象的数据存储结构。
            内存空间在逻辑上分为三部分:代码区、静态数据区和动态数据区,动态数据区又分为栈区和堆区。
    代码区:存储方法体的二进制代码。高级调度(作业调度)、中级调度(内存调度)、低级调度(进程调度)控制代码区执行代码的切换。
    静态数据区:存储全局变量、静态变量、常量,常量包括final修饰的常量和String常量。系统自动分配和回收。
    栈区:存储运行方法的形参、局部变量、返回值。由系统自动分配和回收。
    堆区:new一个对象的引用或地址存储在栈区,指向该对象存储在堆区中的真实数据。

    2018-10-08
    1
    436
  • 王争 置顶
    为什么函数调用要用“栈”来保存临时变量呢?用其他数据结构不行吗?

    其实,我们不一定非要用栈来保存临时变量,只不过如果这个函数调用符合后进先出的特性,用栈这种数据结构来实现,是最顺理成章的选择。

    从调用函数进入被调用函数,对于数据来说,变化的是什么呢?是作用域。所以根本上,只要能保证每进入一个新的函数,都是一个新的作用域就可以。而要实现这个,用栈就非常方便。在进入被调用函数的时候,分配一段栈空间给这个函数的变量,在函数结束的时候,将栈顶复位,正好回到调用函数的作用域内。
    2018-11-01
    4
    289
  • 他在她城断了弦
    leetcode上关于栈的题目大家可以先做20,155,232,844,224,682,496.
    2018-10-15
    3
    515
  • 姜威
    一、什么是栈?
    1.后进者先出,先进者后出,这就是典型的“栈”结构。
    2.从栈的操作特性来看,是一种“操作受限”的线性表,只允许在端插入和删除数据。
    二、为什么需要栈?
    1.栈是一种操作受限的数据结构,其操作特性用数组和链表均可实现。
    2.但,任何数据结构都是对特定应用场景的抽象,数组和链表虽然使用起来更加灵活,但却暴露了几乎所有的操作,难免会引发错误操作的风险。
    3.所以,当某个数据集合只涉及在某端插入和删除数据,且满足后进者先出,先进者后出的操作特性时,我们应该首选栈这种数据结构。
    三、如何实现栈?
    1.栈的API
    public class Stack<Item> {
    //压栈
    public void push(Item item){}
    //弹栈
    public Item pop(){}
    //是否为空
    public boolean isEmpty(){}
    //栈中数据的数量
    public int size(){}
    //返回栈中最近添加的元素而不删除它
    public Item peek(){}
    }
    2.数组实现(自动扩容)
    时间复杂度分析:根据均摊复杂度的定义,可以得数组实现(自动扩容)符合大多数情况是O(1)级别复杂度,个别情况是O(n)级别复杂度,比如自动扩容时,会进行完整数据的拷贝。
    空间复杂度分析:在入栈和出栈的过程中,只需要一两个临时变量存储空间,所以O(1)级别。我们说空间复杂度的时候,是指除了原本的数据存储空间外,算法运行还需要额外的存储空间。
    实现代码:(见另一条留言)

    3.链表实现
    时间复杂度分析:压栈和弹栈的时间复杂度均为O(1)级别,因为只需更改单个节点的索引即可。
    空间复杂度分析:在入栈和出栈的过程中,只需要一两个临时变量存储空间,所以O(1)级别。我们说空间复杂度的时候,是指除了原本的数据存储空间外,算法运行还需要额外的存储空间。
    实现代码:(见另一条留言)

    四、栈的应用
    1.栈在函数调用中的应用
    操作系统给每个线程分配了一块独立的内存空间,这块内存被组织成“栈”这种结构,用来存储函数调用时的临时变量。每进入一个函数,就会将其中的临时变量作为栈帧入栈,当被调用函数执行完成,返回之后,将这个函数对应的栈帧出栈。
    2.栈在表达式求值中的应用(比如:34+13*9+44-12/3)
    利用两个栈,其中一个用来保存操作数,另一个用来保存运算符。我们从左向右遍历表达式,当遇到数字,我们就直接压入操作数栈;当遇到运算符,就与运算符栈的栈顶元素进行比较,若比运算符栈顶元素优先级高,就将当前运算符压入栈,若比运算符栈顶元素的优先级低或者相同,从运算符栈中取出栈顶运算符,从操作数栈顶取出2个操作数,然后进行计算,把计算完的结果压入操作数栈,继续比较。
    3.栈在括号匹配中的应用(比如:{}{[()]()})
    用栈保存为匹配的左括号,从左到右一次扫描字符串,当扫描到左括号时,则将其压入栈中;当扫描到右括号时,从栈顶取出一个左括号,如果能匹配上,则继续扫描剩下的字符串。如果扫描过程中,遇到不能配对的右括号,或者栈中没有数据,则说明为非法格式。
    当所有的括号都扫描完成之后,如果栈为空,则说明字符串为合法格式;否则,说明未匹配的左括号为非法格式。
    4.如何实现浏览器的前进后退功能?
    我们使用两个栈X和Y,我们把首次浏览的页面依次压如栈X,当点击后退按钮时,再依次从栈X中出栈,并将出栈的数据一次放入Y栈。当点击前进按钮时,我们依次从栈Y中取出数据,放入栈X中。当栈X中没有数据时,说明没有页面可以继续后退浏览了。当Y栈没有数据,那就说明没有页面可以点击前进浏览了。
    五、思考
    1. 我们在讲栈的应用时,讲到用函数调用栈来保存临时变量,为什么函数调用要用“栈”来保存临时变量呢?用其他数据结构不行吗?
    答:因为函数调用的执行顺序符合后进者先出,先进者后出的特点。比如函数中的局部变量的生命周期的长短是先定义的生命周期长,后定义的生命周期短;还有函数中调用函数也是这样,先开始执行的函数只有等到内部调用的其他函数执行完毕,该函数才能执行结束。
    正是由于函数调用的这些特点,根据数据结构是特定应用场景的抽象的原则,我们优先考虑栈结构。
    2.我们都知道,JVM 内存管理中有个“堆栈”的概念。栈内存用来存储局部变量和方法调用,堆内存用来存储 Java 中的对象。那 JVM 里面的“栈”跟我们这里说的“栈”是不是一回事呢?如果不是,那它为什么又叫作“栈”呢?
    答:JVM里面的栈和我们这里说的是一回事,被称为方法栈。和前面函数调用的作用是一致的,用来存储方法中的局部变量。
    2018-10-08
    2
    204
  • 阿杜S考特
    内存中的堆栈和数据结构堆栈不是一个概念,可以说内存中的堆栈是真实存在的物理区,数据结构中的堆栈是抽象的数据存储结构。
            内存空间在逻辑上分为三部分:代码区、静态数据区和动态数据区,动态数据区又分为栈区和堆区。
    代码区:存储方法体的二进制代码。高级调度(作业调度)、中级调度(内存调度)、低级调度(进程调度)控制代码区执行代码的切换。
    静态数据区:存储全局变量、静态变量、常量,常量包括final修饰的常量和String常量。系统自动分配和回收。
    栈区:存储运行方法的形参、局部变量、返回值。由系统自动分配和回收。
    堆区:new一个对象的引用或地址存储在栈区,指向该对象存储在堆区中的真实数据。

    2018-10-08
    2
    196
  • 王争
    为什么函数调用要用“栈”来保存临时变量呢?用其他数据结构不行吗?

    其实,我们不一定非要用栈来保存临时变量,只不过如果这个函数调用符合后进先出的特性,用栈这种数据结构来实现,是最顺理成章的选择。

    从调用函数进入被调用函数,对于数据来说,变化的是什么呢?是作用域。所以根本上,只要能保证每进入一个新的函数,都是一个新的作用域就可以。而要实现这个,用栈就非常方便。在进入被调用函数的时候,分配一段栈空间给这个函数的变量,在函数结束的时候,将栈顶复位,正好回到调用函数的作用域内。

    作者回复: 答案 大家可以参考下

    2018-11-01
    3
    121
  • 小洋洋
    函数调用之所以用栈,是因为函数调用中经常嵌套,栗子:A调用B,B又调用C,那么就需要先把C执行完,结果赋值给B中的临时变量,B的执行结果再赋值给A的临时变量,嵌套越深的函数越需要被先执行,这样刚好符合栈的特点,因此每次遇到函数调用,只需要压栈,最后依次从栈顶弹出依次执行即可,这个过程很像文稿中的3+5*8-6//小白之拙见,欢迎拍砖*^o^*
    2018-10-08
    4
    100
  • 鲫鱼
    对我来说理解有些困难,所以姜威的笔记给了我很大的帮助的。给了我更好完善笔记的构架,以及用不同方式解释加深理解和记忆。真的有的人不喜欢看不看就好,划掉不过两秒的事情。
    2018-10-10
    65
  • Jerry银银
    置顶的留言中还有一个问题没有回答——为什么内存中的“栈”也叫“栈”,而且英文都是stack?

    我认为,虽然内存中的栈和数据结构的栈不是一回事,即内存中的栈是一段虚拟的内存空间,数据结构中的栈是一种抽象的数据类型,但是它们都有“栈”的特性——后进先出,所以都叫“栈”也无可厚非。

    -----

    还有,置顶留言中说,内存中的堆栈是真实存在的物理区,这个说法有点不精确,因为大部分人所说的,以及应用编程中所用到的内存,一般情况下指的都是虚拟内存空间,英文为:Virtual Memory,是物理内存的映射。
    2019-03-07
    3
    45
  • 姜威
    实现代码:(栈的数组实现)
    public class StackOfArray<Item> implements Iterable<Item>{
    //存储数据的数组
    Item[] a = (Item[])new Object[1];
    //记录元素个数N
    int N = 0;
    //构造器
    public StackOfArray(){}
    //添加元素
    public void push(Item item){
    //自动扩容
    if (N == a.length ) resize(2*a.length );
    a[N++] = item;
    }
    //删除元素
    public Item pop(){
    Item item = a[--N];
    a[N] = null;
    if (N > 0 && N == a.length / 4) resize(a.length / 2);
    return item;
    }
    //是否为空
    public boolean isEmpty(){
    return N == 0;
    }
    //元素个数
    public int size(){
    return N;
    }
    //改变数组容量
    private void resize(int length) {
    Item[] temp = (Item[])new Object[length];
    for (int i = 0; i < N; i++) {
    temp[i] = a[i];
    }
    a = temp;
    }
    //返回栈中最近添加的元素而不删除它
    public Item peek(){
    return a[N-1];
    }
    @Override
    public Iterator<Item> iterator() {
    return new ArrayIterator();
    }
    //内部类
    class ArrayIterator implements Iterator{
    //控制迭代数量
    int i = N;
    @Override
    public boolean hasNext() {
    return i > 0;
    }
    @Override
    public Item next() {
    return a[--i];
    }
    }
    }

    实现代码:(栈的链表实现)
    public class StackOfLinked<Item> implements Iterable<Item> {
    //定义一个内部类,就可以直接使用类型参数
    private class Node{
    Item item;
    Node next;
    }
    private Node first;
    private int N;
    //构造器
    public StackOfLinked(){}
    //添加
    public void push(Item item){
    Node oldfirst = first;
    first = new Node();
    first.item = item;
    first.next = oldfirst;
    N++;
    }
    //删除
    public Item pop(){
    Item item = first.item;
    first = first.next;
    N--;
    return item;
    }
    //是否为空
    public boolean isEmpty(){
    return N == 0;
    }
    //元素数量
    public int size(){
    return N;
    }
    //返回栈中最近添加的元素而不删除它
    public Item peek(){
    return first.item;
    }
    @Override
    public Iterator<Item> iterator() {
    return new LinkedIterator();
    }
    //内部类:迭代器
    class LinkedIterator implements Iterator{
    int i = N;
    Node t = first;
    @Override
    public boolean hasNext() {
    return i > 0;
    }
    @Override
    public Item next() {
    Item item = (Item) t.item;
    t = t.next;
    i--;
    return item;
    }
    }
    }
    2018-10-08
    1
    41
  • 清以轻尘
    关于这个浏览器的前进和后退,老师您说的是用两个栈实现,其实开篇我已经想到,但是,我还有一个很不错的解决思路,对于内存消耗可能会高点,但是时间复杂度也很低,就是使用双向链表,用 pre和next 来实现前进和后退

    作者回复: 也可以的 👍

    2018-10-22
    2
    33
  • Monday
    对于每次留下的思考题都希望老师在n(n>1)天后给出权威的答案,谢谢。
    国庆在家里只看文档和听音频没有记录笔记,回去工作了,一定补上。个人认为本课题是最实惠的知识付费,没有之一。❤

    作者回复: 关于思考题 很多同学的留言都已经回答的很好了 关于权威答案 我可以集中写篇文章说说

    2018-10-09
    26
  • thewangzl
    JVM中的“栈”应该有两个。
    一个是每个线程中方法调用用到的栈。该栈以栈帧为元素,当调用一个方法时,会把方法相关的局部变量表、操作数栈、方法返回地址等信息封装到栈帧中,把该栈帧入栈;当方法执行结束后,把该栈帧出栈。
    第二个栈就是栈帧中的操作数栈。JVM的解释执行引擎是“基于栈的执行引擎”,是因为JVM的指令都是对操作数栈中的元素进行入栈出栈操作。
    两者应该都是标准的栈。
    2018-10-08
    22
  • Liam
    1 函数调用和返回符合后进先出原则,而局部变量的生命周期应该和函数一致,因此用栈保存局部变量是合适的,函数出栈时同时销毁局部变量

    2 jvm的栈就是一种栈数据结构,本质相同
    2018-10-08
    18
  • 席尔
    老师早上好!想请问下:如果当前栈大小为 K,并且已满,当再有新的数据要入栈时,就需要重新申请 2 倍大小的内存,并且做 K 个数据的搬移操作,然后再入栈。但是,接下来的 K-1 次入栈操作?
     不是k次入栈操作吗?为什么是k–1次? 新的栈空间还剩余k的大小呀,不是还能进行k次入栈操作吗?麻烦老师解答一下,非常感谢!
    2019-01-11
    5
    13
  • zyzheng
    函数调用使用的栈是有硬件基础的,所有的CPU都有相应的SP寄存器用于存储栈顶指针,也有相应的入栈出栈指令,用于实现函数调用栈效率很高,和软件数据结构的栈有所不同。

    如果要回答为什么函数调用要要用栈,个人理解是CPU设计就是如此
    2018-10-08
    12
  • 小邓
    课后思考问题2是多次困扰我的一个问题:内存管理上的“栈”和数据结构上的“栈”到底是不是一回事。
    按出题套路而言,问“如果不是,给出理由”的问题答案大多是“不是”。高赞留言里有的说是,有的说不是,我简单翻了翻三大本厚书《C#图接教程》、《算法》、《深入理解计算机基础》,再去翻了翻相关博客和知乎,我的回答是“不是”。
    (1)首先,在内存管理和数据结构上,都有“堆”和“栈”这两个概念。
    (2)内存管理上的“堆”和“栈”,强调的是数据的生命周期(分配释放是否有次序要求);数据结构上的“堆”和“栈”,强调的是数据的组织。
    (3)内存管理上的“栈”符合数据结构的“栈”的特点,即LIFO,两者同名可以接受。
    (4)数据结构上的“堆”定义:它是一种数组对象,它可以被视为一科完全二叉树结构;应用场景包括堆排序,优先队列等。和内存管理的“堆”定义不同(这里我不是很确定,没有看过内存管理上堆的实现细节)。

    参考:
    (1)数据结构之“堆”:http://www.cnblogs.com/Jason-Damon/archive/2012/04/18/2454649.html
    (2)专题 | 堆、栈简介:https://zhuanlan.zhihu.com/p/45597548
    (3)知乎| 为什么c++中要分为heap(堆)和stack(栈)? - Milo Yip的回答:https://www.zhihu.com/question/281940376/answer/424990646
    2019-04-11
    9
  • Smallfly
    函数调用为什么用栈实现,其中一个原因是为了满足递归的需求。
    2018-10-08
    9
  • hao
    请问老师,3+5*8-6的栈计算演示图的第5步和第6步中间是不是省略了一步40 3 + 啊?不然如果表达式是3+5*8/2-6的结果就不对了。谢谢您

    作者回复: 是的 第六步 处理了2个操作符

    2018-10-15
    7
  • 乘坐Tornado的线程魔法师
    想借此机会请教一个问题,同时也算是给大家的一道思考题。如果文中计算表达式的例子 涉及到小括号(默认小括号使用合法) 该如何处理呢?

    作者回复: 思路一样的 可以把右括号看作优先级最高的 至于左括号怎么处理 留给你思考吧😄

    2018-10-08
    1
    7
收起评论
99+
返回
顶部