当前位置：首页 > 编程日记 > 正文

数据结构之【栈】的基本操作C语言实现

编程日记 2024-06-06 18:00:00

引题：
       很多人都把【栈】描述成【弹匣】，但我总感觉有点不恰当，因为弹匣从上端【装弹】之后，子弹总是在匣的上层；而元素【进栈】之后，总在栈的下面。
       我觉得还是描述成【从下往上向书箱里一层一层地装书，从上往下一层一层地拿书】比较合适。
       不过，描述成某东西或某行为无非是帮助我们更好地去理解【栈】，具体描述成什么样都无所谓，有助于我们理解就行！

在这里插入图片描述
下面我们直入主题：

在这里插入图片描述

顺序栈的声明：
0、顺序栈的声明
顺序栈的基本操作：
1、InitStack(&S)（初始化栈）
2、DestroyStack(&S)（销毁栈）
3、ClearStack(&S)（清空栈）
4、StackEmpty(S)（判断栈是否为空）
5、StackLength(S)（返回栈的长度）
6、GetTop(S,&e)（返回栈的栈顶元素）
7、Push(&S,e)（将元素e压入栈）
8、Pop(&S,&e)（栈顶元素出栈）
9、StackTraverse(S,Status(*visit)())（遍历栈）
顺序栈的应用：
10、CharMatch（检查符号{【（）】}是否匹配）

顺序栈

------- 栈的顺序存储表示 -------回顶部

//关键字宏定义
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW 0
#define STACK_INIT_SIZE 100//顺序栈存储空间的初始分配量
#define STACKINCREMENT 10//顺序栈存储空间的分配增量
//关键字的类型说明
typedef int SElemType;
typedef int Status;
//数据元素（顺序栈）的类型说明
typedef struct{SElemType *base;  //栈底指针 SElemType *top;   //栈顶指针 int stacksize;    //当前已分配的存储空间 
}SqStack;

------- 顺序栈的基本操作 -------

1、InitStack(&S)（初始化栈） ----回顶部

//先分配空间，并指向栈底指针，然后栈顶指针和栈底指针相等 
Status InitStack(SqStack &S){    // 构造一个空栈 S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));if(!S.base)exit(0);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;
}

2、DestroyStack(&S)（销毁栈） ----回顶部

//释放分配的存储空间，释放指针，将存储空间的长度置为0 
Status DestroyStack(SqStack &S){    //销毁栈S，S不再存在 free(S.base);S.base = NULL;S.top = NULL;S.stacksize = 0;printf("销毁成功");return OK; 
}

3、ClearStack(&S)（清空栈） ----回顶部

//判断栈顶指针与栈底指针是否相等，然后逐步释放空间，并逐渐将栈顶指针-1，直至两者相等 
Status ClearStack(SqStack &S){  //把S置为空栈 if(S.top == S.base){printf("本身就是空栈");return OK;}while(S.top != S.base){S.top--;*S.top = NULL;}if(S.top == S.base){S.base = NULL;S.top = NULL;printf("\n栈已被清空\n");return OK;}return ERROR;
}

4、StackEmpty(S)（判断栈是否为空） ----回顶部

//判断栈顶指针和栈底指针是否相等，相等则为空栈，否则非空 
Status StackEmpty(SqStack S){  //若栈S为空栈，则返回TRUE，否则返回FALSE if(S.top == S.base){return TRUE;}return FALSE;
}

5、StackLength(S)（返回栈的长度） ----回顶部

//栈顶指针-栈底指针的差即为栈的长度 
int StackLength(SqStack S){   //返回S的元素个数，即栈的长度 return (S.top - S.base); 
}

6、GetTop(S,&e)（返回栈的栈顶元素） ----回顶部

//返回栈顶的元素（栈顶指针-1所指向的元素） 
Status GetTop(SqStack S, SElemType &e){//若栈不空，则用e返回S的栈顶元素，并返回OK;否则返回ERROR if(S.top == S.base){printf("空栈，无法返回栈顶元素");return ERROR;}	e = *(S.top-1);return OK;
}

