栈

• 栈与栈区
• • 数组栈
  • **Stack.h中的代码：**
  • **Stack.c中的内容**
  • Test.c
  • • 链式栈
• **Stack.h**
• **Stack.c**
• **Test.c**
• 习题：

栈与栈区

在C/C++中有两种栈。
1，一种是数据结构中的栈，和之前的链表一样，只是一种特殊的线性表，但不同的是，他只允许在在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶

如图所示，只能从一端入栈和出栈，类似于弹夹一样，先装进去的子弹最后才能打出来，这一特性在某些问题很适合
2，另外一个栈是操作系统中的栈，用来函数调用时建立栈帧，然后就是某些局部变量的创建，在栈区，然后动态开辟的空间实在堆区，目前我对操作系统了解的不是很多，有兴趣的可以看看***《深入理解计算机系统》***
好啦，下面我开始介绍一下我们数据结构中的栈
栈一般可以用数组或者链表实现，我在下面两种都写一遍，但是还是比较推荐数组的写法，因为数组在尾上插入数据的代价较小。
注：我写的都是支持动态增长的栈，不是静态栈

数组栈

Stack.h中的代码：

#pragma once#include#include#include#includetypedef int STDataType;typedef struct Stack{STDataType* a;int top;//栈顶的位置int capacity;//容量}ST;void StackInit(ST* ps);//栈的初始化void StackDestory(ST* ps);//栈的销毁void StackPush(ST* ps,STDataType x);//压栈void StackPop(ST* ps);//出栈bool StackEmpty(ST* ps);//检测栈是否为空int StackSize(ST* ps);//返回栈中元素的个数STDataType StackTop(ST* ps);//返回栈顶的元素

Stack.c中的内容

#include"Stack.h"void StackInit(ST* ps)//栈的初始化{ assert(ps);//栈可以为空，但是储存栈的结构体不可能是空的ps->a = NULL;ps->capacity = 0;ps->top = 0;}void StackDestory(ST* ps)//栈的销毁{assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0;}void StackPush(ST* ps, STDataType x)//压栈{assert(ps);//压栈之前要检查一下栈是否满 因为我们的top始终是位于栈顶的下一个位置//所以当top的值等于capacity的时候栈就满了或者是一开始栈空的情况if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;  ps->a = (ST*)realloc(ps->a, sizeof(ST) * newCapacity);//在原来的基础上扩容，所以用reallocif (ps->a == NULL){printf("malloc fail\n");exit(-1);}ps->capacity = newCapacity;}//压栈ps->a[ps->top] = x;ps->top++;}void StackPop(ST* ps)//出栈{assert(ps);//出栈之前要考虑一下栈是否为空，空的话就不用出栈了 所以还需要一个断言assert(ps->top > 0);ps->top--;//因为我们打印的时候是从头开始遍历的，只会遍历到top所以只需要top--}bool StackEmpty(ST* ps)//检测栈是否为空{assert(ps);//如果top = 0的时候就是栈空 所以return ps->top == 0;}int StackSize(ST* ps)//返回栈中元素的个数{assert(ps);return ps->top;}STDataType StackTop(ST* ps)//返回栈顶的元素{assert(ps);//同时这里要确保栈中不为空assert(ps->top > 0);return ps->a[ps->top - 1];}

Test.c

#include"Stack.h"int main(){ST xk;StackInit(&xk);StackPush(&xk, 1);StackPush(&xk, 3);StackPush(&xk, 2);StackPush(&xk, 5);StackPush(&xk, 6);//打印栈while (!StackEmpty(&xk))//当栈非空的时候打印{printf("%d  ", StackTop(&xk));StackPop(&xk);//一定要记得出栈 不然会无限循环}return 0;}

链式栈

Stack.h

 #define _CRT_SECURE_NO_WARNINGS 1#pragma once #include#include#include#includetypedef int STDataType;typedef struct Stack//注意:我写的这个是不带哨兵位的单链表{STDataType data;struct Stack* next;}ST;//注意：因为链式栈的初始化一开始就是就是一个空指针 //而后续函数基本都要改动头结点，所以函数应该传入的是二级指针void StackInit(ST** ps);//栈的初始化void StackDestory(ST** ps);//栈的销毁void StackPush(ST** ps, STDataType x);//压栈void StackPop(ST** ps);//出栈bool StackEmpty(ST** ps);//检测栈是否为空int StackSize(ST** ps);//返回栈中元素的个数STDataType StackTop(ST** ps);//返回栈顶的元素

