D4-认识栈结构

认识栈

  • 栈是一种常见的数据结构

  • 数组是一种线性结构，并且可在睡着任意位置插入和删除数据

  • 而栈和队列就是常见的 “受限的线性结构”

  • 栈结构图
    D4-认识栈结构 - 图1

  • 栈（stack），是一种受限的线性表，后进先出（LIFO）

    • 其受限制是仅允许在“D4-认识栈结构 - 图2” 进行插入和删除运算。这一端称为“D4-认识栈结构 - 图3”，相对为“D4-认识栈结构 - 图4“
    • LIFO(last in first out)表示最后进入的元素，第一个弹出栈空间。类似于自动餐托盘，最后放上的盘子，最先拿出去用，最后收到的邮件，最新被看到。程序就是生活的抽象体现。
    • 向一个栈插入新元素被称为 D4-认识栈结构 - 图5, D4-认识栈结构 - 图6或D4-认识栈结构 - 图7,它就是把新元素放在栈顶元素的上面，使之称为新的栈顶元素；
    • 向一个栈删除元素又被称为D4-认识栈结构 - 图8，就是把栈顶元素删除掉。使其相邻的元素称为新的栈顶元素

  • 程序中的应用：

    • 函数调用栈
    • 函数之间相互调用，A调用B，B调C，C又调用D
    • 执行的过程中，回先将A压入栈，A没有执行完，所有不会弹出栈
    • A执行过程中调用了B，会将B压入栈。这时候B在栈顶，A在栈底
    • 如果B执行完，B会弹出栈，但是By有执行完么，没有，又调用了C
    • 所以C会压栈，并在栈顶，而C调用了D，D会压入到栈顶
    • 所以：当前栈顺序：栈底A-B-C-D栈顶
    • D执行完，弹出栈，C/B/A依次弹出栈
    • 所以函数调用栈，就来自他们内部的实现机制（通过栈来实现的）
    • 而递归是一直调用自己，导致栈溢出。。