#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<malloc.h>
//创建基础结构
typedef struct node {
  int data;
  struct node* next;
}ST;
//栈实际上就是一个只能进行头插头删的单向链表
//创建栈的头尾结点 结构体
typedef struct stack {
  struct node* top;//栈顶元素地址
  struct node* bottom;//栈底元素地址
  int size;//栈的元素个数
};
//表示每一个栈都是struct stack* 类型的，栈中的每一个怨怒是都是struct node *类型的  不仅需要为栈分配内存，还需要为压入栈中的元素分配内存
/*
node中的next指针用于让栈中上面的节点连接到下面的节点，stack中的top和bottom分别存放当前栈顶元素的地址和栈底元素的后一个位置的地址（NULL），
因为是用于指向栈中节点的指针，所以得是struct node* 类型。*/
//初始化栈
struct stack* create_stack()
{
  struct stack* s = (struct stack*)malloc(sizeof(struct stack));
  s->size = 0;
  s->bottom = s->top = NULL;
  return s;
}
//一开始栈是空的所以 size为0  top  bottom是NULL
//创建新的结点
struct node* create_node(int data) {
  struct node* newnode = (struct node*)malloc(sizeof(struct node));
  newnode->next = NULL;
  newnode->data = data;
  return newnode;
}
//入栈
//入栈首先要将准备入栈的元素封装成结点，和链表没有差别
void stackPush(struct stack* s, int x) {
  ST* newnode = create_node(x);
  newnode->next = s->top;
  s->top = newnode;
  s->size++;
}
//出栈
void stackPop(struct stack* s, int* x) {
//判断是否为空栈   如果是 空栈的话就  使得输出 Pop failed
  if (s->size == 0) {
    printf("Pop failed\n");
    exit(-1);
  }
  //创建结点临时变量  赋值得到栈顶元素
  ST* tmp = s->top;
  *x = tmp->data;//得到数值
  s->top = tmp->next;
  s->size--;
}
//查看栈顶元素
void stackTop(struct stack* s, int* x) {
  if (s->size == 0) {
    printf("空栈~~\n");
    exit(-1);
  }
  *x = s->top->next->data;
}
//清空栈
void make_stack_empty(struct stack* s) {
  s->size = 0;
  s->bottom = s->top ;
  //将栈底等于栈顶就可以  然后将size为0
}
void stackPrint(struct stack* s) {
  //打印栈表
  ST* list = s->top;
  printf("top -> ");
  while (list!=NULL) {
    printf("%d -> ", list->data);
    list = list->next;
  }
}
int main()
{
  struct stack *s = create_stack();
  stackPush(s, 1);
  stackPush(s, 2);
  stackPush(s, 3);
  stackPush(s, 4);
  stackPush(s, 5);
  stackPrint(s);
  int a = 0;
  stackPop(s,&a);
  printf("\n%d\n", a);
  stackPrint(s);
  return 0;
}

#define _CRT_SECURE_NO_WARNINGS
#include"steck.h"
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//栈是限定在一个表里面的一段进行插入删除操作的线性表
// 数据进出的顺序为先进后处
// 应用场景：网页浏览的时候的后退  编辑软件的撤销
// 
//创建栈  两个方式：数组（顺序表）和 单链表
//1.数组：选用数组用来做栈的存储结构，只需要在数组末尾进行操作即可，完美避开数组操作中挪动数据缺陷
      //   显然是可以用数组来做栈的存储结构
//2.单链表  ：因为栈是吸纳星表的一段进行操作，所以一般是用链表头进行操作
//进行头插头删  是用链表更好 效率更高
//1.用数组的方式
typedef int StackDataType;
typedef struct Stcak {
    StackDataType* data;
    int top;
    int capacity;   //数据域和元素个数
}ST;
//初始化
void StackInit(ST* ps) {
    ps->data = (StackDataType*)malloc(sizeof(StackDataType) * 4);
    if (ps->data == NULL) {
        printf("malloc failed\n");
        exit(-1);
    }
    ps->top = 0;
    ps->capacity = 4;
}
//压栈
void StackPush(ST* ps, int x) {
    assert(ps);//断言
    //满了就扩容
    if (ps->top == ps->capacity) {
        StackDataType* tmp = (StackDataType*)realloc(ps->data, sizeof(StackDataType) * ps->capacity * 2);
        if (tmp == NULL) {
            printf("realloc failed\n");
            exit(-1);
        }
        else {
            ps->data = tmp;
            ps->capacity *= 2;
        }
    }
    ps->data[ps->top] = x;
    ps->top++;
}
//出栈
void StackPop(ST* ps) {
    //出栈是将最后一个元素放出来  先进后出
    assert(ps);
    assert(ps->top > 0);//断言进行判断是否栈为空  即top!=0
    ps->top--;
    //直接减减就可以  没有了对应元素 的数据  如果再次压栈的话 会把之前的数据进行更改
}
//取得栈顶元素
StackDataType StackTop(ST* ps) {
    assert(ps);
    assert(ps->top > 0);
    return ps->data[ps->top - 1];//因为top栈顶始终要保持比元素个数大一，保证压栈的时候先压栈然后再加加
//所以取栈顶元素 的时候 top-1
}
//销毁栈
void StackDestory(ST* ps) {
    assert(ps);
    free(ps->data);
    //释放数组data的空间
    ps->data = NULL;
    ps->top = ps->capacity = 0;
}
//求栈中元素个数
int StackSize(ST* ps) {
    assert(ps);
    return ps->top;
}
//判断是否为空
bool StackEmpty(ST* ps) {
    assert(ps);
    return ps->top == 0;
}
void StackPrint(ST* ps) {
    //打印栈表
    assert(ps);
    for (int i = 0; i < ps->top; i++) {
        printf("%d ", ps->data[i]);
    }
    printf("\n");
}
int main()
{
    ST s;
    ST *ps=&s;
  /*  StackInit(&ps);
    StackPush(&ps, 1);
    StackPush(&ps, 2);
    StackPush(&ps, 3);
    StackPush(&ps, 4);
    StackPush(&ps, 5);
    StackPrint(&ps);*/
    StackInit(ps);
    StackPush(ps, 1);
    StackPush(ps, 2);
    StackPush(ps, 3);
    StackPush(ps, 4);
    StackPush(ps, 5);
    StackPop(ps);//出栈成功
    StackPrint(ps);
    printf("%d \n", StackTop(ps));//取得栈顶元素
    printf("%d \n", StackSize(ps));//获得栈表元素个数
    StackDestory(ps);
    StackPrint(ps);//销毁栈表成功
    return 0;
}