一、将stack译作堆栈而不是栈的原因

最初的计算机科学相关的术语有时候是从其他领域引入的，或者是由一些早期计算机科学家为了方便而引入的。当实现 LIFO （后进先出）数据结构时，计算机科学家发现，类似于一个压缩块的数据结构可以用一个物理堆的形式堆积起来。于是这个数据结构就被称为“堆栈”（stack）而不是“栈”，尽管实际上它的内部结构就是一个栈的形式。这个术语已经广泛接受，并成为各种编程语言和数据结构文档的标准术语之一。所以，将 stack 译作堆栈而不是栈是因为历史原因和一些早期计算机科学家的命名习惯，并已成为行业标准。

二、stack简介

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

要搞清楚这个概念，首先要明白”栈“原来的意思，如此才能把握本质。栈,存储货物或供旅客住宿的地方,可引申为仓库、中转站，所以引入到计算机领域里，就是指数据暂时存储的地方，所以才有进栈、出栈的说法。

首先，系统或者数据结构栈中数据内容的读取与插入（压入）push和弹出pop是两回事。压入是增加数据，弹出是删除数据，这些操作只能从栈顶即最低地址作为约束的接口界面入手操作，但读取栈中的数据是随便的，没有接口约束之说。很多人都误解这个理念从而对栈产生困惑。而系统栈在计算机体系结构中又起到一个跨部件交互的媒介区域的作用 即 cpu 与内存的交流通道，cpu只从系统给我们自己编写的应用程序所规定的栈入口线性地读取执行指令，用一个形象的词来形容它就是pipeline（管道线、流水线）。cpu内部交互具体参见 EU与BIU的概念介绍。

栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被名列前茅个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(较好)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。

栈也称为先进后出表。栈可以用来在函数调用的时候存储断点，做递归时要用到栈。以上定义是在经典计算机科学中的解释。在计算机系统中，栈则是一个具有以上属性的动态内存区域。程序可以将数据压入栈中，也可以将数据从栈顶弹出。在i386机器中，栈顶由称为esp的寄存器进行定位。压栈的操作使得栈顶的地址减小，弹出的操作使得栈顶的地址增大。栈在程序的运行中有着举足轻重的作用。最重要的是栈保存了一个函数调用时所需要的维护信息，这常常称之为堆栈帧或者活动记录。堆栈帧一般包含如下几方面的信息：

三、stack的实现

C++代码如下：

#include using namespace std;class SqStack{private:    enum { MaxSize = 100 };    int data[MaxSize];    int 较好;public:    SqStack();    ~SqStack();    bool isEmpty();    void pushint(int x);    int popint();    int getTop();    void display();};SqStack::SqStack(){    较好 = -1;}SqStack::~SqStack() {}bool SqStack::isEmpty() //判断栈为空{    return(较好 == -1);}void SqStack::pushint(int x)//元素进栈{    if (较好 == MaxSize - 1)    {        cout << "栈上溢出！" << endl;    }    else    {        ++较好;        data[较好] = x;    }}int SqStack::popint()//退栈{    int tmp = 0;    if (较好 == -1)    {        cout << "栈已空！" <= 0; --index)    {        cout << data[index] << endl;    }}int main(){    SqStack st;    cout << "栈空：" << st.isEmpty() << endl;    for (int i = 1; i < 10; i++)    {        st.pushint(i);    }    st.display();    cout << "退一次栈" << endl;    st.popint();    cout << "栈顶元素:" << st.getTop() << endl;    st.popint();    st.display();    return 0;}

延伸阅读1：进栈算法

上一篇

红黑树在编程过程中到底是个什么样的地位?

下一篇

二叉树中的结点值指什么?