栈的实现
实现栈所需要的头文件
#pragma once #include<stdio.h> #include<stdbool.h> #include<stdlib.h> #include<assert.h>
定义数据类型以及创建栈
typedef int STDataType; typedef struct Stack { STDataType* a; int top; int capacity;//容量 }ST;
栈所需要实现的函数
//初始化 void StackInit(ST* ps); //销毁栈 void StackDestory(ST* ps); //入栈 void StackPush(ST* ps, STDataType x); //出栈 void StackPop(ST* ps); //取值 STDataType StackTop(ST* ps); //计算个数 int StackSize(ST* ps); //判断栈是否为空 bool StackEmpty(ST* ps);
函数的实现
#include"Stack.h" typedef int STDataType; void StackInit(ST* ps) { assert(ps); ps->a = (STDataType*)malloc(sizeof(STDataType) * 4); if (ps->a == NULL) { printf("malloc fail\n"); exit(-1); } else { ps->capacity = 4; ps->top = 0; } } void StackDestory(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } void StackPush(ST* ps, STDataType x) { assert(ps); //判断是否增容 if (ps->top == ps->capacity) { STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType)); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } else { ps->a = tmp; ps->capacity *= 2; } } ps->a[ps->top] = x; ps->top++; } void StackPop(ST* ps) { assert(ps); assert(ps->top > 0); ps->top--; } STDataType StackTop(ST* ps) { assert(ps); assert(ps->top > 0); return ps->a[ps->top - 1]; } int StackSize(ST* ps) { assert(ps); return ps->top; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; }
