-
数据结构----线性表之栈
前言
在介绍完链表和顺序表这两种线性结构之后，紧接着就是栈了；有了之前的基础，栈的结构与实现就变得十分简单了；而在上一篇博客中，对比了顺序表和链表，也就知道了利用顺序表来实现栈是比较简单的；
1.结构与介绍💬
简单来说，栈的操作都是在栈顶进行的；因此使用顺序表对栈来说操作是更加简单的；
栈因为在一端进行操作，所以在使用时，先进入栈的后出，后进入栈的先出；即LIFO接下来，着手实现栈的相关操作：
2.相关功能接口💬
在介绍相关操作之前，需要先对其结构进行定义：
typedef int StackDataType; typedef struct Stack { StackDataType* arr; int top; int capacity; }Stack;- 1
- 2
- 3
- 4
- 5
- 6
- 7
栈需要利用顺序表进行相关的操作，因此也就有了以上的操作！
2.1初始化💨
void InitStack(Stack* st) { assert(st); st->capacity = st->top = 0; st->arr = NULL; }- 1
- 2
- 3
- 4
- 5
- 6
2.2压栈💨
static void CheackCapacity(Stack* st) { assert(st); if (st->capacity == st->top) { int newcapacity = st->capacity == 0 ? 4 : (st->capacity * 2); StackDataType* temp = (StackDataType*)realloc(st->arr, newcapacity * sizeof(StackDataType)); if (temp == NULL) { perror("malloc fail"); exit(-1); } st->arr = temp; st->capacity = newcapacity; } } //压栈 void PushStack(Stack* st, StackDataType x) { assert(st); //判断容量 CheackCapacity(st); // st->arr[st->top] = x; st->top++; }- 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
关于扩容完全与顺序表一致，不清楚的可以点击这个链接：🤠我是链接
因为栈只能在一端进行操作，所以在top的位置进行插入，插入完成后，顶端位置需要进行++；
2.3弹栈💨
bool StackEmpty(Stack* st) { assert(st); return st->top == 0; //在压栈的过程中，因为存在后置++，一旦存入数据，top就会指向下一个空间 } void PopStack(Stack* st) { assert(st); assert(!StackEmpty(st)); st->top--; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
2.4获取栈顶元素与有效数据个数💨
//获取栈顶元素 StackDataType StackTop(Stack* st) { assert(st); assert(!StackEmpty(st)); return st->arr[st->top-1]; //top始终指向下一块空间，所以top-1就是栈顶元素 } //获取栈的有效数据个数 int StackSize(Stack* st) { assert(st); return st->top; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
2.5销毁💨
void StackDestory(Stack* st) { assert(st); free(st->arr); st->arr = NULL; st->capacity = st->top = 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
3.完整代码💬
#define _CRT_SECURE_NO_WARNINGS #include#include #include #include #include #include typedef int StackDataType; typedef struct Stack { StackDataType* arr; int top; int capacity; }Stack; //初始化 void InitStack(Stack* st); //压栈 void PushStack(Stack* st, StackDataType x); //弹栈 void PopStack(Stack* st); //打印 void PrintStack(Stack* st); //判空 bool StackEmpty(Stack* st); //获取栈顶元素 StackDataType StackTop(Stack* st); //获取栈的有效数据个数 int StackSize(Stack* st); //销毁 void StackDestory(Stack* st); #define _CRT_SECURE_NO_WARNINGS #include"stack.h" //初始化 void InitStack(Stack* st) { assert(st); st->capacity = st->top = 0; st->arr = NULL; } //判断容量 static void CheackCapacity(Stack* st) { assert(st); if (st->capacity == st->top) { int newcapacity = st->capacity == 0 ? 4 : (st->capacity * 2); StackDataType* temp = (StackDataType*)realloc(st->arr, newcapacity * sizeof(StackDataType)); if (temp == NULL) { perror("malloc fail"); exit(-1); } st->arr = temp; st->capacity = newcapacity; } } //压栈 void PushStack(Stack* st, StackDataType x) { assert(st); //判断容量 CheackCapacity(st); // st->arr[st->top] = x; st->top++; } //弹栈 void PopStack(Stack* st) { assert(st); assert(!StackEmpty(st)); st->top--; } //获取栈顶元素 StackDataType StackTop(Stack* st) { assert(st); assert(!StackEmpty(st)); return st->arr[st->top-1]; } //获取栈的有效数据个数 int StackSize(Stack* st) { assert(st); return st->top; } //判空 bool StackEmpty(Stack* st) { assert(st); return st->top == 0;//在压栈的过程中，因为存在后置++，一旦存入数据，top就会指向下一个空间 } //打印 void PrintStack(Stack* st) { assert(st); for (int i = 0; i < st->top; i++) { printf("%d -> ", st->arr[i]); } printf("\n"); } //销毁 void StackDestory(Stack* st) { assert(st); free(st->arr); st->arr = NULL; st->capacity = st->top = 0; } void test() { Stack st; InitStack(&st); PushStack(&st, 10); PushStack(&st, 20); PushStack(&st, 30); PushStack(&st, 40); PopStack(&st); PrintStack(&st); printf("%d\n", StackTop(&st)); printf("%d", StackSize(&st)); StackDestory(&st); } int main() { test(); } - 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
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
4.括号匹配
下面给出实例：
分析：给定一系列括号，我们可以将括号的左部分压入到栈中，然后通过与栈中括号进行比对，从而完成括号的匹配；
换句话说，将（、{、[这三种括号压栈，与其余三种括号比对即可！下面给出完整代码：
//括号匹配 #include#include #include #include #include #include typedef int StackDataType; typedef struct Stack { StackDataType* arr; int top; int capacity; }Stack; //初始化 void InitStack(Stack* st) { assert(st); st->capacity = st->top = 0; st->arr = NULL; } //判断容量 static void CheackCapacity(Stack* st) { assert(st); if (st->capacity == st->top) { int newcapacity = st->capacity == 0 ? 4 : (st->capacity * 2); StackDataType* temp = (StackDataType*)realloc(st->arr, newcapacity * sizeof(StackDataType)); if (temp == NULL) { perror("malloc fail"); exit(-1); } st->arr = temp; st->capacity = newcapacity; } } //压栈 void PushStack(Stack* st, StackDataType x) { assert(st); //判断容量 CheackCapacity(st); // st->arr[st->top] = x; st->top++; } //弹栈 void PopStack(Stack* st) { assert(st); assert(!StackEmpty(st)); st->top--; } //获取栈顶元素 StackDataType StackTop(Stack* st) { assert(st); assert(!StackEmpty(st)); return st->arr[st->top-1]; } //判空 bool StackEmpty(Stack* st) { assert(st); return st->top == 0;//在压栈的过程中，因为存在后置++，一旦存入数据，top就会指向下一个空间 } //销毁 void StackDestory(Stack* st) { assert(st); free(st->arr); st->arr = NULL; st->capacity = st->top = 0; } bool isValid(char* s) { Stack st; InitStack(&st); while (*s) { if (*s == '(' || *s == '{' || *s == '[') { PushStack(&st, *s); } else { if (StackEmpty(&st)) { StackDestory(&st); return false; } if ((StackTop(&st) == '(' && *s != ')') || (StackTop(&st) == '{' && *s != '}') || (StackTop(&st) == '[' && *s != ']')) { StackDestory(&st); return false; } PopStack(&st); } s++; } bool flag = StackEmpty(&st); StackDestory(&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
- 117
- 118
- 119
- 120
分析：利用之前实现的栈即可完成将括号的左部分压入其中；
- 当全部为右括号时，此时栈中无元素，所以判空即可，当栈为空时即返回false；
- 而当括号中的左括号与*s匹配完成后，此时栈中为空栈；所以返回true；
- 当匹配了一部分括号，即左括号多于右括号，此时也不能正常匹配，所以返回false;
Ending💬
关于栈也就完成相关操作了，最后的括号匹配来源于leetcode;
好了，就这样吧🤠
-
相关阅读:
Java并发——锁（）
vscode 设置vue3 通用页面模板
ant design vue 实现组件类型推断 vue3,vite,ts
vue 中的监听器watch
python数据管理和分析
word重复上次操作的快捷键的F4没效果了
ElementPlus·表单验证
LabVIEW压电驱动迟滞补偿控制
【一】曾经那些错误，你又踩坑了吗？
鄙视测试，理解测试，成为测试
- 原文地址：https://blog.csdn.net/weixin_57248528/article/details/126183537
