什么是栈，栈及其特点和应用详解

image.png

  • 栈只能从表的一端存取数据，另一端是封闭的，如图 1 所示；
  • 在栈中，无论是存数据还是取数据，都必须遵循”先进后出”的原则，即最先进栈的元素最后出栈。拿图 1 的栈来说，从图中数据的存储状态可判断出，元素 1 是最先进的栈。因此，当需要从栈中取出元素 1 时，根据”先进后出”的原则，需提前将元素 3 和元素 2 从栈中取出，然后才能成功取出元素 1

因此，我们可以给栈下一个定义，即栈是一种只能从表的一端存取数据且遵循 “先进后出” 原则的线性存储结构。

通常，栈的开口端被称为栈顶；相应地，封口端被称为栈底。因此，栈顶元素指的就是距离栈顶最近的元素，拿图 2 来说，栈顶元素为元素 4；同理，栈底元素指的是位于栈最底部的元素，图 2 中的栈底元素为元素 1。

image.png
图 2 栈顶和栈底

进栈和出栈

基于栈结构的特点，在实际应用中，通常只会对栈执行以下两种操作：

  • 向栈中添加元素，此过程被称为”进栈”（入栈或压栈）；
  • 从栈中提取出指定元素，此过程被称为”出栈”（或弹栈）；

栈的具体实现

栈是一种 “特殊” 的线性存储结构，因此栈的具体实现有以下两种方式：

  1. 顺序栈：采用顺序存储结构可以模拟栈存储数据的特点，从而实现栈存储结构；
  2. 链栈：采用链式存储结构实现栈结构；

    两种实现方式的区别，仅限于数据元素在实际物理空间上存放的相对位置，顺序栈底层采用的是数组，链栈底层采用的是链表。有关顺序栈和链栈的具体实现会在后续章节中作详细讲解。

栈的应用

  1. 浏览器 “回退” 功能的实现
  2. 检测代码中的括号匹配问题
  3. 数值的进制转换功能

以上也仅是栈应用领域的冰山一角，这里不再过多举例

顺序栈基本操作（入栈和出栈）C语言详解

顺序栈的底层是数组，除了栈本身特点限制以外，那么接下来的操作也非常简单

image.png

这里给出使用顺序表模拟栈存储结构常用的实现思路，即在顺序表中设定一个实时指向栈顶元素的变量（一般命名为 top），top 初始值为 -1，表示栈中没有存储任何数据元素，及栈是”空栈”。一旦有数据元素进栈，则 top 就做 +1 操作；反之，如果数据元素出栈，top 就做 -1 操作

顺序栈元素”入栈”

比如，还是模拟栈存储 {1,2,3,4} 的过程。最初，栈是”空栈”，即数组是空的，top 值为初始值 -1，如图 3 所示：

image.png
图 3 空栈示意图

首先向栈中添加元素 1，我们默认数组下标为 0 一端表示栈底，因此，元素 1 被存储在数组 a[1] 处，同时 top 值 +1，如图 4 所示：

image.png
图 4 模拟栈存储元素 1

采用以上的方式，依次存储元素 2、3 和 4，最终，top 值变为 3，如图 5 所示：

image.png
图 5 模拟栈存储{1,2,3,4}

  1.     //元素elem进栈，a为数组，top值为当前栈的栈顶位置
  2.     int push(int* a,int top,int elem){
  3.         a[++top]=elem;
  4.         return top;
  5.     }

代码中的 a[++top]=elem，等价于先执行 ++top，再执行 a[top]=elem

顺序栈元素”出栈”

其实，top 变量的设置对模拟数据的 “入栈” 操作没有实际的帮助，它是为实现数据的 “出栈” 操作做准备的。

比如，将图 5 中的元素 2 出栈，则需要先将元素 4 和元素 3 依次出栈。需要注意的是，当有数据出栈时，要将 top 做 -1 操作。因此，元素 4 和元素 3 出栈的过程分别如图 6a) 和 6b) 所示：

image.png
图 6 数据元素出栈
注意，图 6 数组中元素的消失仅是为了方便初学者学习，其实，这里只需要对 top 值做 -1 操作即可，因为 top 值本身就表示栈的栈顶位置，因此 top-1 就等同于栈顶元素出栈。并且后期向栈中添加元素时，新元素会存储在类似元素 4 这样的旧元素位置上，将旧元素覆盖。

元素 4 和元素 3 全部出栈后，元素 2 才能出栈。因此，使用顺序表模拟数据出栈操作的 C 语言实现代码为： 

