数据结构（笔记）——顺序栈

1.顺序栈的定义

顺序栈是 栈的一种顺序存储结构，即用 一段连续的存储空间（通常是数组）来实现栈。
栈的特点是 先进后出（LIFO, Last In First Out）：

只能在一端（称为栈顶 Top）进行插入和删除。

另一端固定（称为栈底 Base）。

2.顺序栈特点

3.顺序栈与链栈优缺点

4.主要代码

初始化

void InitStack(SeqStack* s) { s->base = (ElemType*)malloc(sizeof(ElemType) * STACK_INIT_SIZE); assert(s->base != NULL); s->capacity = STACK_INIT_SIZE; s->top = 0; }

实现目的
初始化顺序栈，分配初始空间，设置容量和空栈状态。

实现步骤

malloc 分配 STACK_INIT_SIZE 个元素大小的连续内存。

assert 检查分配是否成功。

设置容量 capacity。

把栈顶指针 top 置 0，表示栈为空。

申请空间

bool Inc(SeqStack* s) { ElemType* newbase = (ElemType*)realloc(s->base, sizeof(ElemType) * (s->capacity + STACK_INC_SIZE)); if (newbase == NULL) { printf("空间已满.\n"); return false; } s->base = newbase; s->capacity += STACK_INC_SIZE; return true; }

实现目的
扩容：在栈满时，重新申请更大的空间。

实现步骤

调用 realloc 重新分配空间（在原有空间基础上 +STACK_INC_SIZE 个元素）。

如果返回 NULL，扩容失败，输出提示并返回 false。

否则更新 base 指针和 capacity，扩容成功返回 true。

判断栈满

bool IsFull(SeqStack* s) { return s->top >= s->capacity; }

判断栈空

bool IsEmpty(SeqStack* s) { return s->top == 0; }

插入

