栈

栈：一种特殊的线性表，其只允许在固定的一段进行插入和删除元素，进行插入和删除元素的一端叫做栈顶，另一端叫做栈底，栈中的元素遵守着先进后出的原则

 stack.h

#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);

 stack.c

#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时他就是空的
}

test.c

#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);
}