所有接口函数
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);