7、Push(&S,e)（将元素e压入栈） ----回顶部

//先判断栈是否已满，（若栈满，则再分配空间），然后将元素插入栈顶，并另栈顶指针+1 
Status Push(SqStack &S,SElemType e){ //插入元素e为新的栈顶元素if((S.top - S.base) >= S.stacksize){S.base = (SElemType*) realloc (S.base,(S.stacksize + STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(0);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;}*S.top++ = e;return OK;
}

8、Pop(&S,&e)（栈顶元素出栈） ----回顶部

//先判断栈是否已空，（若空，则返回ERROR），若不空将栈顶指针-1 
Status Pop(SqStack &S,SElemType &e){    //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR if(S.top == S.base)return ERROR;e = * --S.top;return OK;
}

9、StackTraverse(S,Status(*visit)())（遍历栈） ----回顶部

Status visit(int *p){if(p){printf("%d ",*p);return OK;}return ERROR;
}

//从栈底指针所指向的元素开始，依次访问，直至遇到栈顶指针 
Status StackTraverse(SqStack S,Status(*visit)(int*)){//从栈底到栈顶依次对栈中每个元素调用函数visit()。一旦visit()失败，则操作失败 SElemType *p;p = S.base;while(p<S.top){visit(p);p++;}if(p == S.top){return OK;}return ERROR;
}

------- 顺序栈的应用 -------

10、检查符号是否匹配 ----回顶部

Status CharMatch(char a[]){ //检查符号匹配// 91：[     93：]// 40：(     41：)// 123：{    125：} SqStack S;InitStack(S);SElemType e;int i;for(i=0; a[i]!='\0'; i++){switch (a[i]){case '{':case '[':case '(':Push(S,a[i]);break;case ')':case ']':case '}':if(StackEmpty(S)){printf("符号不匹配"); //情况①遇到右括号，栈空，则不匹配 return ERROR;}else{GetTop(S,e);if(((e+2)==a[i]) || ((e+1)==a[i])){ //如果匹配，则将栈顶元素（即对应左括号）出栈 Pop(S,e);}else{printf("符号不匹配");  //情况②遇到的右括号与栈顶元素不匹配，则符号不匹配 return ERROR;}}break;}}if(StackEmpty(S)){printf("符号匹配");return OK;}printf("符号不匹配");  //情况③如果只有左括号，没有右括号 return ERROR; }//CharMatch

参考文献：
[1] 严蔚敏，吴伟民，《数据结构（C语言版）》.
[2] 程杰，《大话数据结构》，清华大学出版社，2011出版年.
[2] 明日科技，《C语言从入门到精通》，清华大学出版社，2019年版

https://www.dkcj.cn/info/9555.html

数据结构之【栈】的基本操作C语言实现

顺序栈

相关文章：

编码小记（未整理-持续更新）

使用locate 的正则查询查找所有main.c

My Favorites

数据库事务初探

数据结构之【队列】的基本操作C语言实现

在python3环境安装builtwith模块

kettle组件-输出

NGOSS的一点简单概念

Windows Mobile 5.0 设备的目录变化

第二周期的第一次站立会议

常见的函数式编程模型

Ubuntu下安装和配置Redis

自学笔记——1.Pyhton保留关键字

人的一生有三件事不能等

安装部署中的数据库打包和快捷方式启动浏览器

Windows下安装和配置Redis

python练习册每天一个小程序第0004题

xxxxxxx

自学笔记——2.字符串的切片、遍历、查找字符

【EXLIBRIS】随笔记 011

Ubuntu搭建Spark运行环境

hibernate 和 mybatis 的区别

VC中基于 Windows 的精确定时

VMware虚拟机安装之后，打开时找不到启动Centos的界面

service iptables status无法执行，报错

Qt5的cmake文件位置

2018-12-2

重载、重写和隐藏

[整理] - Relational Engine之UMS Internals

跟踪workflow instance 状态