需求：無

棧的概念：

• 棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數據插入和刪除操作的一端稱為棧頂，另一端為棧底。棧中的數據元素遵守后進先出（LIFO）原則。
• 壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。
• 出棧：棧的刪除操作叫做出棧。出數據也在棧頂。

?

?棧的圖示：

• 棧的實現一般可以使用數組和鏈表實現，相對而言數組結構實現更優一些。因為尾插時代價小很多。（不用遍歷）

?

棧的判空：

棧的判空有二種實現方式，一種是top賦為0，一種是top賦為-1。區別：是top為0的時候，是先賦值再++，top為-1的時候相反。

?

?棧的應用場景：

• 函數的調用：操作系統會給每一個線程分配一個獨立的內存空間，每一個內存空間其實就是一個棧結構，它會將臨時標量，參數等等放到棧中，當棧執行完的時候，就會將最近的一個棧幀出棧。
• 括號匹配，判斷括號是否匹配，例如（[]），[（{}）]

下面是源碼：

void StackInit(Stack* ps)
{assert(ps);ps->a = NULL;ps->capacity = ps->top = 0;
}void StackPush(Stack* ps, STDateType x)
{assert(ps);if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDateType* tmp = (STDateType*)realloc(ps->a, sizeof(STDateType) * newcapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top] = x;++ps->top;
}void StackPop(Stack* ps)
{assert(ps);assert(ps->top > 0);--ps->top;
}STDateType StackTop(Stack* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}int StackSize(Stack* ps)
{assert(ps);return ps->top;
}bool StackEmpty(Stack* ps)
{assert(ps);return (ps->top == 0);
}void StackDestroy(Stack* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}