一.栈
1.栈的概念及结构
- 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
- 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶
- 无论是入栈还是出栈，都遵循后进先出原则。
2.栈的实现方式
- 栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的不需要付出很大的代价。
- 如果使用链表方式实现的话，会出现一个问题，我们的栈实际上是通过尾插实现入栈的，也就是说在入栈时我们每一次都需要通过遍历的方式找尾，或者使用双头循环链表的方式找尾，但是由于数组的连续性和支持随机访问，对比于链表无疑是更加方便的。因此，接下来内容中的栈结构我们就通过数组的方式实现。
3.栈的分类
- 栈分为静态栈和动态栈
静态栈
// 下面是定长的静态栈的结构，实际中一般不实用 typedef int STDataType; #define N 10 typedef struct Stack { STDataType a[N]; int _top; // 栈顶 int _capacity; // 容量 }Stack;
动态栈
- 动态栈是通过动态内存开辟的方式实现的，由于支持动态内存的变化，因此在实际应用中动态栈无疑是更好的选择
typedef int STDataType;//方便以后修改栈中存储的数据类型 typedef struct Stack { STDataType* a;//数组 int top;//存放栈中有效元素的个数 int capacity;//栈的容量大小 }Stack; // 初始化栈 void StackInit(Stack* ps); // 入栈 void StackPush(Stack* ps, STDataType data); // 出栈 void StackPop(Stack* ps); // 获取栈顶元素 STDataType StackTop(Stack* ps); // 获取栈中有效元素个数 int StackSize(Stack* ps); // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 bool StackEmpty(Stack* ps); // 销毁栈 void StackDestroy(Stack* ps); //获取栈底元素 STDataType StackTail(Stack* ps);
4.动态栈的实现
栈的初始化函数 StackInit
- 无论是什么数据结构，我们都得先初始化
// 初始化栈 void StackInit(Stack* ps) { assert(ps);//断言 ps->a = NULL;//数组中还没有元素 //容量和有效元素都为0 ps->capacity = 0; ps->top = 0; }
入栈函数 StackPush
// 入栈 void StackPush(Stack* ps, STDataType data) { assert(ps); //判断是否还有空间 if (ps->capacity == ps->top) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//通过容量判断此时栈中有没有元素，如果没有元素就申请4个字节的空间，如果有容量，但容量不够时就把容量变为之前的2倍 STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity* sizeof(STDataType)); if (tmp == NULL)//判读开辟空间是否成功 { perror("realloc failed"); exit(-1); } ps->a = tmp;//成功了就把这个新的空间给我们的a数组 ps->capacity = newCapacity;//容量也要做相应的动态变化 } ps->a[ps->top] = data;//往栈中存元素 ps->top++;//有效元素++ }
- 这里可能有些人对于动态内存管理的内容不够了解，可以看看我这篇博客：【C语言进阶】那些你必须掌握的C/C++要点——动态内存管理(1)
- 这里还有一点要提，这里为什么用realloc开辟空间而不是使用malloc呢？
- 这里就涉及一些realloc的进阶玩法
- 我们知道realloc是用来修改动态开辟的内存大小，但是当我们给它传入的是一个空指针，它的功能与malloc就是相同的。
出栈的函数 StackPop
// 出栈 void StackPop(Stack* ps) { assert(ps); --ps->top; }
- 出栈就非常简单啦，我们直接让top减1就行，由于我们的数组是通过下标的方式访问数组成员的，top只有减少就无法在找到相应的元素啦
获取栈顶元素的函数 StackTop
// 获取栈顶元素 STDataType StackTop(Stack* ps) { assert(ps); assert(ps->top > 0); //有效元素为top，数组的下标得-1 return ps->a[ps->top-1]; }
- 我们栈中的元素是尾插的，因此最后一个元素就是我们的栈顶元素
获取栈底元素 StackTail
- 需要栈底的情况其实并不常见，我们会在某些特别情况下才会用到（比如我们之后会带大家写的oj题）
STDataType StackTail(Stack* ps) { assert(ps); return ps->a[0]; }
- 我们的元素是尾插进数组的，因此我们的首元素就是我们的栈底元素。
获取栈中有效元素的个数的函数 StackSize
// 获取栈中有效元素个数 int StackSize(Stack* ps) { assert(ps); return ps->top; }
- 我们在之前无论是入栈还是出栈都变化了我们的有效元素top，因此返回的top就是我们的有效元素个数。
判断栈是否为空的函数 StackEmpty
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 bool StackEmpty(Stack* ps) { assert(ps); return ps->top == 0; }
- top存着我们的有效元素，因此可以通过判断top是否为0来判断栈是否为空
销毁栈的函数
// 销毁栈 void StackDestroy(Stack* ps) { assert(ps); free(ps->a);//free掉动态开辟的数组 ps->a = NULL;//置空 ps->top = ps->capacity = 0;//把有效元素和容量全部清空 }
- 我们的内存是通过动态开辟出来的，因此当我们使用完后就必须把我们的申请的内存给free掉防止内存泄漏。
5.测试栈
- 我们来试试的效果
void TestStack1() { Stack ST; StackInit(&ST); StackPush(&ST, 10); StackPush(&ST, 20); StackPush(&ST, 30); while (!StackEmpty(&ST)) { printf("%d ", StackTop(&ST)); StackPop(&ST); } StackDestroy(&ST); } int main() { TestStack1(); return 0; }
总结
- 今天的内容到这里就结束了，如果你能理解之前讲过的顺序表，链表等，栈的内容其实非常的简单，想学好的话，一定要自己动手试试哦！！
- 好了，如果你有任何疑问欢迎在评论区或者私信我提出，大家下次再见啦！
