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.
​
}