1.棧的概念及結構

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

2.棧的實現

棧的實現一般可以使用數組或者鏈表實現，相對而言數組的結構實現更優一些。因為數組在尾上插入數據的代價比較小。

?2.1定義一個動態棧

typedef int STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;

2.2棧的初始化

void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;}

2.3棧的銷毀

void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}

2.4數據進棧

數據進棧的話首先要考慮一下是否需要擴容，所以先判斷一下top是否等于capacity，如果滿了的話再判斷一下capacity是否是第一次擴容，如果是的話則擴容至4，不是的話則擴2倍，再對空間進行擴容，這里巧妙地利用了realloc這個庫函數，因為如果需要擴容的這個空間是0，則相當于是malloc，擴容完之后就將數據放進top這個位置，然后再將top++，這樣才會使得top一直是棧頂元素的下一個位置。

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

2.5數據出棧

先保證這個棧不是空的，top>0才有數據可以出。出棧直接top--就行了。

void STPop(ST* ps, STDataType x)
{assert(ps);//空assert(ps->top > 0);--ps->top;
}

2.6棧的數據個數

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

2.7判斷棧是否為空

bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

2.8獲取棧頂元素

這里需要注意一下，棧頂元素的位置是top-1.

STDataType STTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}

---

完整代碼

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 STInit(ST* ps);
void STDestroy(ST* ps);
void STPush(ST* ps,STDataType x);
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
STDataType STTop(ST* ps);

Stack.c:

void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;}
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4:ps->capacity * 2;STDataType* tmp = (STDataType*) realloc(ps->a, sizeof(STDataType) * newCapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;
}
void STPop(ST* ps, STDataType x)
{assert(ps);//空assert(ps->top > 0);--ps->top;
}
int STSize(ST* ps)
{assert(ps);return ps->top;
}
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}STDataType STTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}