4. 栈 - 存储结构

4.1 栈 - 基本概念

栈：一种只能从表的一端存取数据且遵循 “先进后出” 原则的线性存储结构
栈的开口端被称为栈顶，封口端被称为栈底
进栈（入栈或压栈），向栈中添加元素
出栈（或弹栈），从栈中提取出指定元素
栈的具体实现有以下两种方式：
- 顺序栈：采用顺序存储结构实现栈存储数据的特点
- 链栈：采用链式存储结构实现栈结构

4.2 顺序栈 - 顺序表实现栈存储结构

顺序栈实现方法十分简单，具体实现的代码如下：

#include<stdio.h>
// 元素elem进栈
int push(int* a, int top, int elem) {
    a[++top] = elem;   // 先计算++top，在计算 a[top] = elem
    return top;
}
// 数据元素出栈
int pop(int* a, int top) {
    if (top == -1) {
        printf("空栈!!!\n");
        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;
}

4.3 链栈 - 链表实现栈存储结构

链栈的具体实现的方法如下：

#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("栈内没有元素!!!\n");
        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;
}