个人主页：欢迎大家光临——>沙漠下的胡杨

  各位大帅哥，大漂亮

 如果觉得文章对自己有帮助

 可以一键三连支持博主

 你的每一分关心都是我坚持的动力

 

 ☄： 本期重点：数组栈的模拟实现

  希望大家每天都心情愉悦的学习工作。 

栈数据结构的特性：

数组模拟栈的实现：

头文件的实现：

源文件的实现：

栈的初始化：

栈的销毁：

入栈：

出栈：

读出栈顶元素：

判断栈是否为空：

栈中元素的个数：

栈的整体代码：

头文件：

源文件：

最后我们来看下一个栈的习题——>括号匹配问题

栈数据结构的特性：

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

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

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

 

我们看个图片来进一步理解下栈：

刚开始时栈顶和栈底一样，然后ABCD分别入栈，然后在把D出栈，这个过程是怎么实现的呢？我们接着往下看吧。 

数组模拟栈的实现：

头文件的实现：

首先我们要知道一个栈中都要有什么，必须有一个动态的数组吧，然后要有一个栈顶，还要有一个容量配合栈顶来完成一些逻辑。所以我们如下创建：

typedef int STDataType;typedef struct Stack{STDataType* a;int top;int capacity;}ST;

我们还要有一些常见的栈的接口，比如初始化，销毁，插入，删除，取栈顶，返回栈的元素个数，判断栈是否为空。如下：

void StackInit(ST* ps);//初始化void StackDestroy(ST* ps);//销毁void StackPush(ST* ps, STDataType x);//插入（入栈），栈的插入是尾插。void StackPop(ST* ps);//删除（出栈），从尾部删除。STDataType StackTop(ST* ps);//读出栈顶bool StackEmpty(ST* ps);//判断栈是否为空int StackSize(ST* ps);//栈中的元素个数

这些就是我们要实现的函数接口啦，下面我们进行实现。

源文件的实现：

栈的初始化：

void StackInit(ST* ps)//初始化{assert(ps);ps->a = NULL;ps->capacity = ps->top = 0;}

我们在初始化时一般是把动态的数组置为NULL，把栈顶和容量置为0。

 

栈的销毁：

void StackDestroy(ST* ps)//销毁{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;}

栈销毁时，我们先free掉开辟的动态数组，在把内容置为NULL，接着把栈顶和容量置为0。

 

入栈：

void StackPush(ST* ps, STDataType x)//插入（入栈），栈的插入是尾插。{assert(ps);if (ps->capacity == ps->top){int NewCapaticy = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType)*NewCapaticy);if (tmp == NULL){perror("realoc fail\n");exit(-1);}ps->a = tmp;ps->capacity = NewCapaticy;}ps->a[ps->top] = x;ps->top++;}

这里在扩容时，我们可以直接把栈顶和容量做对比，如果相等那么就扩容，扩容一般是2倍或者1.5倍，如果不相等，直接尾插，最后栈顶自增一。

 

出栈：

void StackPop(ST* ps)//删除（出栈），从尾部删除。{assert(ps);assert(!StackEmpty(ps));ps->top--;}

入栈时，先判断栈是否为空，如果不为空，就让栈顶自减一，如果为空，就直接报错，为空时不能再出栈啦。

 

读出栈顶元素：

STDataType StackTop(ST* ps)//读出栈顶{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top-1];}

先判断栈是否为空，不为空时再返回栈顶的元素，此时栈顶的元素个数从0开始的，下标访问要 -1进行访问。

 

判断栈是否为空：

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

还是直接用表达式判断，用表达式的结果，作为布尔值进行返回。

 

栈中元素的个数：

int StackSize(ST* ps)//栈中的元素个数{assert(ps);return ps->top;}

这里返回栈顶就可以啦。

栈的整体代码：

头文件：

#pragma once #define  _CRT_SECURE_NO_WARNINGS#include #include #include #include typedef int STDataType;typedef struct Stack{STDataType* a;int top;int capacity;}ST;void StackInit(ST* ps);//初始化void StackDestroy(ST* ps);//销毁void StackPush(ST* ps, STDataType x);//插入（入栈），栈的插入是尾插。void StackPop(ST* ps);//删除（出栈），从尾部删除。STDataType StackTop(ST* ps);//读出栈顶bool StackEmpty(ST* ps);//判断栈是否为空int StackSize(ST* ps);//栈中的元素个数

