数据结构-------栈
顺序栈：
一、数据结构定义
- 数据元素 DATATYPE
typedef struct person {char name[32];char sex;int age;int score;
} DATATYPE;
- 顺序栈结构 SeqStack
typedef struct list {DATATYPE *head; // 栈空间首地址int tlen; // 栈总容量（total length）int top; // 栈顶指针（相当于当前元素计数）
} SeqStack;
二、核心操作接口
- 创建栈
SeqStack *CreateSeqStack(int size)
{SeqStack *ss = malloc(sizeof(SeqStack));if (NULL == ss){perror("CreateSeqStack malloc error\n");return NULL;}ss->head = malloc(sizeof(DATATYPE) * size);if (NULL == ss){perror("CreateSeqStack malloc2 error\n");return NULL;}ss->tlen = size;ss->top = 0;return ss;
}- 实现要点：
- 动态分配结构体内存
- 分配连续存储空间：
head = malloc(size * sizeof(DATATYPE)) - 初始化
tlen = size,top = 0
- 销毁栈
int DestroySeqStack(SeqStack *ss)
{if (NULL == ss){fprintf(stderr, "DestroySeqStack pamter error\n");return 1;}free(ss->head);free(ss);return 0;
}
内存释放顺序： - 释放数据空间
free(ss->head) - 释放控制结构
free(ss)
- 释放数据空间
- 入栈操作
int PushSeqStack(SeqStack *ss, DATATYPE *data) // add
{if (NULL == ss || NULL == data || IsFullSeqStack(ss)){fprintf(stderr, "PushSeqStack pamter error\n");return 1;}memcpy(&ss->head[ss->top], data, sizeof(DATATYPE));ss->top++;return 0;
}- 实现流程：
if 栈未满：复制数据到ss->head[top]位置top++返回成功
else：返回失败
- 出栈操作
int PopSeqStack(SeqStack *ss)
{if (NULL == ss){fprintf(stderr, "PopSeqStack pamter error\n");return 1;}ss->top--;return 0;
}- 实现逻辑：
if 栈非空：top--返回成功
else：返回失败
- 判空操作
int IsEmpySeqStack(SeqStack *ss)
{return 0 == ss->top;
}- 判断条件：
top == 0
- 判满操作
int IsFullSeqStack(SeqStack *ss)
{return ss->tlen == ss->top;
}- 判断条件：
top == tlen
- 获取栈顶元素
DATATYPE *GetTopSeqStack(SeqStack *ss)
{if (NULL == ss || IsEmpySeqStack(ss)){fprintf(stderr, "GetTopSeqStack pamter error\n");return NULL;}return &ss->head[ss->top - 1];
}- 注意点：
- 返回
ss->head[top-1]的地址 - 需先判断栈是否为空
- 返回
- 获取栈大小
int GetSizeSeqStack(SeqStack *ss)
{if (NULL == ss ){fprintf(stderr, "GetSizeSeqStack pamter error\n");return 1;}return ss->top;
}- 直接返回
top值
三、存储结构示意图
栈底 → head[0]head[1]...
栈顶 → head[top-1] ← 当前有效元素head[top] ← 下一个可用位置（当top<tlen时）...head[tlen-1]
四、时间复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 创建栈 | O(1) | 内存分配操作 |
| 销毁栈 | O(1) | 内存释放操作 |
| 入栈/出栈 | O(1) | 直接操作栈顶指针 |
| 获取栈顶元素 | O(1) | 随机访问特性 |
| 获取栈大小 | O(1) | 直接读取top值 |
五、优势与局限
-
优势：
- 随机访问特性，支持快速定位
- 内存连续，缓存命中率高
- 操作时间复杂度均为O(1)
-
局限：
- 固定容量，需要预先分配空间
- 扩容成本高（需要重新分配内存）
- 可能产生空间浪费（分配未使用的空间）
六、典型应用场景
- 函数调用栈的实现
- 表达式求值（中缀转后缀表达式）
- 括号匹配检测
- 浏览器的后退操作栈
- 撤销/重做功能实现
七、实现注意事项
-
内存管理：
- 创建时需分配两次内存（控制结构+数据空间）
- 销毁时需按相反顺序释放
-
临界条件处理：
- 入栈前必须检查栈是否已满
- 出栈前必须检查栈是否为空
- 获取栈顶元素前必须检查非空
八、实际应用
1.符号匹配
main 函数
#include "./SeqStack.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int do_check(char *buf, SeqStack *ss, int num)
{int col = 1;DATATYPE data;while (*buf){DATATYPE *tmp = NULL;bzero(&data, sizeof(data));int c = *buf;switch (c){case '(':case '[':case '{':handle_left_bracket(c, num, col, &data, ss);break;case ')':case ']':case '}':if (handle_right_bracket(c, num, col, ss)){return 1;}break;}buf++;col++;}return 0;
}// 封装左括号的处理逻辑
void handle_left_bracket(int c, int num, int col, DATATYPE *data, SeqStack *ss)
{data->sym = c;data->linenum = num;data->colnum = col;PushSeqStack(ss, data);
}// 封装右括号的处理逻辑
int handle_right_bracket(int c, int num, int col, SeqStack *ss)
{DATATYPE *tmp = GetTopSeqStack(ss);if (tmp == NULL){printf("read sym:%c ,line:%d col:%d\n", c, num, col);return 1;}if ((c == ')' && tmp->sym == '(') ||(c == ']' && tmp->sym == '[') ||(c == '}' && tmp->sym == '{')){PopSeqStack(ss);return 0;}else{printf("read sym:%c ,line:%d col:%d or top sym:%c ,line:%d col:%d\n", c, num, col, tmp->sym, tmp->linenum, tmp->colnum);return 1;}
}
int main(int argc, char const *argv[])
{SeqStack *ss = CreateSeqStack(5);FILE *fp = fopen("./open.c", "r+");if (NULL == fp){perror("fopen");return 1;}int num = 1;int ret = 0;while (1){char buf[256] = {0};if (NULL == fgets(buf, sizeof(buf), fp)){break;}ret = do_check(buf, ss, num);if(1== ret){DestroySeqStack(ss);exit(1);}num++;/* code */}if(IsEmpySeqStack(ss)){printf("file ok\n");}else{DATATYPE *tmp = GetTopSeqStack(ss);printf("top sym:%c ,line:%d col:%d\n", tmp->sym, tmp->linenum, tmp->colnum);}return 0;
}
2.四则运算（栈）
int applyOperator(int a, int b, char op)
{switch (op){case '+':return a + b;case '-':return a - b;case '*':return a * b;case '/':return a / b;default:fprintf(stderr, "applyOperator error\n");return 0;}
}
int precedence(char op)
{if (op == '+' || op == '-'){return 1;}if (op == '*' || op == '/'){return 2;}return 0;
}
int evaluateExpression(char *expression)
{SeqStack *operand = CreateSeqStack(100);SeqStack *opertor = CreateSeqStack(100);int i = 0;while (expression[i] != '\0'){char c = expression[i];if (isdigit(c)){int num = 0;while (isdigit(expression[i])){num = num * 10 + (expression[i] - '0');i++;}DATATYPE data;data.op = '0';data.num = num;PushSeqStack(operand, &data);}else if (c == '+' || c == '-' || c == '*' || c == '/'){while (!IsEmpySeqStack(opertor) && precedence(c) <= precedence(GetTopSeqStack(opertor)->op)){DATATYPE opData = *GetTopSeqStack(opertor);PopSeqStack(opertor);DATATYPE bData = *GetTopSeqStack(operand);PopSeqStack(operand);DATATYPE aData = *GetTopSeqStack(operand);PopSeqStack(operand);int ret = applyOperator(aData.num, bData.num, opData.op);DATATYPE retData;retData.op = '0';retData.num = ret;PushSeqStack(operand, &retData);}DATATYPE data;data.op = c;PushSeqStack(opertor, &data);i++;}else{i++;}}// 处理运算符栈中剩余的运算符while (!IsEmpySeqStack(opertor)){DATATYPE opData = *GetTopSeqStack(opertor);PopSeqStack(opertor);DATATYPE bData = *GetTopSeqStack(operand);PopSeqStack(operand);DATATYPE aData = *GetTopSeqStack(operand);PopSeqStack(operand);int ret = applyOperator(aData.num, bData.num, opData.op);DATATYPE retData;retData.op = '0';retData.num = ret;PushSeqStack(operand, &retData);}int result = GetTopSeqStack(operand)->num;DestroySeqStack(operand);DestroySeqStack(opertor);return result;
}