目录

一、数据结构中的栈

二、接口函数

三、栈的初始化

四、入栈

五、判断栈是否为空

六、出栈

七、栈顶元素及元素总数

八、顺序栈的销毁

一、数据结构中的栈

        首先，栈（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;
 
}