数据结构-栈

1、栈的基本概念

1、栈是特殊的线性表：只允许在一端进行插入和删除操作

2、栈的逻辑结构就是线性结构，栈的存储结构既可以是顺序存储，也可以是链式存储

3、栈顶：允许进行插入和删除的一端（最上面的为栈顶元素)

4、栈底：不允许进行插入和删除的一端（最下边的栈底元素)

5、空栈：不含任何元素的空表

6、特点：先进后出 、      LIFO(Last in First Out)

2、栈的基本操作   

创建、销毁、压栈（进栈）、弹栈（出栈）、判空、遍历

3、栈的创建

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 100

//顺序栈的创建方式：利用数组  和  利用指针
//利用数组创建栈
typedef  int eleT;
typedef struct Satck {
    eleT data[MAX_SIZE];//存放栈中的元素
    int top;//存放栈顶元素的索引
    int bottom;//存放栈底元素的索引
}ST;

void Init_Stack(ST* s);
bool is_empty(ST s);
void push_stack(ST* s, eleT val);
void print_stack(ST s);
void pop_stack(ST* s);
void clear_stack(ST* s);
int main()
{

    eleT val = 0;
    ST s;  //定义栈变量

    int order = 0;
    printf("操作指令：\n");
    printf("1、初始化\n");
    printf("2、压栈\n");
    printf("3、弹栈\n");
    printf("4、遍历\n");
    printf("5、判空\n");
    printf("6、清0\n");
    while (1)
    {
        printf("请输入指令：");
        scanf("%d", &order);
        switch (order)
        {
        case 1:
            //初始化
            //1、初始化一个空栈
            Init_Stack(&s);
            break;
        case 2:
            //压栈
            printf("请输入要压栈的元素：");
            scanf("%d", &val);
            push_stack(&s, val);
            break;
        case 3:
            //弹栈  弹出栈顶元素，
            //思路逻辑：把栈顶元素删除，并打印出来即可
            pop_stack(&s);
            break;
        case 4:
            //遍历
            print_stack(s);
            break;
        case 5:
            //判空
            is_empty(s) ? printf("空栈\n") : printf("不是空栈\n");
            break;
        case 6:
            //清0  
            //清0逻辑：不改变栈顶和栈底元素位置，只是把栈内元素设置为0
            clear_stack(&s);
            break;
        case 7:
            //退出
            return;
        default:
            printf("指令有误，重新输入\n");
        }
    }
    return 0;
}

//1、初始化一个空栈  
//空栈的特点：top==-1   bottom == -1
void Init_Stack(ST* s)
{
    s->bottom = -1;
    s->top = -1;
    printf("初始化成功\n");
}

//2、压栈
void push_stack(ST* s, eleT val)
{
    //先判断栈是否已满
    if (s->top == MAX_SIZE - 1)
    {
        //栈已满
        printf("栈已满，无法压栈\n");
        return;
    }
    //再判断是不是空栈
    if (is_empty(*s))
    {//空栈
        s->bottom++;
    }
    s->top++;
    s->data[s->top] = val;//放入新元素
    printf("压栈成功\n");
}

//3、判空  判断是不是空栈   是空栈返回1(true)   不是空栈返回0(false)
bool is_empty(ST s)
{
    if (s.top == -1)
    {  //是空栈
        return true;
    }
    //不是空栈
    return false;
}

//4、栈的遍历
void print_stack(ST s)
{
    //判断是否是空栈
    if (is_empty(s))
    {
        printf("空栈\n");
        return;
    }

    for (int i = s.bottom; i <= s.top; i++)
    {
        printf("%d  ", s.data[i]);
    }
    printf("\n");
}

//弹栈
//把栈顶元素删除，并打印出来即可
void pop_stack(ST* s)
{
    //判断你是否是空栈
    if (is_empty(*s))
    {
        printf("空栈\n");
        return;
    }
    //要考虑到弹栈之前，栈内是否只有一个元素
    eleT topele = s->data[s->top];// 先把栈顶元素保存一下
    if (s->top == 0)
    {
        //说明栈内只有一个元素
        s->bottom--;
    }
    s->top--;
    printf("弹出的栈顶元素为：%d\n", topele);
}

//清0逻辑：不改变栈顶和栈底元素位置，只是把栈内元素设置为0
void clear_stack(ST* s)
{
    if (is_empty(*s))
    {
        printf("空栈\n");
        return;
    }

    for (int i = s->bottom; i <= s->top; i++)
    {
        s->data[i] = 0;
    }
    printf("清0成功\n");
}