数据结构------栈的介绍和实现

1.栈的一些初步认识

2.栈的实现

3.相关的函数介绍

（1）栈的初始化

（2）栈的销毁

（3）栈的数据插入

（6）判断是否为空

（7）栈的大小

4.栈的实现完整代码

（1）stack.h

（2）stack.c

（3）test.c

5.栈的应用--有效的括号

1.栈的一些初步认识

相信前面看过我的函数栈帧的创建和销毁这篇博客的小伙伴们对于栈已经有了一个初步的了解

因为在那个博客里面，我们提到了栈顶指针，栈底指针，压栈，出栈等等一些专业术语；

现在我们来系统的认识一下栈：

栈实际上也是一个存储数据的结构，和我们的线性表是一样的，但是栈肯定是有自己的独特之处的，否则也不会作为一个单独的数据结构存在，确实，栈的特殊性就在于我们的数据都是从栈顶进入，栈顶出去，这个就是栈的特殊之处；

栈的这个特性使得先进去的数据后出来，后进栈的数据先出来，这个有什么好处呢？我们现在可能还体会不到，我通过一个例子大家就可以体会到栈的用途，栈是有用的；

比如我们想要判断一串符号的顺序：看看是不是一一对应的，例如{（【】）}这个肯定就是一一对应的符号组合，但是对于{【（}】）这个就不是一一对应的符号，我们是用肉眼可以看出来的，但是如果有题目让我们设计程序进行判断呢？

