栈实现（C语言）

在编写栈之前，我们首先需要了解栈到底是声明？

所谓栈，我们遵循先进后出，后进先出

什么意思呢？

例如  我们入栈1，5，6，8，9

那么出栈时先出9，其次是8，6，5，1

我们还需要了解，栈是顺序结构

首先，我们先在头文件中写函数声明

typedef int ELEM_TYPE;
#define STACK_INIT_SIZE 10//栈的初始容量10
typedef struct stack {
	ELEM_TYPE* base;//栈底指针，用来接受malloc申请的空间
	int top;//栈顶指针
	int stacksize;//保存栈的当前可使用最大容量
}Stack,*PStack;


//初始化
void Init_stack(PStack ps);
//入栈
bool Push(PStack ps, ELEM_TYPE value);
//出栈并删除
bool Pop(PStack ps,ELEM_TYPE* rtval);
//获取栈顶数据
bool Top(PStack ps,ELEM_TYPE* rtval);
//获取有效值个数
int Get_length(PStack ps);
//判空
bool IsEmpty(PStack ps);
//判满
bool IsFull(PStack ps);
//扩容
void Inc(PStack ps);
//清空
void Clear(PStack ps);
//销毁
void Destory(PStack ps);
//打印
void Show(PStack ps);

接下来来实现栈的定义：

#include
#include
#include
#include"stack.h"
//初始化
void Init_stack(PStack ps) {
	assert(ps!=NULL);
	ps->base = (ELEM_TYPE*)malloc(sizeof(ELEM_TYPE)* STACK_INIT_SIZE);
	assert(ps->base != NULL);
	ps->stacksize = STACK_INIT_SIZE;
	ps->top = 0;
}
//入栈
bool Push(PStack ps, ELEM_TYPE value) {
	assert(ps!=NULL);
	if (IsFull(ps)) {
		Inc(ps);
	}
	ps->base[ps->top] = value;
	ps->top++;
	return true;
}
//出栈并删除
bool Pop(PStack ps, ELEM_TYPE* rtval) {
	assert(ps != NULL);
	if (IsEmpty(ps)) {
		return false;
	}
	*rtval = ps->base[ps->top - 1];
	ps->top--;
	return true;
}
//获取栈顶数据
bool Top(PStack ps, ELEM_TYPE* rtval) {
	assert(ps != NULL);
	if (IsEmpty(ps)) {
		return false;
	}
	*rtval = ps->base[ps->top - 1];
	return true;
}
//获取有效值个数
int Get_length(PStack ps){
	assert(ps != NULL);
	return ps->top;
}
//判空
bool IsEmpty(PStack ps) {
	assert(ps != NULL);
	return ps->top == 0;
}
//判满
bool IsFull(PStack ps) {
	assert(ps != NULL);
	return ps->top == ps->stacksize;
}
//扩容
void Inc(PStack ps) {
	assert(ps != NULL);
	ELEM_TYPE* p= (ELEM_TYPE*)realloc(ps->base,(ps->stacksize*sizeof(ELEM_TYPE)) * 2);
	if (p == NULL) {
		return;
	}
	ps->base = p;
	ps->stacksize *= 2;
}
//清空
void Clear(PStack ps) {
	assert(ps != NULL);
	ps->top = 0;
}
//销毁
void Destory(PStack ps) {
	assert(ps != NULL);
	free(ps->base);
	ps->stacksize = ps->top = 0;
}
//打印
void Show(PStack ps) {
	for (int i = 0; i < ps->top;i++) {
		printf("%5d",ps->base[i]);
	}
	printf("n");
}

最后，来对我们编写的栈进行测试

测试用例