数据布局——栈

目录
栈
概念与布局

栈底层布局选型
数组
链表
使用数组实现栈
​编辑
初始化栈
判断栈空
入栈
出栈
取栈顶元素
栈的元素个数
烧毁

---

栈

概念与布局

栈是一种特殊的线性表，它只答应在固定的一端举行插入和删除元素利用。举行数据插入和删除利用的一端称为栈顶，另一端称为栈底。栈中的数据依照先辈后出的原则。
压栈：栈的插入利用叫做压栈/入栈/进栈。
出栈：栈的删除利用叫做出栈。
出数据和入数据都在栈顶。

栈底层布局选型

数组

链表

 那么对于数组和链表我们选择哪个比力好呢？
答案是数组。由于链表固然动态性更强，但是每个利用都必要动态分配结点，内存开销比力大，且频仍分配/释放可能引发内存碎片。而数组尾插尾删的服从更高。
使用数组实现栈

我们就根据次序表的布局来模拟一遍栈的布局。

1. typedef int STDataType;
2. typedef struct stack
3. {
4.         STDataType* arr;
5.         int top;
6.         int capacity;
7. }ST;

复制代码

初始化栈

1. void STInit(ST* ps)
2. {
3.         assert(ps);
4.         ps->arr = NULL;
5.         ps->top = ps->capacity = 0;
6. }

复制代码

判断栈空

1. bool STEmpty(ST* ps)
2. {
3.         assert(ps);
4.         return ps->top == 0;
5. }

复制代码

入栈

1. void STCheck(ST* ps)
2. {
3.         if (ps->top == ps->capacity)
4.         {
5.                 int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
6.                 STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));
7.                 if (tmp == NULL)
8.                 {
9.                         perror("realloc failed!");
10.                         exit(1);
11.                 }
12.                 else
13.                 {
14.                         ps->arr = tmp;
15.                         ps->capacity = newcapacity;
16.                 }
17.         }
18. }

复制代码

1. void STPush(ST* ps, STDataType x)
2. {
3.         assert(ps);
4.         STCheck(ps);
5.         ps->arr[ps->top++] = x;
6. }

复制代码

出栈

1. void STPop(ST* ps)
2. {
3.         assert(ps && ps->arr && !STEmpty(ps));
4.         ps->top--;
5. }

复制代码

注意：删除的空间不能free掉，由于动态开发的空间不能局部释放。
取栈顶元素

1. STDataType STTop(ST* ps)
2. {
3.     assert(ps && ps->arr && !STEmpty(ps));
4.         return ps->arr[ps->top-1];
5. }

复制代码

栈的元素个数

1. int STSize(ST* ps)
2. {
3.         assert(ps);
4.         return ps->top;
5. }

复制代码

烧毁

1. void STDestroy(ST* ps)
2. {
3.         assert(ps);
4.         free(ps->arr);
5.         ps->arr = NULL;
6.         ps->top = ps->capacity = 0;
7. }

复制代码