大话数据结构4-栈

发表于 2020-10-22 更新于 2021-01-10 分类于 1- 编程相关，数据结构与算法阅读次数： Valine：

栈（stack）是一种后进先出的数据结构，实际上，这种结构运用非常普遍，例如浏览网页时，我们使用”后退”按键，word，PS 等软件的撤销操作，都是栈的应用。

I 栈的定义

实际上，栈也是一种线性表结构，只不过它的插入和删除操作限定在表尾进行。我们称这种为 “后进先出（Last in first out）”, 即 LIFO 结构。

通常的，我们将允许插入和删除的一端称为 栈顶（top），另一端则成为 栈底（bottom）。

向栈中添加元素称为 进栈操作，取出元素称为 出栈操作。事实上，不一定是最先进栈的元素一定最后一个出栈，例如，元素 1,2,3 按顺序进栈，它的出栈顺序可以是 3,2,1, 也可以是 1,2,3 (1进，1出，2进，2出，3进，3出)，2,1,3 … 对于3个元素按顺序进栈，合计共有5种可能的出栈顺序。

II 栈的抽象数据类型

将上述栈的定义代码化，将栈的相关操作用函数的形式表达出来，定义成为一个抽象的数据类型：

ADT stack
Data        //栈中的数据

Operation       //栈中的操作
    InitStack(*S);      //初始化栈，建立一个空栈 S
    DestroyStack(*S);       //若栈 S 存在，则销毁栈 S
    ClearStack(*S);         //将栈S清空
    StackEmpty(S);          //若栈为空，则返回 true，否则 false
    GetTop(S, *e);      //寻找 栈S 的头部，并将它的值赋值给e
    Push(*S, e);        //插入新元素 e 到栈中
    Pop(*S, *e);        //删除栈中的栈顶元素，并用e返回他的值
    StackLength(S);         //返回栈S 中的元素的个数

III 顺序存储结构实现栈

顺序存储即将栈中元素存放在物理上连续的区域内，可以使用类似数组的方式表示栈中的元素。具体的，入栈和出栈的代码如下所示。

/* 入栈操作 */
Status Push (SqStack *S, SElemType e){
    if(s->top == MAXSIZE - 1)   
        return ERROR;   //栈满

    S->top ++;  //栈顶指针加1
    S->data[S->top] = e;       //新元素插入在栈顶
    return OK;
}

/* 出栈操作 */
Status Pop(SqStack *S, SElemType *e){
    if(S->top == -1)        //注意空栈的判定方式
        return ERROR;

    *e = S->data[S->top];       //将要删除的栈顶元素赋值给e
    S->top --;          //栈顶指针减1
    return OK;
}

由于顺序存储结构固有的存储空间问题（存储空间需要事先分配，容易出现溢出问题），当两个栈中存储的元素相同时，我们可以通过两栈共享空间的方法，来提升空间利用率，降低溢出风险。

实际上，两栈共享空间 是一种头尾相接的结构，两个栈的栈顶指针向中间靠拢，只要两个栈顶指针不见面，两个栈就可以一直使用。向两栈共享的空间中添加、删除元素，如下所示：

/*添加元素*/
Status Push(SqDoubleStack *S, SElemType e, int StackNumber){
    if (S->top1 + 1 == S->top2)     //栈已满
        return ERROR;
    
    if(stackNumber == 1)
        S->data[++S->top1] = e;     //若是栈1中元素
    else if(stackNumber == 2)
        S->data[--S->top2] = e;      //若是栈2中的元素， top2 -1 后

    return OK;
}

/*弹出元素*/
Status Pop(SqDoubleStack *S, SElemType *e, int StackNumber){
    if(stackNumber == 1){
        if(S->top1 == -1)       //说明栈1已经是空
            return ERROR;
        *e = S->data[S->top1 --];       //将栈1中的栈顶元素出栈
    }else if(stackNumber == 2){
        if(S->top2 == MAXSIZE)
            return ERROR;       //说明栈2是空
        *e = S->data[S->top2 ++];       //将栈2的栈顶元素出栈
    }
    return OK;
}

