C语言 栈与数组的实现详解

typedef struct Stack
{ 
    STDataType _a[];  //STDataType 为int宏定义，当然你也可以将它定义为其他类型，宏定义是为了换栈类型的时候方便一点
    int _top; // 栈顶
    int _capacity; // 容量
}Stack;

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
bool StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);

void StackInit(Stack* ps)
{
    ps->_a = NULL; //初始化时将指针指向空,此时没有开辟空间
    //这里可以将top赋值为0，也可以赋值为-1。
    ps->_top = -1;  //赋值为0时表示top为栈顶元素的下一个位置的下标，赋值为-1时top为栈顶元素的下标
    ps->_capacity = 0; //栈的容量
}

void StackPush(Stack* ps, STDataType data)
{
    assert(ps);
    //考虑要不要增容
    //当top为0时判断条件为
    //if(ps->top==ps->_capacity)
    if (ps->_top+1 == ps->_capacity)//当栈满时进入
    {
        //判断当前栈的容量是否为0，为0的话开辟4个空间，不为0时扩容一倍
        int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
        STDataType* tmp = realloc(ps->_a, sizeof(STDataType) * newcapacity);
        if (tmp == NULL)
        {
            exit(-1);
        }
        ps->_a = tmp;
        ps->_capacity = newcapacity;
    }
    //扩容完成，或者不用扩容，开始插入
    ps->_top++;
    ps->_a[ps->_top] = data;
    //当top为0时插入操作
    //ps->_a[ps->_top] = data;
    //ps->_top++;
}

void StackPop(Stack* ps)
{
    assert(ps);
    //判断是否为空
    assert(!StackEmpty(ps));//暴力判断
    //if (top==-1)//温柔判断
    //{
    //  printf("栈已经空了！\n");
    //  exit(-1); //甩出异常
    //}
    ps->_top--;
}

STDataType StackTop(Stack* ps)
{
    assert(ps);
    //判断是否为空,为空甩出异常。
    assert(!StackEmpty(ps));
    //if (!StackEmpty(ps)) {
    //  printf("栈为空！\n");
    //  exit(-1);
    //}
    return ps->_a[ps->_top]; //返回栈顶元素
}

//取出栈里有效元素个数。
int StackSize(Stack* ps)
{
    assert(ps);
    return ps->_top+1; 
}

bool StackEmpty(Stack* ps)
{
    assert(ps);
    return ps->_top == -1;  //ps->_top为-1返回true,否则返回false.
​
}