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

    展开
     1
     473
  • 王争 置顶
    2018-11-01
    为什么函数调用要用“栈”来保存临时变量呢?用其他数据结构不行吗?

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

    从调用函数进入被调用函数,对于数据来说,变化的是什么呢?是作用域。所以根本上,只要能保证每进入一个新的函数,都是一个新的作用域就可以。而要实现这个,用栈就非常方便。在进入被调用函数的时候,分配一段栈空间给这个函数的变量,在函数结束的时候,将栈顶复位,正好回到调用函数的作用域内。
    展开
     5
     323
  • 他在她城断了弦
    2018-10-15
    leetcode上关于栈的题目大家可以先做20,155,232,844,224,682,496.
     6
     573
  • 姜威
    2018-10-08
    一、什么是栈?
    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里面的栈和我们这里说的是一回事,被称为方法栈。和前面函数调用的作用是一致的,用来存储方法中的局部变量。
    展开
     2
     217
  • 阿杜S考特
    2018-10-08
    内存中的堆栈和数据结构堆栈不是一个概念,可以说内存中的堆栈是真实存在的物理区,数据结构中的堆栈是抽象的数据存储结构。
            内存空间在逻辑上分为三部分:代码区、静态数据区和动态数据区,动态数据区又分为栈区和堆区。
    代码区:存储方法体的二进制代码。高级调度(作业调度)、中级调度(内存调度)、低级调度(进程调度)控制代码区执行代码的切换。
    静态数据区:存储全局变量、静态变量、常量,常量包括final修饰的常量和String常量。系统自动分配和回收。
    栈区:存储运行方法的形参、局部变量、返回值。由系统自动分配和回收。
    堆区:new一个对象的引用或地址存储在栈区,指向该对象存储在堆区中的真实数据。

    展开
     3
     196
  • 王争
    2018-11-01
    为什么函数调用要用“栈”来保存临时变量呢?用其他数据结构不行吗?

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

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

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

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

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

    -----

    还有,置顶留言中说,内存中的堆栈是真实存在的物理区,这个说法有点不精确,因为大部分人所说的,以及应用编程中所用到的内存,一般情况下指的都是虚拟内存空间,英文为:Virtual Memory,是物理内存的映射。
    展开
     3
     52
  • 姜威
    2018-10-08
    实现代码:(栈的数组实现)
    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;
    }
    }
    }
    展开
     1
     42
  • 清以轻尘
    2018-10-22
    关于这个浏览器的前进和后退,老师您说的是用两个栈实现,其实开篇我已经想到,但是,我还有一个很不错的解决思路,对于内存消耗可能会高点,但是时间复杂度也很低,就是使用双向链表,用 pre和next 来实现前进和后退

    作者回复: 也可以的 👍

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

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

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

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

    如果要回答为什么函数调用要要用栈,个人理解是CPU设计就是如此
    
     12
  • 乘坐Tornado的线程魔...
    2018-10-08
    想借此机会请教一个问题,同时也算是给大家的一道思考题。如果文中计算表达式的例子 涉及到小括号(默认小括号使用合法) 该如何处理呢?

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

     1
     9
  • Smallfly
    2018-10-08
    函数调用为什么用栈实现,其中一个原因是为了满足递归的需求。
    
     9
  • hao
    2018-10-15
    请问老师,3+5*8-6的栈计算演示图的第5步和第6步中间是不是省略了一步40 3 + 啊?不然如果表达式是3+5*8/2-6的结果就不对了。谢谢您

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

    
     8
我们在线,来聊聊吧