/数据元素出栈
int pop(int * a,int top){
    if (top==-1) {
        printf("空栈");
        return -1;
    }
    printf("弹栈元素：%d\n",a[top]);
    top--;
    return top;
}

大家看到这行代码可能觉得有问题，就是入栈1234，出栈4321的同时top—，这自然没有问题

但大家可能觉得就是 我要出栈2位置的元素，那34去哪里，没有回栈的操作

其实这样看大家需求，如果你要34回栈就写回栈的代码就行

总结

通过学习顺序表模拟栈中数据入栈和出栈的操作，初学者完成了对顺序栈的学习，这里给出顺序栈及对数据基本操作的 C 语言完整代码 

    #include <stdio.h>
    //元素elem进栈
    int push(int* a,int top,int elem){
        a[++top]=elem;
        return top;
    }
    //数据元素出栈
    int pop(int * a,int top){
        if (top==-1) {
            printf("空栈");
            return -1;
        }
        printf("弹栈元素：%d\n",a[top]);
        top--;
        return top;
    }
    int main() {
        int a[100];
        int top=-1;
        top=push(a, top, 1);
        top=push(a, top, 2);
        top=push(a, top, 3);
        top=push(a, top, 4);
        top=pop(a, top);
        top=pop(a, top);
        top=pop(a, top);
        top=pop(a, top);
        top=pop(a, top);
        return 0;
    }

链栈基本操作（入栈和出栈）C语言详解

image.png

将链表头部作为栈顶的一端，可以避免在实现数据 "入栈" 和 "出栈" 操作时做大量遍历链表的耗时操作

链表的头部作为栈顶，意味着：

  • 在实现数据”入栈”操作时，需要将数据从链表的头部插入；
  • 在实现数据”出栈”操作时，需要删除链表头部的首元节点；

因此，链栈实际上就是一个只能采用头插法插入或删除数据的链表

链栈元素入栈

例如，将元素 1、2、3、4 依次入栈，等价于将各元素采用头插法依次添加到链表中，每个数据元素的添加过程如图 2 所示：

image.png
图 2 链栈元素依次入栈过程示意图

    //链表中的节点结构
    typedef struct lineStack{
        int data;
        struct lineStack * next;
    }lineStack;
    //stack为当前的链栈，a表示入栈元素
    lineStack* push(lineStack * stack,int a){
        //创建存储新元素的节点
        lineStack * line=(lineStack*)malloc(sizeof(lineStack));
        line->data=a;
        //新节点与头节点建立逻辑关系
        line->next=stack;
        //更新头指针的指向
        stack=line;
        return stack;
    }

为了方便理解代码

image.png

链栈元素出栈

例如，图 2e) 所示的链栈中，若要将元素 3 出栈，根据”先进后出”的原则，要先将元素 4 出栈，也就是从链表中摘除，然后元素 3 才能出栈，整个操作过程如图 3 所示：

image.png
图 3 链栈元素出栈示意图

    //栈顶元素出链栈的实现函数
    lineStack * pop(lineStack * stack){
        if (stack) {
            //声明一个新指针指向栈顶节点
            lineStack * p=stack;
            //更新头指针
            stack=stack->next;
            printf("出栈元素：%d ",p->data);
            if (stack) {
                printf("新栈顶元素：%d\n",stack->data);
            }else{
                printf("栈已空\n");
            }
            free(p);
        }else{
            printf("栈内没有元素");
            return stack;
        }
        return stack;
    }

image.png

总结

    #include <stdio.h>
    #include <stdlib.h>
    typedef struct lineStack{
        int data;
        struct lineStack * next;
    }lineStack;
    lineStack* push(lineStack * stack,int a){
        lineStack * line=(lineStack*)malloc(sizeof(lineStack));
        line->data=a;
        line->next=stack;
        stack=line;
        return stack;
    }
    lineStack * pop(lineStack * stack){
        if (stack) {
            lineStack * p=stack;
            stack=stack->next;
            printf("弹栈元素：%d ",p->data);
            if (stack) {
                printf("栈顶元素：%d\n",stack->data);
            }else{
                printf("栈已空\n");
            }
            free(p);
        }else{
            printf("栈内没有元素");
            return stack;
        }
        return stack;
    }
    int main() {
        lineStack * stack=NULL;
        stack=push(stack, 1);
        stack=push(stack, 2);
        stack=push(stack, 3);
        stack=push(stack, 4);
        stack=pop(stack);
        stack=pop(stack);
        stack=pop(stack);
        stack=pop(stack);
        stack=pop(stack);
        return 0;
    }