【手撕数据结构】把玩栈

栈的概念

前面我们已经了解了顺序表和链表这样的线性表，现在我们再来了解一种特殊的线性表。栈(stack)，栈遵守先进后出的原则，即先入栈的数据后出栈，插入数据是在栈顶插入，被称为压栈。删除数据也是在栈顶删除，叫做出栈

栈的结构

因为栈也是一种线性表，并且在物理结构上也是连续的，所以我们底层采用数组(顺序表)实现

typedef int STDataType;	//方便以后修改栈的存储数据类型
typedef struct Stack
{STDataType* arr;int top;int capacity;
}ST;

栈的初始化

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

因为底层是顺序表，所以初始化与顺序表一样。

栈的销毁

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

因为底层是顺序表，所以销毁与顺序表一样。栈的内存空间是动态开辟出来的，当我们使用完后必须释放其内存空间，避免内存泄漏。

入栈

void STPush(ST* ps, STDataType x)
{assert(ps);//检查空间是否足够if (ps->top == ps->capacity){int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, NewCapacity * sizeof(STDataType));//有可能开辟空间失败if (tmp == NULL){perror("realloc failed");exit(1);}else{ps->arr = tmp;ps->capacity = NewCapacity;}}ps->arr[ps->top++] = x;
}

这里入栈只能在栈顶插入，相当于顺序表的尾插。进行入栈操作前，我们需要检测栈的当前状态，若已满，则需要先对其进行增容，然后才能进行入栈操作。

出栈

void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));	//不要忘记判空，栈必须得有数据才能出栈ps->top--;
}

出栈也是与顺序表的尾删一样的，这里直接将top减减，不影响后面再次在那个位置插入数据，会直接覆盖.但需检测栈是否为空，若为空，则不能进行出栈操作。

获取栈顶元素

STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->arr[ps->top - 1];
}

取栈顶元素，即获取栈的最上方的元素。若栈为空，则不能获取。

检查栈是否为空

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

检测栈是否为空，即判断栈顶的位置是否是0即可。若栈顶是0，则栈为空

获取栈有效数据个数

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

因为top记录的是栈顶，使用top的值便代表栈中有效元素的个数。