-
【数据结构】栈
1.栈的概念及结构
栈：是一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的元素遵循后进先出LIFO（Last in First Out）的原则。
压栈：栈的插入操作叫做进栈，压栈，或入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈，出数据也在栈顶。
2.栈的实现
2.1栈的实现思路
栈的实现可以用数组或者链表实现，栈的实现使用数组更优一些，因为数组的在尾上的插入删除代价比较小。（压栈出栈）如果说一定要用链表（节省空间），可以将栈顶元素放置在带哨兵卫头结点的后面，栈底元素放在尾处，这样利于出栈。
2.2概念理解题
若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（C）
A 1,4,3,2
B 2,3,4,1
C 3,1,4,2
D 3,4,2,1A.入栈1，出栈1，入栈2,3,4,出栈4,3,2
B.入栈1,2,出栈2,入栈3，出栈3，入栈4，出栈4，最后出栈1
D.入栈1,2,3,出栈3，入栈4，出栈4，最后接连出栈2,12.3栈的结构体定义
//静态 //#define N 100 //typedef int STDataType; //struct Stack //{ // STDataType a[N]; // int top;//栈顶元素的位置 //}; //动态 typedef int STDataType; typedef struct Stack { STDataType* a; int top;//记录栈顶元素的位置 int capacity;//栈容量，用于栈的扩容 }ST;- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
2.4函数接口（功能）
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);//统计栈的元素个数2.5头文件Stack.h
#pragma once #include#include #include #include //静态 //#define N 100 //typedef int STDataType; //struct Stack //{ // STDataType a[N]; // int top;//栈顶元素的位置 //}; //动态 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);//统计栈的元素个数 - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
2.6函数实现Stack.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Stack.h" void StackInit(ST* ps)//栈的初始化 { assert(ps); ps->a = NULL; ps->top = ps->capacity = 0;//这里设定了top一开始的位置是0，即top是栈顶元素的下一个位置。 } void StackPush(ST* ps, STDataType x)//压栈 { assert(ps); //扩容 if(ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity;//容量改变 } ps->a[ps->top] = x; ps->top++;//压栈一个元素，栈顶元素的位置改变1 } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0;//top最开始的下标定在0，而不是-1(有两种情况) } void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); ps->top--;//栈顶元素位置-- } STDataType StackTop(ST* ps) { assert(ps); return ps->a[ps->top - 1]; } int StackSize(ST* ps) { assert(ps); return ps->top;//top即栈顶元素位置，等于栈中元素个数 } void StackDestroy(ST* ps)//栈的销毁 { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
2.7测试函数Test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Stack.h" void TestStack() { ST st;//建立一个栈 //初始化栈 StackInit(&st); //压栈 StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); printf("%d ", StackTop(&st));//3 StackPop(&st); printf("%d ", StackTop(&st));//2 StackPop(&st); StackPush(&st, 4); StackPush(&st, 5); //若栈不为空，则打印栈顶元素 while (!StackEmpty(&st)) { printf("%d ", StackTop(&st));//5 4 1 StackPop(&st);//出栈栈顶元素 } StackDestroy(&st);//一定要销毁栈，不然会造成内存泄漏 } int main() { TestStack(); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
2.8有效的括号（利用栈实现）
OJ链接：有效的括号解题思路：
由于本题没有提供C语言的栈，所以我们得先自己写个数据结构栈（C语言）。
1.遇到左括号，则压入栈中
2.遇到右括号，则取栈顶元素–一种类型的左括号（StackTop），看其是否能匹配
3.当循环结束，栈为空，则说明左括号和右括号的数量匹配（因为在取到右括号时，会获取到栈顶元素，即左括号，随之出栈栈顶元素）。
4.最后记得销毁栈，不然会导致内存泄漏typedef char 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->top = 0;//这里设定了top一开始的位置是0，即top是栈顶元素的下一个位置。 ps->capacity=0; } void StackPush(ST* ps, STDataType x)//压栈 { assert(ps); //扩容 if(ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity;//容量改变 } ps->a[ps->top] = x; ps->top++;//压栈一个元素，栈顶元素的位置改变1 } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0;//top最开始的下标定在0，而不是-1(有两种情况) } void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); ps->top--;//栈顶元素位置-- } STDataType StackTop(ST* ps) { assert(ps); return ps->a[ps->top - 1]; } int StackSize(ST* ps) { assert(ps); return ps->top;//top即栈顶元素位置，等于栈中元素个数 } void StackDestroy(ST* ps)//栈的销毁 { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } bool isValid(char * s) { //1.首先建立一个栈 ST st; //2.初始化栈 StackInit(&st); //匹配 while(*s) { if(*s=='{'||*s=='('||*s=='[')//是左括号则压入栈中 { StackPush(&st,*s); } else { //当左括号的数量少于右括号时，如'}' if(StackEmpty(&st)) { StackDestroy(&st); return false; } char top=StackTop(&st);//获取栈顶元素，即左括号 StackPop(&st);//及时出栈栈顶元素 if((*s==')'&&top!='(')|| (*s=='}'&&top!='{')|| (*s==']'&&top!='[')) { StackDestroy(&st); return false; } } s++; } bool flag=StackEmpty(&st); StackDestroy(&st); return flag; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
-
相关阅读:
c语言tips-宏连接
噢不，一条update.where无索引导致的MySQL死锁
学信息系统项目管理师第4版系列11_信息安全管理
springboot医院HIS信息管理系统源码：技术架构：Angular+Nginx+Java+Spring，SpringBoot
澳洲最热门职业，护士排第一，医生竟然不如程序员？
关于Docker中设置Java应用的JVM
玩转堆排序以及Topk问题——【数据结构】
【实验记录】一些小疑问
partial的使用，对定制化的想法
LLM面面观之RLHF平替算法DPO
- 原文地址：https://blog.csdn.net/weixin_63449996/article/details/126668763
