目录
A.初始化 Stackinit 销毁 Stackdestroy
D. 栈的有效元素 Stacksize 判空 Stackempty
1.一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作；
2.进行数据插入和删除操作的一端称为栈顶，另一端称为栈底；
3.栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则；
压栈：向栈中插入数据；
出栈：从栈中取出数据；
图示：
其实用链表和数组都可以实现栈，但栈底就相当于链表的头，数组的第一个元素，栈顶就相当与链表的尾，数组的最后一个元素，当我们进行压栈或是出栈操作时，链表就需要找到尾，所以时间复杂度为O（N），而数组则是O（1），所以这里选择用数组实现栈比较好。
用数组实现的话，就和前面的顺序表类似了。
1.这里数组的初始化就和顺序表那里是一样的了，需要用到动态内存管理的函数，如果不懂的话，建议去补一下这一块的知识哦；
2.这个top用来记录实时数据的数量，和顺序表那里的 sz 是一样的，但注意：
<1> 如果初始化成0，那么这个 top 就指的是栈顶的下一个位置；
<2> 如果初始化成-1，那么这个 top 就指的是栈顶的位置；
3.初始化容量，这由你自己决定。
void Stackinit(Stack* ps)
{
assert(ps);
ps->arr = (STdatatype*)malloc(sizeof(STdatatype) * MR_CAP);
if (ps->arr == NULL)
{
perror("malloc fail");
exit(-1);
}
ps->top = 0; //表示的是栈顶的下一个位置
ps->capacity = MR_CAP; //默认容量
}这个非常简单，直接看代码吧。
void Stackdestroy(Stack* ps)
{
assert(ps);
free(ps->arr);
ps->arr = NULL;
ps->top = 0;
ps->capacity = 0;
}在插入前，我们需要判断容量是否已满，若已满，则需要扩容。
void Stackpush(Stack* ps, STdatatype x)
{
assert(ps);
if (ps->top == ps->capacity) //判断是否已满
{
STdatatype* tmp = (STdatatype*)realloc(ps->arr, 2 * sizeof(STdatatype) * ps->capacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
ps->arr = tmp;
ps->capacity *= 2;
}
ps->arr[ps->top] = x;
ps->top++; //数据入栈后，实时数据数量加1
}删除前要注意栈是否为空，若为空则不能进行删除操作；
删除就是使 top 减1。
void Stackpop(Stack* ps)
{
assert(ps);
assert(ps->top); //判断栈是否为空
ps->top--; //删除数据
}
出栈前需要判断栈是否为空，为空则无数据可出栈；
因为前面初始化的 top 是0，所以栈顶数据的下标是 top-1 ，如果初始化的 top 是-1，那么栈顶数据的下标则是 top 。
STdatatype Stacktop(Stack* ps)
{
assert(ps);
assert(ps->top); //判断栈是否为空
return ps->arr[ps->top - 1]; //栈顶数据的下标是 top-1
}1.若初始化的 top 是0，则 top 就是栈的有效元素个数；
2.若初始化的 top 是-1，则 top+1 为栈的有效元素个数。
int Stacksize(Stack* ps)
{
assert(ps);
return ps->top;
}1.如果 top 是0，则为空，返回 true；
2.如果 top 不是0，则不为空，返回 false 。
bool Stackempty(Stack* ps)
{
assert(ps);
return ps->top == 0; //如果 top ==0 ，则这句代码为真，返回 true；反之，返回 false
}#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#define MR_CAP 5
typedef int STdatatype;
typedef struct Stack
{
STdatatype* arr;
int top;
int capacity;
}Stack;
void Stackinit(Stack* ps);
void Stackpush(Stack* ps,STdatatype x);
void Stackpop(Stack* ps);
STdatatype Stacktop(Stack* ps);
int Stacksize(Stack* ps);
bool Stackempty(Stack* ps);
void Stackdestroy(Stack* ps);
#include "Stack.h"
void Stackinit(Stack* ps)
{
assert(ps);
ps->arr = (STdatatype*)malloc(sizeof(STdatatype) * MR_CAP);
if (ps->arr == NULL)
{
perror("malloc fail");
exit(-1);
}
ps->top = 0;
ps->capacity = MR_CAP;
}
void Stackpush(Stack* ps, STdatatype x)
{
assert(ps);
if (ps->top == ps->capacity)
{
STdatatype* tmp = (STdatatype*)realloc(ps->arr, 2 * sizeof(STdatatype) * ps->capacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
ps->arr = tmp;
ps->capacity *= 2;
}
ps->arr[ps->top] = x;
ps->top++;
}
void Stackpop(Stack* ps)
{
assert(ps);
assert(ps->top);
ps->top--;
}
STdatatype Stacktop(Stack* ps)
{
assert(ps);
assert(ps->top);
return ps->arr[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->arr);
ps->arr = NULL;
ps->top = 0;
ps->capacity = 0;
}
#include "Stack.h"
void testStack()
{
Stack st;
Stackinit(&st);
int i = 0;
for (i = 1; i <= 8; i++)
{
Stackpush(&st, i);
}
printf("%d\n ", Stacksize(&st));
/*while (!Stackempty(&st))
{
printf("%d ", Stacktop(&st));
Stackpop(&st);
}*/
printf("\n");
Stackdestroy(&st);
}
int main()
{
testStack();
return 0;
}