拿这个{（【】）}作为案例，我们的{先进栈，（再进栈，【再进栈，这个时候我们的左边的括号都判断完了，我们需要判断右边的符号和左边的是不是一一对应的，这个时候就可以使用栈这个数据结构，因为我们的栈是后进先出，前面的3个符号进栈之后，我们就可以让他们依次出栈和我们后面的几个符号进行比较，例如这里的大括号第一个进栈，小括号第二个进栈，中括号第三个进栈，我们要向看看是否匹配，就只需要判断第四个的符号中括号和我们第一个出栈的符号是否匹配，这个时候栈这个数据结构就可以帮助我们判断这个一串符号前后是不是一一对应的。

2.栈的实现

我们还是写一个系统的文件，包括栈的实现的头文件，源文件和测试文件这三个文件；

我们在头文件里面进行相关函数的声明，源文件里面进行相关的函数的定义，测试文件里面定义一个栈进行我们写的函数的测试；

我们这里是定义了一些函数：栈的初始化，栈的销毁，栈里面插入数据，栈里面删除数据，返回栈顶的数据，判断栈是否是空的，栈的大小；

3.相关的函数介绍

（1）栈的初始化

这里就是把数组置空，栈顶的位置设为0，容量设置为0，这里是top指的是栈顶的位置，我们这里初始化为0，实际上指的是栈顶的下一个元素，实际情况下，栈这个时候是空的，我们应该初始化为-1，我们初始化为0方便后面的插入数据，我们插入数据就是在栈顶的下一个位置进行插入的，因此我们初始化为0可以方便后续的数据的插入；

（2）栈的销毁

就是释放掉数组的空间，栈顶位置和栈的容量都设置为0就可以了；

（3）栈的数据插入

我们要为这个栈开辟空间，把我们要插入的数据给插入进去，再让栈顶的位置加加就行了；

（4）栈的元素删除

这个就是不断的删除栈顶的元素，让栈顶位置元素不断的弹出，最后不断的让top--,但是这个栈的元素的个数是有限的，肯定不能一直进行top--把，我们调用这个判断是否为空的函数进行断言，因为这个函数判断的是为空的，所以我们断言的时候取非，这个时候过了再进行top--；

（5）取出栈的元素

返回值就是我们取出来的元素，还是要进行断言，因为栈里面的元素个数是有限的，我们肯定不能一直取出元素；

（6）判断是否为空

我们设置布尔值，pst->top为0时候，说明栈里面没有元素，是空的，我们就返回true,否则就返回false;

（7）栈的大小

我们还是返回pst->top表示的是栈顶的下一个位置，下表和个数是相差1的，如果是2个元素，我们的pst->top表示的是栈顶的下一个元素位置，下标是从0开始的，栈顶的下一个元素就是第三个元素，下标就是2，我们返回的就是2个元素的个数；

4.栈的实现完整代码

（1）stack.h

#pragma once
#include<stdbool.h>
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int sldatatype;
typedef struct stack
{sldatatype* a;int top;int capacity;
}stack;void stackinit(stack* pst);void stackdestory(stack* pst);void stackpush(stack* pst, sldatatype x);void stackpop(stack* pst);sldatatype stacktop(stack* pst);bool stackempty(stack* pst);int size(stack* pst);

（2）stack.c

#include"stack.h"void stackinit(stack* pst)
{assert(pst);pst->a = NULL;pst->top = 0;//指向栈顶的下一个元素pst->capacity = 0;
}void stackdestory(stack* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = 0;pst->capacity = 0;
}void stackpush(stack* pst, sldatatype x)
{if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : (pst->capacity * 2);sldatatype* temp = (sldatatype*)realloc(pst->a, newcapacity * sizeof(sldatatype));if (temp == NULL){perror("realloc fail!");return;}pst->a = temp;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}void stackpop(stack* pst)
{assert(pst);assert(!stackempty(pst));pst->top--;
}sldatatype stacktop(stack* pst)
{assert(pst);assert(!stackempty(pst));return pst->a[pst->top - 1];
}bool stackempty(stack* pst)
{assert(pst);return pst->top == 0;
}int size(stack* pst)
{assert(pst);return pst->top;
}

（3）test.c

#include"stack.h"void test1()
{stack s1;stackinit(&s1);stackpush(&s1, 1);stackpush(&s1, 2);stackpush(&s1, 3);stackpush(&s1, 4);while (!stackempty(&s1)){printf("%d ", stacktop(&s1));stackpop(&s1);}stackdestory(&s1);
}
int main()
{test1();return 0;
}

我们这里进行栈里面的数据打印的时候是设置了一个循环，我们每打印一个数据，就弹出栈顶位置的元素，这个时候就有一个新的数据成为栈顶，我们再打印新的栈顶位置数据。

5.栈的应用--有效的括号

这里的应用就是我们开始提到的括号的匹配问题，我们要判断这个括号之间是否是相互匹配的；

因为现阶段我们还是使用C语言进行实现，所以我们要自己实现栈，如果是C++，我们可以使用相应的一些库，我们可以直接进行调用，这里我们就把上面实现的函数复制过来就可以了。

代码展示：

#include<stdbool.h>
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef char sldatatype;
typedef struct stack
{sldatatype* a;int top;int capacity;
}stack;void stackinit(stack* pst);void stackdestory(stack* pst);void stackpush(stack* pst, sldatatype x);void stackpop(stack* pst);sldatatype stacktop(stack* pst);bool stackempty(stack* pst);int size(stack* pst);void stackinit(stack* pst)
{assert(pst);pst->a = NULL;pst->top = 0;//指向栈顶的下一个元素pst->capacity = 0;
}void stackdestory(stack* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = 0;pst->capacity = 0;
}void stackpush(stack* pst, sldatatype x)
{if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : (pst->capacity * 2);sldatatype* temp = (sldatatype*)realloc(pst->a, newcapacity * sizeof(sldatatype));if (temp == NULL){perror("realloc fail!");return;}pst->a = temp;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}void stackpop(stack* pst)
{assert(pst);assert(!stackempty(pst));pst->top--;
}sldatatype stacktop(stack* pst)
{assert(pst);assert(!stackempty(pst));return pst->a[pst->top - 1];
}bool stackempty(stack* pst)
{assert(pst);return pst->top == 0;
}int size(stack* pst)
{assert(pst);return pst->top;
}
bool isValid(char* s) 
{stack s1;stackinit(&s1);while(*s){if(*s=='('||*s=='['||*s=='{'){stackpush(&s1,*s);}else{if(stackempty(&s1)){stackdestory(&s1);return false;}char top=stacktop(&s1);stackpop(&s1);if(*s==']'&&top!='['||*s=='}'&&top!='{'||*s==')'&&top!='('){stackdestory(&s1);return false;}else{}}++s;}bool ret=stackempty(&s1);stackdestory(&s1);return ret;
}

（1）这个代码看上去比较复杂，实际上前面的很多都是在自己实现一个栈，只有inValid才是真正的一个接口函数，其他的都是为这个函数服务的，我们的inValid函数调用其他的函数进行相应的判断；

（2）因为我们这里是对符号进行判断，所以我们的头文件里面的int需要修改为char类型数据，这个时候我们的typedef int sldatatype的作用就显示了出来。