栈

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>
typedef int stdata;
typedef struct Stack
{
  stdata* a;//动态开辟
  //如果使用stdata a[max],就相当于一个静态表，不够灵活
  int top;//栈顶
  int capacity;//记录容量
}st;
//初始化
void stackinit(st *ps);
//销毁
void stackdestroy(st*ps);
//对容量进行检查
void stackcheckcapacity(st*ps);
//插入,因为所有的操作都是在栈顶进行操作,所以就不用区分是尾插还是头插
//入栈
void stackpush(st*ps,stdata x);
//插入
//出栈
void stackpop(st *ps);
//返回栈顶的元素
stdata stacktop(st*ps);
//栈里面元素的个数
int stacksize(st *ps);
bool stackempty(st*ps);

#define _CRT_SECURE_NO_WARNINGS 1
#include"stack.h"
//初始化
void stackinit(st *ps)
{
  assert(ps);//我们初始化一个指针，他肯定不能是空的
  ps->a = malloc(sizeof(stdata)*4);//一开始初始化的时候可以就给a一定的空间，方便后面使用，假如一开始是空的话，还有进行判断比较麻烦
  //malloc完都要进行判断检查
  if (ps->a == NULL)
  {
    perror("malllc");
    return;
  }
  ps->capacity = 0;
  ps->top=0;//top从头开始，指向最后一个数据
  //假如一开始把top置为0，在push的时候，就把top索引赋值，再把top进行加加
}
void stackcheckcapacity(st*ps)
{
  if (ps->top == ps->capacity)
  {
    int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
    //增容是对数组进行，所以不可以使用结构体
    stdata*tmp = (stdata*)realloc(ps->a, sizeof(st)*newcapacity * 2);
    if (tmp == NULL)
    {
      perror("realllc");
      return;
    }
    else
    {
      ps->a = tmp;
      ps->capacity = newcapacity;
    }
  } 
}
void stackpush(st*ps,stdata x)
{
  stackcheckcapacity(ps);
  //同样我们也要对容量进行检查
  assert(ps);
  ps->a[ps->top] = x;//top一开始是0，所以是从0开始加
  ps->top++;//++后top都是指向最后一个元素的后一个位置
}
//删除
void stackpop(st*ps)
{
  assert(ps);
  //如果栈空了，调用pop就直接报错，直接终止
  assert(ps->top > 0);
  //直接把top--一下就可以了
  ps->top--;
  //这时候top就指向前一元素
}
//销毁
void stackdestroy(st*ps)
{
  //也要对他进行一个断言
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->top=ps->capacity = 0;
}
//返回栈顶的元素
stdata stacktop(st*ps)
{
  assert(ps);
  assert(ps->top > 0);
  //假如说top在0的位置，也就是第一个位置，减一就是错误的
  //由于top是指向栈顶的下一个元素，那么返回栈顶,就是top的前一个
  return ps->a[ps->top - 1];
}
//记录栈里面一共有多少个元素
int stacksize(st*ps)
{
  assert(ps);//我们也要对栈进行断言，不可以为空
  return ps->top;//由于top是从0开始的，所以他指向的是最后一个元素的下一个，而top的值也就是元素的个数
}
//判断栈是否为空
bool stackempty(st*ps)
{
  assert(ps);
  return ps->top == 0;//因为我们一开始设置的top是为0.所以当top值为0的时候，他就是空的，
                      //假如top一开始设定的是-1，那么当top为-1时他就是空的
}

#define _CRT_SECURE_NO_WARNINGS 1
#include"stack.h"
int main()
{
  st stack;
  stackinit(&stack);
  stackpush(&stack, 1);
  stackpush(&stack, 2);
  stackpush(&stack, 3);
  stackpush(&stack, 4);
  stackpush(&stack, 5);
  stackpush(&stack, 6);
  //因为栈是先进后出，所以每次出的都是从栈顶出来
  while (!stackempty(&stack))
  {
    printf("%d ", stacktop(&stack));
    //打印完一个，就出一个
    stackpop(&stack);
  }
  stackdestroy(&stack);
}