头文件:
#pragma once
#include<stdio.h>
#include<windows.h>
#include<assert.h>
#include<malloc.h>
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
STDataType* _a;
int _top; // 栈顶
int _capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
一些基本操作:
栈的初始化与销毁:
//栈的初始化
void StackInit(Stack* ps){
assert(ps);
ps->_a = (STDataType*)malloc(sizeof(STDataType)* 3);
if (NULL == ps->_a){
assert(0);
return;
}
ps->_capacity = 3;
ps->_top = 0;
}
//栈的销毁
void StackDestroy(Stack* ps){
assert(ps);
free(ps->_a);
ps->_a = NULL;
ps->_capacity = 0;
ps->_top = 0;
}
入栈(需要判断栈是否满了,满了则需要对栈扩容)
//栈满了申请新的空间
void BuySize(Stack*ps){
//1.申请新空间
int newsize = (ps->_capacity) * 2;
STDataType*new_a = (STDataType*)malloc(sizeof(STDataType)*newsize);
if (NULL==new_a){
assert(0);
return ;
}
//2.数据的拷贝
new_a = (STDataType*)memcpy(new_a, ps->_a, ps->_capacity);
//3.释放旧空间
free(ps->_a);
ps->_a = new_a;
//4.新空间的使用
ps->_capacity = newsize;
}
void StackInit(Stack* ps){
assert(ps);
ps->_a = (STDataType*)malloc(sizeof(STDataType)* 3);
if (NULL == ps->_a){
assert(0);
return;
}
ps->_capacity = 3;
ps->_top = 0;
}
static int StactFull(Stack*ps){
return ps->_capacity == ps->_top;
}
//入栈
void StackPush(Stack* ps, STDataType data){
if (StactFull(ps))
{
//如果栈满了则需要扩容
BuySize(ps);
}
ps->_a[ps->_top] = data;
ps->_top++;
}
出栈(需要判断栈是否为空):
//判断栈是否为空
int StackEmpty(Stack* ps){
assert(ps);
return 0==ps->_top;
}
//出栈
void StackPop(Stack* ps){
if (StackEmpty(ps))
{
return;
}
ps->_top--;
}
获取栈顶元素:
// 获取栈顶元素
STDataType StackTop(Stack* ps){
assert(!StackEmpty(ps));
return ps->_a[ps->_top-1];
}
获取栈中有效元素的个数:
// 获取栈中有效元素个数
int StackSize(Stack* ps){
return ps->_top;
}