void Push(SeqStack* s, ElemType x) { if (IsFull(s) && !Inc(s)) { printf("空间已满，无法插入.\n", x); return; } s->base[s->top++] = x; //s->top++; }

实现目的
入栈：在栈顶插入新元素。

实现步骤

判断是否栈满：

如果满，尝试扩容 Inc。

如果扩容失败，提示并返回。

将新元素存入数组 base[top]。

top++，指向下一个空位置。

删除

void Pop(SeqStack* s) { if (IsEmpty(s)) { printf("栈为空，无法删除.\n"); return; } s->top--; }

实现目的
出栈：删除栈顶元素。

实现步骤

如果栈空，输出提示，返回。

否则 top--，相当于丢弃栈顶元素。

查看栈顶元素

bool GetTop(SeqStack* s, ElemType* v) { if (IsEmpty(s)) { printf("栈为空，无法得到栈头.\n"); return false; } *v = s->base[s->top - 1]; return true; }

实现目的
取栈顶元素，但不删除。

实现步骤

如果栈空，提示并返回 false。

否则，将 top-1 位置的元素赋给 *v，返回 true。

显示

void Show(SeqStack* s) { for (int i = s->top - 1; i >= 0; --i) { printf("%d\n", s->base[i]); } printf("\n"); }

实现目的
打印栈中所有元素（从栈顶到栈底）。

实现步骤

循环从 top-1 到 0，依次输出。

打印换行结束。

长度

int Length(SeqStack* s) { return s->top; }

清除

void Clear(SeqStack* s) { s->top = 0; }

销毁

void Destroy(SeqStack* s) { free(s->base); s->base = NULL; s->capacity = s->top = 0; }

5.栈的应用

应用1

// 行编辑程序，利用顺序栈实现简单的文本编辑功能 void LineEdit() { SeqStack st; // 定义一个顺序栈变量 InitStack(&st); // 初始化栈，置为空栈 char ch = getchar(); // 读入一个字符 while (ch != '$') // 以 $ 作为结束符，遇到 $ 停止输入 { while (ch != '$' && ch != '\n') // 直到遇到换行或结束符 { switch (ch) // 根据不同的输入字符进行处理 { case '#': // 输入 # 表示删除前一个字符 Pop(&st); // 出栈一个字符（删除） break; case '@': // 输入 @ 表示清空一行 Clear(&st); // 清空栈 break; default: // 普通字符 Push(&st, ch); // 入栈保存 break; } ch = getchar(); // 继续读取下一个字符 } Print(&st); // 一行输入结束后，输出当前栈内容 ch = getchar(); // 继续读下一个字符，判断是否为 $ } Destroy(&st); // 输入结束后，销毁栈，释放资源 } void main() { printf("请输入字符序列，'$'结束输入，'#'删除，'@'清空："); LineEdit(); // 调用行编辑程序 }

应用2

// 将十进制数转换为八进制并输出 void Convert_8(int value) { SeqStack st; // 定义一个顺序栈 InitStack(&st); // 初始化栈（空栈） int v; // 用于临时存放栈顶元素 // ---- 第一步：不断取余数入栈 ---- while (value) // 当 value 还不为 0 时继续循环 { Push(&st, value % 8); // 将 value 除以 8 的余数压入栈中 value /= 8; // value 更新为 value / 8，继续处理 } // 循环结束时，余数按照“低位先入栈”的顺序存放在栈中 // ---- 第二步：出栈并输出 ---- while (!IsEmpty(&st)) // 栈不为空时继续 { GetTop(&st, &v); // 获取栈顶元素，赋值给 v Pop(&st); // 出栈，删除这个栈顶元素 printf("%d", v); // 输出该元素（按出栈顺序得到八进制高位到低位） } printf("\n"); // 换行 } void main() { int value = 47183; // 定义一个十进制整数 Convert_8(value); // 调用函数，将其转换为八进制并输出 }

47183 ÷ 8 = 5897 余 7 5897 ÷ 8 = 737 余 1 737 ÷ 8 = 92 余 1 92 ÷ 8 = 11 余 4 11 ÷ 8 = 1 余 3 1 ÷ 8 = 0 余 1

入栈顺序（从低位到高位）：7, 1, 1, 4, 3, 1

出栈顺序（高位到低位）：1 3 4 1 1 7

应用3

// 函数：检查字符串中的括号是否匹配 bool Cheak(char *str) { SeqStack st; // 定义一个顺序栈 InitStack(&st); // 初始化栈为空 char v; // 用于保存栈顶元素 // ---- 遍历字符串 ---- while (*str != '\0') // 遍历直到字符串结束符 { // 如果遇到左括号 '[' 或 '(' if (*str == '[' || *str == '(') { Push(&st, *str); // 入栈保存 } // 如果遇到右括号 ']' else if (*str == ']') { GetTop(&st, &v); // 取栈顶元素 if (v != '[') // 如果不是对应的 '[' return false; // 括号不匹配，直接返回错误 Pop(&st); // 匹配成功，弹出左括号 } // 如果遇到右括号 ')' else if (*str == ')') { GetTop(&st, &v); // 取栈顶元素 if (v != '(') // 如果不是对应的 '(' return false; // 括号不匹配 Pop(&st); // 匹配成功，弹出左括号 } ++str; // 指向下一个字符 } // ---- 判断最终结果 ---- return IsEmpty(&st); // 栈为空表示完全匹配，否则有多余左括号 } // 主函数：测试括号匹配 void main() { char *str = "[([(])[])]"; // 测试字符串 bool flag = Cheak(str); // 调用检查函数 if (flag) // 如果匹配成功 { printf("OK!\n"); } else // 匹配失败 { printf("Error!\n"); } }

遇到左括号 → 入栈

把 [ 或 ( 入栈，等候匹配。

遇到右括号 → 检查栈顶

如果栈顶不是对应的左括号 → 说明不匹配，返回 false。

如果匹配 → 弹出栈顶，继续检查下一个字符。

遍历结束

如果栈为空，说明左右括号完全匹配 → 返回 true。

如果栈非空，说明还有没匹配的左括号 → 返回 false。