回顾
前几期我们讲解了数据类型中的链表、顺序表：
今天我们来认识一种新的数据结构--栈
1.什么是栈
栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
2.栈的实现
栈的实现方式可以使用数组，也可以使用链表的形式，二者相较而言数组其实更优，数组在尾部插入数据的代价更小。
通常栈我们实现的都是动态的栈，根据需求来进行空间的分配，这种动态栈在实际解决问题上用到的会更多，下来我们来实现的是动态增长的栈。
2.1动态栈的初始化
栈的结构体：
对数据类型进行重命名，这样以后需要更换其他数据类型使用的时候只需要更改这一个地方就可以了。
定义一个数组动态的开辟空间，size用来存储当前栈内的有效元素个数，capacity来表示栈的总容量大小，这样的是为了当栈内有效元素个数与容量一致时，方便对其进行扩容。
typedef int StackData; typedef struct Stack { StackData* data; int size; int capacity; }Stack;
栈的初始化：
void StackInit(Stack* SK) { assert(SK); SK->data = NULL; SK->capacity = 0; SK->size = 0; }
先将栈中所有的数据都初始化为空，因为栈只需要在容量满的时候进行扩容，这里可以不需要先开辟空间，这一步可以节省。
2.2栈的通用操作
入栈：
在对栈进行数据插入前，首先进行栈区容量检查，如果满或是空，就先进行空间的增容。然后再将元素插入到栈顶，栈中有效元素个数size++。
void StackPush(Stack* SK,StackData x) { assert(SK); if (SK->capacity == SK->size) { SK->capacity = (SK->capacity == 0 ? 5 : SK->capacity * 2); StackData* tmp = (StackData*)realloc(SK->data,sizeof(StackData) *SK->capacity); if (tmp == NULL) { perror("realloc "); exit(-1); } SK->data = tmp; } SK->data[SK->size] = x; SK->size++; }
出栈：
栈的出栈相较入栈更为简单，因为栈的空间是动态开辟来的，无法对其一部分空间进行释放，故无法达到真正意义上的删除。这里也不可将元素的值置为0，因为有一种情况就是元素数据的值就是0。因此这里只需要让size--就可以达到目的，size是栈中有效的元素个数，插入元素时也是使用size为下标进行插入，所以size--后，代表栈少了一个元素，再进行入栈操作，新的元素就会覆盖旧的值。
void StackPop(Stack* SK) { assert(SK); assert(SK->size > 0); SK->size--; }
获取栈顶元素：
想要知道栈顶的元素，首先要对栈中元素进行判定，如果栈中元素不大于0，则栈中无元素。
栈有元素时，size是有效元素个数，数组的性质下标是从0开始，所以这里size-1，就代表栈的顶部元素。
StackData StackTop(Stack* SK) { assert(SK); assert(SK->size > 0); return SK->data[SK->size-1]; }
检测栈是否为空：
在什么情况下栈为空？只有一种情况就是栈内的元素个数为0，此时站内无元素就是空。
bool StackEmpty(Stack* SK) { assert(SK); return SK->size == 0; }
栈中有效元素个数：
当我们在对栈进行多次入栈和出栈操作后，我们想知道此时栈中还有多少元素时，就会用到。如何知道呢，在最开始我们定义了一个size，它存的值就是栈内的有效元素个数，所以只需要返回size就可以。
int StackSize(Stack* SK) { assert(SK); return SK->size; }
2.3栈销毁
这里不能直接对SK进行释放，因为SK中的data是动态开辟来的，所以需要先对data进行free，然后将其他成员置空。
void StackDestroy(Stack* SK) { assert(SK); free(SK->data); SK->capacity = 0; SK->size = 0; SK->data = NULL; }
源码实现分享：
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include <stdio.h> #include <assert.h> #include <stdbool.h> #include <stdlib.h> typedef int StackData; typedef struct Stack { StackData* data; int size; int capacity; }Stack; //栈初始化 void StackInit(Stack* SK); //栈销毁 void StackDestroy(Stack* SK); //入栈 void StackPush(Stack* SK,StackData x); //出栈 void StackPop(Stack* SK); //获取栈顶元素 StackData StackTop(Stack* SK); //检测栈是否为空 bool StackEmpty(Stack* SK); //栈中有效元素个数 int StackSize(Stack* SK);
#include "Stack.h" void StackInit(Stack* SK) { assert(SK); SK->data = NULL; SK->capacity = 0; SK->size = 0; } void StackDestroy(Stack* SK) { assert(SK); free(SK->data); SK->capacity = 0; SK->size = 0; SK->data = NULL; } void StackPush(Stack* SK,StackData x) { assert(SK); if (SK->capacity == SK->size) { SK->capacity = (SK->capacity == 0 ? 5 : SK->capacity * 2); StackData* tmp = (StackData*)realloc(SK->data,sizeof(StackData) *SK->capacity); if (tmp == NULL) { perror("realloc "); exit(-1); } SK->data = tmp; } SK->data[SK->size] = x; SK->size++; } void StackPop(Stack* SK) { assert(SK); assert(SK->size > 0); SK->size--; } StackData StackTop(Stack* SK) { assert(SK); assert(SK->size > 0); return SK->data[SK->size-1]; } bool StackEmpty(Stack* SK) { assert(SK); return SK->size == 0; } int StackSize(Stack* SK) { assert(SK); return SK->size; }
本期的内容就是以上这些啦，希望大家动动小手指，给博主一键三连，大家的支持是我前行的最大动力。
