堆栈（Stack）是一种数据结构，它具有后进先出（Last In First Out，LIFO）的特点。在堆栈中，最后进栈的元素是最先出栈的，而最先进栈的元素要最后出栈。可以想象一下，我们平时玩扑克牌时，拿到的牌是依次叠在一起的，摸牌时我们是从最上面开始摸的，摸的越深就越靠近牌堆底部。这就是一个堆栈的典型示例。
在计算机中，函数调用时使用了堆栈这种数据结构。当一个函数被调用时，它的参数、局部变量和返回地址都被压入栈中，函数执行结束后再从栈中弹出这些数据，恢复调用函数的上下文。
堆栈指针（Stack Pointer）是指向堆栈顶部的指针。在计算机中，当需要将数据压入堆栈时，就将堆栈指针下移，指向新的栈顶元素。当需要弹出数据时，就将堆栈指针上移，指向原来的栈顶元素。
在一些汇编语言中，堆栈指针通常被称为 SP 寄存器，例如 x86 架构的汇编代码中使用的 SP 寄存器指向堆栈的栈顶。
堆栈在计算机领域有很广泛的应用，例如函数调用、表达式求值、语法分析等。
在函数调用中，堆栈被用于保存当前函数的上下文，包括函数参数、局部变量和返回地址等信息。当函数返回时，会将这些信息从堆栈中弹出，恢复调用函数的上下文。
在表达式求值时，堆栈被用于存储运算符和操作数。当遇到一个操作符时，先将它入栈，再将它的右操作数和左操作数分别出栈进行计算。
在语法分析时，堆栈被用于存储词法分析器输出的单词列表。语法分析器将根据语法规则将单词列表转换为语法分析树，而堆栈则是整个过程中存储单词列表的重要数据结构。
堆栈可以使用数组（Array）和链表（Linked List）两种数据结构来实现。
使用数组实现堆栈时，需要定义一个表示堆栈的数组和一个指向堆栈顶部元素的指针。当需要将一个元素压入堆栈时，将元素插入数组的末尾，并将指针加一；当需要弹出一个元素时，将指针减一，并返回指针所指向的元素即可。
使用链表实现堆栈时，每个链表节点都表示一个堆栈元素，而堆栈的顶部是最后一个节点。当需要将一个元素压入栈时，就新建一个节点放在链表尾部，更新顶部节点即可；当需要弹出一个元素时，将顶部节点删除，并更新顶部节点为前一个节点。
关注微信