Question

什么是堆栈指针？怎么理解堆栈指针？

Answer 1

堆栈是一个抽象数据类型，规定的两项必备的基本操作分别为入栈和出栈。这个抽象数据类型并没规定入栈与出栈具体要怎么实现。你问的问题已经在实现这一层面 上，所以按照堆栈这种抽象数据类型的规定看，“先修改指针，然后插入数据，出栈时刚好相反”并不是必须的，这取决于你的操作的具体实现。 \x0d\x0a\x0d\x0a如果你的堆栈的实现是往上长的（就是说往顶的方向长，其实质是你的栈底是定死的不能动，入栈的东西只能不断往上叠，这就像你在书桌上放书一样，桌 底是定死的，所以你的书只能一本一本地往上堆，往上长），计算机内部的堆栈的实现采取的就是这种模式，所以就得像你说的那样，“先修改指针，然后插入数 据，出栈时刚好相反”，因为你堆栈指针指向的总是栈顶元素，栈底不能动，所以数据入栈前要先修改指针使它指向新的空余空间然后再把数据存进去，出栈的时候 自然相反，你联系我上面举的放书的例子仔细想想。 \x0d\x0a\x0d\x0a然而，如果你的堆栈的实现是往下长的（就是说你每压一个元素入栈，栈底就自动下移一个元素的位置，其实质就是这种堆栈模型是一个“无底洞”型）， 这个时候，你的栈顶就变成了定死的，你就可以先压入元素，然后再修改指针。因为你的栈底是无限的，你压入一个元素，新的元素就取代先前的栈顶元素占据栈顶 的位置，那么你先前的指向栈顶元素的指针这个时候就该修改让它指向这个新的栈顶元素了。 \x0d\x0a\x0d\x0a下面的就是对“无底洞”型堆栈的一种实现的描述： \x0d\x0a压栈（入栈）：将对象或者数据压入栈中，更新栈顶指针，使其指向最后入栈的对象或数据。 \x0d\x0a弹栈（出栈）：返回栈顶指向的对象或数据，并从栈中删除该对象或数据，更新栈顶。 \x0d\x0a\x0d\x0a话说回来，计算机内部肯定选第一种模型，不会选第二种，因为第二种模型，每压入一个新的元素，都需要把之前堆栈里的所有元素整体下移动一个元素的 位置，腾出栈顶元素的位置让新的元素进来，这种平移可是一笔不小的开销啊！但是并不是说“无底洞”模型就没办法实现了，其实它可以通过第一种模型来模拟 的，每需要压入一个新的元素的时候，就先开辟一个空间，数据存入这个空间，然后再修改栈顶元素指针使其指向这个新的栈顶元素。 \x0d\x0a\x0d\x0a换句话说，用链表的话，只要有足够的空间可开辟出来作为一个节点，那么两种堆栈模型都能实现（当然“无底洞”型还是如我上面说的那样用第一种模拟出来的，否则平移的工作量相当可观），如果用数组，由于数组在内存中是连续分配出来的空间，用第一种模型更自然一些