目录

一、栈

1、概念与结构

二、栈的实现

1、定义栈的结构

2、栈的初始化

3、栈的销毁

4、入栈

5、出栈

6、bool类型判断栈是否为空

7、取栈顶元素

8、获取栈中有效元素个数

三、完整实现栈的三个文件

Stack.h

Stack.c

test.c

---

一、栈

1、概念与结构

栈：⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进行数据插入和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

重点：栈底层结构选型

        栈的实现⼀般可以使用数组或者链表实现，相对而言数组的结构实现更优⼀些。因为数组在尾上插入数据的代价比较小。

二、栈的实现

1、定义栈的结构

//定义栈的结构
typedef int STDataType;
typedef struct Stack
{STDataType* arr;int capacity;//栈的空间大小int top;
}ST;

思路分析：

        定义栈数组指针变量arr，其类型可以通过typedef来转化，定义整型类型栈的空间大小和top栈顶，最后通过typedef类型转换新命名ST栈的结构体类型。

2、栈的初始化

//栈的初始化
void STInit(ST* ps)
{assert(ps);ps->arr = NULL;ps->capacity = ps->top = 0;
}

思路分析：

        首先assert断言判断ps栈的地址是否为空（NULL），将数组地址置为空（NULL），再将容量capacity和栈顶置为0，即此时栈为空（NULL），栈顶与栈底相等。

栈的初始化时调试窗口：

3、栈的销毁

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

思路分析：

（1）首先asset断言判断ps栈的地址是否为空（NULL）；

（2）再判断ps->arr数组地址是否为空（NULL），若不为空（NULL），则释放掉ps->arr的栈数组地址，再将数组地址置为空（NULL），再将容量capacity和栈顶置为0，即此时栈为空（NULL），栈顶与栈底相等；

（3）若ps->arr数组地址不为空，则直接重复初始化的操作。

栈的销毁时调试窗口：

4、入栈

//入栈
void StackPush(ST* ps, STDataType x)
{assert(ps);//判断空间是否足够if (ps->capacity == ps->top){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空间足够ps->arr[ps->top++] = x;
}

思路分析：

（1）首先assert断言判断ps栈地址是否为空（NULL）；

（2）再判断空间是否足够，若空间足够的情况下直接插入数据，即判断ps->capacity栈容量是否等于栈顶ps->top，若空间不足够就进入if语句；

（3）ps->capacity栈容量若为0，则申请四个空间，若不为0，则增容2倍的ps->capacity栈容量，最后赋给变量newCapcity；

（4）通过realloc增容函数将新申请的空间强制类型转化为STDataType*给栈指针变量tmp；

（5）再判断tmp是否申请空间成功，最后将新申请的空间地址赋值给arr数组指针变量，再使newCapacity赋值给ps->capacity栈容量；

（6）若空间足够，则直接让栈顶++，同时进行赋值操作。

5、出栈

//出栈
void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));--ps->top;
}

思路分析：

（1）首先通过assert断言判断ps栈的地址是否为空（NULL）和！StackEmpty（ps）为真，若栈为空（NULL），则不可以出数据；

（2）然后再通过栈顶top--，完成出栈操作，使栈顶元素变为无效数据，不存在栈里面。 

出栈时的调试窗口： 

测试代码运行结果：

 

6、bool类型判断栈是否为空

//bool类型判断栈是否为空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

思路分析：

        通过bool类型去判断栈是否为空（NULL），通过assert断言判断ps栈的地址是否为空（NULL），若不为空，则返回ps->top == 0比较运算式的最终结果值，即为1或0。

7、取栈顶元素

//取栈顶元素
STDataType StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}

思路分析：

        首先通过assert断言判断ps栈的地址是否为空（NULL）和！StackEmpty（ps）为真；最终返回栈顶元素地址，即数组位置top-1。

 

8、获取栈中有效元素个数

//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}

思路分析：

        通过assert断言判断ps栈的地址，最终返回栈中的有效元素个数，即为栈顶的数组下标。

三、完整实现栈的三个文件

Stack.h

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//定义栈的结构
typedef int STDataType;
typedef struct Stack
{STDataType* arr;int capacity;//栈的空间大小int top;
}ST;//栈的初始化
void STInit(ST* ps);//栈的销毁
void STDestroy(ST* ps);//栈顶——入数据、出数据
//入栈
void StackPush(ST* ps, STDataType x);//出栈
void StackPop(ST* ps);//bool类型判断是否为空
bool StackEmpty(ST* ps);//取栈顶元素
STDataType StackTop(ST* ps);//获取栈中有效元素个数
int STSize(ST* ps);

Stack.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include<Stack.h>//栈的初始化
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->top = ps->capacity = 0;
}//入栈
void StackPush(ST* ps, STDataType x)
{assert(ps);//判断空间是否足够if (ps->capacity == ps->top){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空间足够ps->arr[ps->top++] = x;
}//出栈
void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));--ps->top;
}//bool类型判断栈是否为空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//取栈顶元素
STDataType StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}

test.c

#define  _CRT_SECURE_NO_WARNINGS 1#include<Stack.h>void STTest()
{ST st;STInit(&st);//初始化//入栈StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);StackPush(&st, 5);//出栈//StackPop(&st);//循环出栈，直到栈为空while (!StackEmpty(&st)){STDataType data = StackTop(&st);//取栈顶元素printf("%d ", data);//出栈StackPop(&st);}printf("size:%d\n", STSize(&st));//获取栈中有效元素的个数STDestroy(&st);//栈的销毁
}int main()
{STTest();return 0;
}