IV 链式存储结构实现栈

栈的链式存储结构成为链栈。对于链栈，我们将链表的头结点与栈的栈顶指针统一起来，即让链表的头尾栈顶。我们首先定义链栈，要注意的是我们不仅要定义链栈本身，还需要定义链栈中的 node。如下：

typedef struct StackNode{       //定义链栈中的元素
    SElemType data;
    struct StackNode *next;
}StackNode, *LinkStackPtr;

typedef struct LinkStack{           //定义链栈本体
    LinkStackPtr top;
    int count;
}LinkStack;

进一步的，链栈的进栈、出栈操作如下：

Status Push (LinkStack *S, SElemType e){
    LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
    s->data = e;
    s->next = S->top;       //把当前栈顶元素赋值给新结点的直接后继
    S->top = s;             //将新的结点s赋值给栈顶指针
    S->count ++;
    return OK;
}

Status Pop(LinkStack *S, SElemType *e){
    LinkStackPtr p;
    if(StackEmpty(*S))
        return ERROR;
    *e = S->top->data;
    p = S->top;                 //将栈顶结点赋值给 p，用于后面释放空间
    S->top = S->top->next;      //使栈顶结点向下移动一位，指向后一结点
    free(p);
    S->count --;
    return OK;
}

V 栈的作用

栈的引入简化线性表对象的一些特性，使得我们可以更加专注于问题的核心，这也是一种非常有价值的思维方式。下面，列举两个栈的应用：

递归

在程序语言中，我们把调用自己的函数称为 递归函数。我们首先举个例子来说明。我们关注斐波那契数列，它的后一个数等于前两个数的和。

//  斐波那契数列递归函数. 
int Fbi(int i){
    if(i < 2)
        return i == 0?0:1;
    return Fbi(i-1) + Fbi(i-2);     //这里 Fbi 就是函数自己
}
int main(){
    int i;
    for(int i = 0;i < 40; i++)      //从i = 0开始打印前40位斐波那契数
        printf("%d", Fbi(i));
    return 0;
}

因为斐波那契数列的数学表达式可以写为：

$$ F(n) = \begin{cases}
0 & \quad 当n = 0\\
1 & \quad 当n = 1\\
F(n-1)+F(n-2) & \quad 当n>1\\
\end{cases} $$

根据这一表达式，可以很好的理解上面的代码中的内容。

递归函数虽然写起来简洁，但是可能会因不慎而进入无穷递归，最终使得程序崩溃。因此，递归程序一定要注意编写 递归条件，当满足时，递归即不再进行。

通常的，递归代码会显得比较简洁，但对于程序来说，大量递归调用会建立很多函数的副本，会消耗大量的时间和内存，而迭代结构则不会产生前述问题。

回顾上面的递归代码，我们可以发现，对于递归逻辑，它首先按照一个顺序找到所有的函数，我们定义之为前进顺序，然后，计算的顺序则是前进顺序的逆顺序。这正好是栈这种数据结构的数据存储和读取方式。因此，编译器会使用栈的结构来实现递归。也就是前进阶段，每一层递归函数的局部变量、参数返回值等都被压入栈中，从而回退阶段直接 pop 栈中数据，以得到最终的答案。

四则运算表达式求值

波兰数学家发明了适用于计算机的后缀表达法（postfix expression），也叫逆波兰（Reverse Polish Notation，RPN）表示。计算机首先将我们输入的“中缀表达式(infix expression)”（即我们习惯的数学表达式）转换为后缀表达式，(方法是通过栈来”进出”运算符号) 然后从左向右进行计算，遇到数字就进栈，遇到算符就将栈顶的两个数组出栈进行运算。最终可以达到让计算机识别括号、并保证乘法除法优先运算的效果。(参考link)