数据结构——栈

1、栈的概念

（1）是一种特殊的线性表，只能在一端进行插入或删除操作
（2）逻辑结构：线性结构；存储结构：既可以是顺序存储，也可以是链式存储
（3）栈顶：允许插入或删除的一端
（4）栈底：不允许插入或删除的一端，位置固定不变
（5）空栈：栈中没有元素
（6）使用特点：LIFO（后进先出）

2、操作

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>

#define STACK_MAX_COUNT  20

//大小：栈中元素的个数
//常用操作：创建、销毁（清0）、压栈（进栈）、弹栈（出栈）、判断空、遍历栈
//创建方式：顺序存储->顺序栈（数组创建、指针创建），链式存储->链栈

//如果操作要修改结构体变量，并使其有效，传地址；否则，传值

//顺序栈   数组创建方式
typedef int elementType;
typedef struct Stack_List {
    elementType data[STACK_MAX_COUNT];  //存储栈的元素
    int botom;  //栈底元素索引
    int top;  //栈顶元素索引
}Stack;

void printf_menu();
void Init_Stack(Stack* s);
int is_empty(Stack s);
void push_Stack(Stack* s, elementType val);
void pop_Stack(Stack* s);
void ptint_Stack(Stack s);
void clear_Stack(Stack* s);

int main() {
    printf_menu();
    Stack s;  //定义栈变量
    int order = 0;
    int flage = 0;
    elementType val;
    while (1) {
        printf("请输入操作指令：");
        scanf(" %d", &order);
        switch(order) {
            case 0:  //初始化栈
                Init_Stack(&s);
                break;
            case 1:  //判断栈是否为空
                flage = is_empty(s);
                flage ? printf("空栈！\n") : printf("不是空栈！\n");
                break;
            case 2:  //进栈(压栈)
                printf("请输入要压栈的元素：");
                scanf(" %d", &val);
                push_Stack(&s, val);
                break;
            case 3:  //出栈(弹栈)，弹出栈顶元素
                  //思路：把栈顶元素删除，并打印出来即可
                pop_Stack(&s);
                break;
            case 4:  //遍历栈
                ptint_Stack(s);
                break;
            case 5:  //清栈
                  //逻辑：不改变栈顶和栈底元素的位置，只是栈中元素全部置0
                clear_Stack(&s);
                break;
            case 6:  //退出
                return;
            default:
                printf("输入错误！\n");
        }
    }
    return 0;
}

void printf_menu() {
    printf("操作指令如下:\n");
    printf("0----初始化栈\n");
    printf("1----判断栈是否为空\n");
    printf("2----进栈(压栈)\n");
    printf("3----出栈(弹栈)弹出栈顶元素\n");
    printf("4----遍历栈\n");
    printf("5----清栈，将栈中元素全部置0\n");
    printf("6---退出\n");
    printf("**************************************\n");
}

//初始化栈——空栈
//特点：top==-1  botom==-1
void Init_Stack(Stack* s) {
    assert(s);
    //将栈顶和栈底指针均置为-1，此时表示为一个空栈
    s->botom = -1; 
    s->top = -1;
    printf("初始化成功！\n");
}

//判断栈是否为空
int is_empty(Stack s) {
    //if (s.top == -1) {  //空栈
    //    return 1;
    //}else {
    //    return 0;
    //}

    //优化
    return s.top == -1;
}

//进栈(压栈)
void push_Stack(Stack* s, elementType val) {
    //栈是否满
    if (s->top >= STACK_MAX_COUNT - 1) {
        printf("栈已满，无法压栈！\n");
        return;
    }
    //压栈之前，栈是否空
    if (s->top == -1) {  //或者把条件改为is_empty(*s)
        //空栈
        s->botom = 0;
    }
    s->top++;
    s->data[s->top] = val;
    printf("压栈成功！\n");
}

//出栈(弹栈)，弹出栈顶元素
void pop_Stack(Stack* s) {
    //判断是否是空栈
    if (s->top == -1) {  //或者把条件改为is_empty(*s)
        //空栈
        printf("空栈，无法弹栈！\n");
        return;
    }
    //弹栈之前，判断栈内是否只有一个元素
    elementType topele = s->data[s->top];  //先把栈顶元素保存
    if (s->top == 0) {  //栈内只有一个元素
        s->botom = -1;
    }
    s->top--;
    printf("弹出的栈顶元素为：%d\n", topele);
}

//遍历栈
void ptint_Stack(Stack s) {
    //判断是否是空栈
    if (s.top == -1) {  //或者把条件改为is_empty(*s)
        //空栈
        printf("空栈，无法弹栈！\n");
        return;
    }
    for (int i = s.botom;i <= s.top;i++) {
        printf("%d ", s.data[i]);
    }
    printf("\n");
}

//清栈
//逻辑：不改变栈顶和栈底元素的位置，只是栈中元素全部置0
void clear_Stack(Stack* s) {
    //判断是否是空栈
    if (s->top == -1) {  //或者把条件改为is_empty(*s)
        //空栈
        printf("空栈，无法弹栈！\n");
        return;
    }
    for (int i = s->botom;i <= s->top;i++) {
        s->data[i] = 0;
    }
    printf("清栈成功！\n");
}