Stack.c

 #define _CRT_SECURE_NO_WARNINGS 1#include"Stack.h"void StackDestory(ST** ps)//栈的销毁{assert(ps);//这的*ps表示的是头结点 当栈空的时候头结点是有可能为NULL的    //但是指针的地址是不可能空的，所以我们断言的是指针的地址ST* cur = *ps;while (cur){ST* ret = cur->next;free(cur);cur = ret;}*ps = NULL;//和单链表的销毁是一样的}void StackPush(ST** ps, STDataType x)//压栈{//压栈其实相当于单链表的头插assert(ps);ST* cur = (ST*)malloc(sizeof(ST));//先申请一个空间来储存x的值if (cur == NULL){printf("malloc fail\n");exit(-1);}cur->data = x;cur->next = NULL;    //当栈为空的时候if (*ps == NULL){*ps = cur;}else{ST* ret = (*ps);*ps = cur;(*ps)->next = ret;}}void StackPop(ST** ps)//出栈{assert(ps);//出栈就是单链表中删除第一个元素 //所以我们应该要断言一下栈不为空的时候才可以出栈assert(*ps);//当只有一个元素时ST* cur = *ps;*ps = (*ps)->next;free(cur);}bool StackEmpty(ST** ps)//检测栈是否为空{assert(ps);return (*ps) == NULL;}int StackSize(ST** ps)//返回栈中元素的个数{assert(ps);ST* cur = *ps;int sum = 0;while (cur){sum++;cur = cur->next;}return sum;}STDataType StackTop(ST** ps)//返回栈顶的元素{assert(ps && *ps);//断言栈不为空return (*ps)->data;}

Test.c

 #define _CRT_SECURE_NO_WARNINGS 1#include"Stack.h"int main(){ST* xk = NULL;StackPush(&xk, 223);StackPush(&xk, 453);StackPush(&xk, 43534);StackPush(&xk, 3454);StackPush(&xk, 3665);StackPush(&xk, 7876);while (!StackEmpty(&xk)){printf("%-7d   ", StackTop(&xk));printf("%d\n", StackSize(&xk));StackPop(&xk);}return 0;}

习题：

括号匹配问题
我这边解题用的是C语言 可能显得有点鸡肋，用c++要方便好多，但这也可以说是学以致用了哈哈哈
我用的是数组栈去解题的，有兴趣的可以试试链式栈，由于C语言的局限性，我们必须把栈的模拟全部 ctrl+c+v上去

思路：依次遍历字符串中每一个字符，遇到左边括号就入栈，遇到右边的括号就出栈，并且出栈的时候拿栈顶的字符和字符串此时的字符比较，如果符合的话我们此时就比较下一个字符，知道字符串全部遍历完，如果有一个不匹配的话，直接return false
需要注意的代码我在下面已经标记出来了

typedef char STDataType;//赋值粘贴的时候别忘记改成chartypedef struct Stack{STDataType* a;int top;//栈顶的位置int capacity;//容量}ST;void StackInit(ST* ps)//栈的初始化{ assert(ps);//栈可以为空，但是储存栈的结构体不可能是空的ps->a = NULL;ps->capacity = 0;ps->top = 0;}void StackDestory(ST* ps)//栈的销毁{assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0;}void StackPush(ST* ps, STDataType x)//压栈{assert(ps);//压栈之前要检查一下栈是否满 因为我们的top始终是位于栈顶的下一个位置//所以当top的值等于capacity的时候栈就满了或者是一开始栈空的情况if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;  ps->a = (ST*)realloc(ps->a, sizeof(ST) * newCapacity);//在原来的基础上扩容，所以用reallocif (ps->a == NULL){printf("malloc fail\n");exit(-1);}ps->capacity = newCapacity;}//压栈ps->a[ps->top] = x;ps->top++;}void StackPop(ST* ps)//出栈{assert(ps);//出栈之前要考虑一下栈是否为空，空的话就不用出栈了 所以还需要一个断言assert(ps->top > 0);ps->top--;//因为我们打印的时候是从头开始遍历的，只会遍历到top所以只需要top--}bool StackEmpty(ST* ps)//检测栈是否为空{assert(ps);//如果top = 0的时候就是栈空 所以return ps->top == 0;}int StackSize(ST* ps)//返回栈中元素的个数{assert(ps);return ps->top;}STDataType StackTop(ST* ps)//返回栈顶的元素{assert(ps);//同时这里要确保栈中不为空assert(ps->top > 0);return ps->a[ps->top - 1];}bool isValid(char * s){  ST pos;//创建一个栈     StackInit(&pos);     while(*s)     {   if(*s=='('||*s=='{'||*s=='[')      {   StackPush(&pos,*s);   s++;   }  else  {      if(StackEmpty(&pos)) //这一步一定不能忘记了，因为当栈为空的时候，下面的返回栈顶会报错的  return false;      if((*s==')'&&StackTop(&pos)!='(') ||(*s=='}'&&StackTop(&pos)!='{') ||(*s==']'&&StackTop(&pos)!='['))  return  false;     else     {   StackPop(&pos);  s++;     }  }     }      if(!StackEmpty(&pos)) return false;//如果最后栈区不是空的话，那么也是不符合要求的  return true;}