源文件：

#include "Stack.h"void StackInit(ST* ps)//初始化{assert(ps);ps->a = NULL;ps->capacity = ps->top = 0;}void StackDestroy(ST* ps)//销毁{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;}void StackPush(ST* ps, STDataType x)//插入（入栈），栈的插入是尾插。{assert(ps);if (ps->capacity == ps->top){int NewCapaticy = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType)*NewCapaticy);if (tmp == NULL){perror("realoc fail\n");exit(-1);}ps->a = tmp;ps->capacity = NewCapaticy;}ps->a[ps->top] = x;ps->top++;}void StackPop(ST* ps)//删除（出栈），从尾部删除。{assert(ps);assert(!StackEmpty(ps));ps->top--;}STDataType StackTop(ST* ps)//读出栈顶{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top-1];}bool StackEmpty(ST* ps)//判断栈是否为空{assert(ps);return ps->top == 0;}int StackSize(ST* ps)//栈中的元素个数{assert(ps);return ps->top;}

最后我们来看下一个栈的习题——>括号匹配问题

题目如下：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

 

这个我们就可以使用栈区后进先出的性质来进行解决：

1. 我们先创建一个栈，然后遍历字符串。

2. 如果是元素为  '(' 或者 '[' 或者 '{' 这三个其中之一，我们就把该元素入栈。

3. 如果是 ')' 或者是 '}' 或者是 ']'  那我们判断栈顶是否是这三个其中一个对应的左括号，如果是那我们就把左括号出栈，继续便利，如果不是对应的左括号，那么我们就返回false。

4.如果最后栈不为空我们返回false，为空我们返回true。

5.如果返回，我们应该及时把栈销毁，防止内存泄漏，只需要返回，我们就销毁栈。

 

代码如下：

typedef int STDataType;typedef struct Stack{STDataType* a;int top;int capacity;}ST;void StackInit(ST* ps);//初始化void StackDestroy(ST* ps);//销毁void StackPush(ST* ps, STDataType x);//插入（入栈），栈的插入是尾插。void StackPop(ST* ps);//删除（出栈），从尾部删除。STDataType StackTop(ST* ps);//读出栈顶bool StackEmpty(ST* ps);//判断栈是否为空int StackSize(ST* ps);//栈中的元素个数void StackInit(ST* ps)//初始化{ps->a = NULL;ps->capacity = ps->top = 0;}void StackDestroy(ST* ps)//销毁{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;}void StackPush(ST* ps, STDataType x)//插入（入栈），栈的插入是尾插。{assert(ps);if (ps->capacity == ps->top){int NewCapaticy = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType)*NewCapaticy);if (tmp == NULL){perror("realoc fail\n");exit(-1);}ps->a = tmp;ps->capacity = NewCapaticy;}ps->a[ps->top] = x;ps->top++;}void StackPop(ST* ps)//删除（出栈），从尾部删除。{assert(ps);assert(!StackEmpty(ps));ps->top--;}STDataType StackTop(ST* ps)//读出栈顶{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top-1];}bool StackEmpty(ST* ps)//判断栈是否为空{assert(ps);return ps->top == 0;}int StackSize(ST* ps)//栈中的元素个数{assert(ps);return ps->top;}bool isValid(char * s){    ST st;    StackInit(&st);//初始化栈    while(*s)//遍历字符串    { if(*s == '{' || *s == '[' || *s == '(')//左括号入栈 {     StackPush(&st,*s);     s++; } else {     if(StackEmpty(&st))//如果栈为空，直接返回     {  StackDestroy(&st);  return false;     }     STDataType top = StackTop(&st);//取出栈顶元素做比较     if((top == '(' && *s == ')')     || (top == '{' && *s == '}')     || (top == '[' && *s == ']'))     { StackPop(&st); s++;     }     else     {  StackDestroy(&st);  return false;     } }    }    bool ret = StackEmpty(&st);//判断栈是否为空    StackDestroy(&st);    return ret;}

今天到此结束啦，感谢大家观看。

开发者涨薪指南 48位大咖的思考法则、工作方式、逻辑体系中评网简体版