数组栈的实现

个人主页：平行线也会相交
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创
收录于专栏【数据结构初阶（C实现）】

所有接口函数

void StackInit(ST* ps);//栈的初始化
void StackDestroy(ST* ps);//销毁栈
void StackPush(ST* ps,STDataType x);//取栈顶的数据
void StackPop(ST* ps);
STDataType StackTop(ST* ps);//取栈顶的数据
int StackSize(ST* ps);
bool StackEmpty(ST* ps);//判断栈是否为空

栈的初始化

//初始化
void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;

这里需要注意的是ps->top初始化成0或者-1是有一些区别的。
当top初始化成0的时候（先放数据然后在ps->top++），意味着top指向的是栈顶数据的下一个；
当top初始化成-1的时候(先ps->top++,然后再放数据)，意味着top指向栈顶数据。
总之，我们到底是先ps->top++,还是先放数据，都是可以的。

在栈顶放数据

void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps->capacity == ps->top){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newCapacity);if (tmp == NULL){printf("realloc fail\n");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;
}

释放数据

//销毁
void StackDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;
}

删除数据

这里还没有报错，所以当ps->top一直减减直到ps->top减到-1的时候，此时就会进行报错，因为此时已经没有东西可以删除了。
所以，这里我们最好加上**assert(ps->top>0);或者把这句话换为assert(!StackEmpty(ps));**当栈为空的时候，就会提示我们不要在进行数据的删除了。

当栈里面的数据为空时，此时如果我们还想删除数据，就会直接报错。

//删除数据
void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));ps->top--;
}

取栈顶的数据

//取栈顶的数据
STDataType StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top - 1];
}

判断栈取区是否为空

bool StackEmpty(ST* ps)
{assert(ps);//if (ps->top == 0)//{//	return true;//}//else//{//	return false;//}return ps->top == 0;
}

当栈为空的时候，即ps->top=0的时候，返回真，就代表栈为空的。

栈区数据的个数

int StackSize(ST* ps)
{assert(ps);return ps->top;
}

由于我们刚刚初始化的时候，ps->top初始化的为0，top指向的是栈顶的下一个。

运行

总代码

test.c

//数组栈的实现
#define _CRT_SECURE_NO_WARNINGS 1#include"Stack.h"void TestStack1()
{ST st;StackInit(&st);StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);StackPop(&st);StackPop(&st);StackPop(&st);StackPop(&st);StackPop(&st);//printf("%d\n", StackTop(&st));//StackDestroy(&st);
}void TestStack2()
{ST st;StackInit(&st);StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);printf("%d ", StackTop(&st));StackPop(&st);printf("%d ", StackTop(&st));StackPop(&st);StackPush(&st, 5);StackPush(&st, 6);while (!StackEmpty(&st)){printf("%d ", StackTop(&st));StackPop(&st);}StackDestroy(&st);
}int main()
{//TestStack1();TestStack2();return 0;
}

Stack.c

#pragma once
#include"Stack.h"//初始化
void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;}//销毁
void StackDestroy(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->capacity == ps->top){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newCapacity);if (tmp == NULL){printf("realloc fail\n");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;
}//删除数据
void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));ps->top--;
}//取栈顶的数据
STDataType StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top - 1];
}int StackSize(ST* ps)
{assert(ps);return ps->top;
}bool StackEmpty(ST* ps)
{assert(ps);//if (ps->top == 0)//{//	return true;//}//else//{//	return false;//}return ps->top == 0;
}

Stack.h

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps,STDataType x);
void StackPop(ST* ps);
STDataType StackTop(ST* ps);//取栈顶的数据
int StackSize(ST* ps);
bool StackEmpty(ST* ps);