目录

一、数据结构中的栈

二、接口函数

三、栈的初始化

四、入栈

五、判断栈是否为空

六、出栈

七、栈顶元素及元素总数

八、顺序栈的销毁

一、数据结构中的栈

        首先，栈（Stack）这个词在数据结构和操作系统两个学科中都有出现。

操作系统中：主要指函数栈帧、局部变量等开辟的位置，即内存上的栈区。

数据结构中：是一种后进先出的数据结构。数据的出入都从栈顶操作，如下图。

作为一种线性结构，栈可以用数组和链表模拟。

 对于数组：可以将尾部作为栈顶，尾插即为入栈，尾删即为出栈，效率为O(N)。

对于单链表：可以将头部作为栈顶，头插即为入栈，头删即为出栈，效率也为O(N)。

从单纯的数据操作的效率角度看，二者基本相同。再考虑一下数组（顺序表）和链表各自的优势和劣势。

对于数组：支持随机访问，但需要增容操作。

对于单链表：不支持随机访问，缓存命中率较低。

综合来看，二者基本相同。但增容操作的损耗较小，我们习惯上使用数组来实现顺序栈。

二、接口函数

typedef char STDataType;typedef struct STack
{int capacity;int top;STDataType* a;
}ST;//栈的初始化
void STInit(ST* ps);
//栈的销毁
void STDestroy(ST* ps);
//写test函数时，写完init记得写上destroy，养成好习惯，防止内存泄漏//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//查看栈顶元素
STDataType Topval(ST* ps);
//检查栈是否为空
bool STEmpty(ST* ps);
//栈里有几个数据
int STSize(ST* ps);

三、栈的初始化

//栈的初始化
void STInit(ST* ps)
{assert(ps);ps->top = -1;ps->capacity = 2;ps->a = (STDataType*)malloc((ps->capacity) * sizeof(STDataType));}

栈结构中包含3个成员，一个是capacity，用来衡量栈的容量，一个是top，用来取出栈顶元素，还有一个是指针a，指向存储数据的动态的数组。

这里我先给a数组开辟了2个元素大小的空间，因此ps->capacity即为2。

对于top的初始化有2种形式，-1和0。具体情况如下图。 

 top == 0时，指向的是栈顶的下一个元素，top本身也为栈中元素的个数。

 top == -1时，指向的是栈顶的元素，是栈中元素个数-1。

top初始化定义的差别，会影响后续接口STTop和STSize的具体实现。

后面的代码我将以top == -1为例。

四、入栈

//入栈
void STPush(ST* ps, STDataType x)
{assert(ps);//判断是否需要增容if ((ps->top) + 1 == ps->capacity){int newcapacity = ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);if (NULL == tmp){perror("realloc fail");return;}printf("增容成功\n");ps->a = tmp;ps->capacity = newcapacity;}ps->top++;ps->a[ps->top] = x;}

先判断是否需要增容，即当前栈中元素数top+1 是否和 capacity相等。

相等则利用realloc增容为原来的2倍，这里不要忘了将capacity进行更新，否则后续一直不会增容，但数据扔在往栈中放，此时访问就会导致越界。

top初始化为-1的情况下，先将top++到栈顶的下一个元素，再将x入栈。

五、判断栈是否为空

//检查栈是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == -1;}

这里要看初始化的topinit为0还是-1，若此时的top == topinit 即为空，返回为真。

六、出栈

}
//出栈
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));//assert(top>-1)也可以//必须检查是否为空，否则删除过多后top为负值，此时再插入数据若还是负值，然后访问会导致越界ps->top--;//由于出栈是top--来实现的，实际上并没有把空间还给操作系统，只是访问不到，但没有归还权限//因此在栈为空时，仍需要destroy}

要先检查栈不为空，然后利用top--，使我们无法访问到栈顶的那个元素。

只要栈不为空，就拿出栈顶元素，此时若想拿到下一个，则必须进行pop出栈，直到全部出栈。 

七、栈顶元素及元素总数

//查看栈顶元素
STDataType STTop(ST* ps)
{assert(ps);return ps->a[ps->top];
}

//栈里有几个数据
int STSize(ST* ps)
{assert(ps);return ps->top + 1;}

根据top初始化不同，还可能返回ps->a[ps->top -1] 和 ps->top

查看栈顶元素返回值为STDataType

八、顺序栈的销毁

//栈的销毁
void STDestroy(ST* ps)
{assert(ps);ps->top = -1;ps->capacity = 0;free(ps->a);ps->a = NULL;}