数据结构 — 栈
【摘要】 目录
文章目录
目录栈栈的特性与结构栈的操作集应用示例：括号匹配问题
栈
首先需要说明本文讨论的栈（Stack）是一种数据结构，而非用户态虚拟存储器中的空间结构。作为数据结构的栈是一种特殊的线性表，其数据成员也与线性表一致。区别在于栈是后进先出的，而线性表允许在任意位置插入和删除数据元素。所以，栈也被称作后进先出的线性表，或简称后进先出表。
栈的一种...
目录
栈
首先需要说明本文讨论的栈（Stack）是一种数据结构，而非用户态虚拟存储器中的空间结构。作为数据结构的栈是一种特殊的线性表，其数据成员也与线性表一致。区别在于栈是后进先出的，而线性表允许在任意位置插入和删除数据元素。所以，栈也被称作后进先出的线性表，或简称后进先出表。
栈的一种应用场景就是改变数据元素序列的顺序，其思路就是：顺序的将数据元素压栈，但却根据需要让数据元素按照预期的时机出栈，从而改变它们的序列。
在软件设计中，利用栈来进行数据元素序列转换的例子很多。例如：在编译软件系统中，就需要频繁地把中缀表达式形式的算术表达式，转换成后缀表达式形式的算术表达式。又例如：任何支持递归算法的程序设计语言，都是借助栈来实现递归算法需要的后调用的过程先执行的要求的。
栈的特性与结构
栈的核心特性之一显然就是 后进先出。而栈的结构具有栈底（含元素）、栈顶（不含元素）的概念，入栈和出栈都只能在栈顶完成。
栈的操作集
- 初始化栈（StackInitiate）：设定栈长，并将栈顶置零。
- 非空否判断（StackNotEmpty）：若堆栈非空，则返回 1，否则返回 0。
- 入栈（StackPush）：在栈顶插入数据元素。
- 出栈（StackPop）：把栈顶数据元素弹出（删除并返回）。
- 取栈顶数据元素（StackTop）：取当前栈顶数据元素（返回，但不删除）。
应用示例：括号匹配问题
假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个函数，用来判别表达式中括号是否正确配对，并设计一个测试主函数。
算法思路: 检验括号是否配对可以设置一个栈，每读入一个括号，如果是左括号，则直接进栈，如果读入的是右括号，并且与当前栈顶的左括号是同类型的，则说明括号是配对的，将栈顶的左括号出栈，否则不配对。如果输入序列已经读完，而栈中仍然有等待配对的左括号，则该括号不配对。
- stack.h
#ifndef __STACK // 避免头文件被多次导入。
#define __STACK
#include <stdint.h>
#define STACK_MAX_SIZE 50 /* Maximum stack length. */
enum RESULT { SUCCESS, FAIL
};
typedef char symbol; // 定义栈数据元素的类型，示例定义的是字符类型。
typedef struct sq_stack_s { symbol elems[STACK_MAX_SIZE]; // 栈数据元素数组。 uint8_t top; // 栈顶索引。
} sq_stack_t;
void stack_initiate(sq_stack_t* s);
int stack_not_empty(sq_stack_t* s);
int stack_push(sq_stack_t* s, symbol sym);
int stack_pop(sq_stack_t* s, symbol* sym);
int stack_top(sq_stack_t* s, symbol* sym);
#endif
- 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
- stack.c
#include <stdio.h>
#include "stack.h"
void stack_initiate(sq_stack_t* s) // 传递结构体时，通常采用指针的方式，这样不需要进行对象拷贝。
{ s->top = 0;
}
int stack_not_empty(sq_stack_t* s)
{ return s->top <= 0? SUCCESS: FAIL;
}
int stack_push(sq_stack_t* s, symbol sym)
{ if (s->top >= STACK_MAX_SIZE) { printf("The stack is full.\n"); return FAIL; } else { s->elems[s->top] = sym; s->top++; // 注意 ++ 要放在后面，错误的写法 ++s->top 会先执行 ++s。 return SUCCESS; }
}
/* 通过使用指针变量的方式来返回有效数值，而非通过 return 语句，return 语句则用于返回函数的执行结果。*/
int stack_pop(sq_stack_t* s, symbol* sym)
{ if (s->top <= 0) { printf("The stack is empty.\n"); return FAIL; } else { s->top--; *sym = s->elems[s->top]; return SUCCESS; }
}
int stack_top(sq_stack_t* s, symbol* sym)
{ if (s->top <= 0) { printf("The stack is empty.\n"); return FAIL; } else { *sym = s->elems[s->top - 1]; return SUCCESS; }
}
- 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
编译 libstack 静态库：
gcc -c stack.c --std c99
ar -crv libstack.a stack.o
- 1
- 2
- main.c
#include <stdio.h>
#include "stack.h" /* 首先需要生成库文件，才能被主程序链接。 */
int match_symbol(symbol left, symbol right)
{ if (left == '(' && right == ')') { return SUCCESS; } else if (left == '[' && right == ']') { return SUCCESS; } else if (left == '{' && right == '}') { return SUCCESS; } else { return FAIL; }
}
int main(void)
{ sq_stack_t s; symbol sym_str[STACK_MAX_SIZE]; symbol* cp; // Cursor pointer，游标指针，用于遍历输入的字符数组。 symbol left_sym; // 用于临时存储栈弹出或返回的数据元素。 stack_initiate(&s); printf("INPUT >"); gets(sym_str); cp = sym_str;
/* 当 cp 游标走到字符串终结符 `/0`，while 循环就会退出。 */ while (*cp) { switch (*cp) { case '(': case '[': case '{': stack_push(&s, *cp++); // 1. *cp, 2. cp++ break; case ')': case ']': case '}': if (SUCCESS == stack_not_empty(&s)) { printf("There is no left bracket in the stack.\n"); return FAIL; } else { stack_top(&s, &left_sym); if (SUCCESS == match_symbol(left_sym, *cp)) { stack_pop(&s, &left_sym); } else { printf("Not symbol match.\n"); return FAIL; } } default: cp++; } } if (SUCCESS == stack_not_empty(&s)) { printf("Match successful.\n"); return SUCCESS; } else { printf("Match failed.\n"); return FAIL; }
}
- 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
编译 main 程序：
gcc main.c -o main -L./ -lstack
- 1
运行：
$ ./main
INPUT >{}
Match successful.
$ ./main
INPUT >[]
Match successful.
$ ./main
INPUT >{{}
Match failed.
$ ./main
INPUT >{{}]
Not symbol match.
$ ./main
INPUT >(())
Match successful.
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
文章来源: is-cloud.blog.csdn.net，作者：范桂飓，版权归原作者所有，如需转载，请联系作者。
原文链接：is-cloud.blog.csdn.net/article/details/106888443
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）