企业官网建设流程全解析

引言

栈（Stack）是计算机科学中最基础、最重要的数据结构之一。它的"后进先出"（LIFO，Last In First Out）特性使其在函数调用、表达式求值、括号匹配、浏览器前进后退等场景中扮演着不可替代的角色。

本文将从零开始，详细讲解顺序栈的完整实现。顺序栈使用连续内存（数组）存储元素，是最直观的栈实现方式。

栈的 LIFO 特性示意 入栈 (Push) 出栈 (Pop) ┌─────┐ ┌─────┐ │ │ ← top │ │ │ 3 │ 进 │ 3 │ 出 │ 2 │ ←── │ 2 │ ──→ │ 1 │ │ 1 │ └─────┘ ← base └─────┘ ← base 后进 (3) 的在上方 后进 (3) 的先出来 先进 (1) 的在下方 先进 (1) 的后出来

第一部分：顺序栈的设计原理

一、核心数据区：三指针设计

typedef struct SeqStack { ElemType* base; // 指向栈底（分配的起始地址） ElemType* top; // 指向栈顶元素的上一个空闲位置 size_t stacksize; // 当前总容量（元素个数，不是字节数） } SeqStack;

设计要点解析：

1. base→ 指向分配的起始地址：用于内存管理和定位栈底

2. top→ 指向栈顶元素的上方：这是经典设计，空栈时top == base

3. stacksize→ 当前容量：用于判断是否已满，是否需要扩容

二、关键指针关系

关键规律：

三、空栈与满栈判断

第二部分：基础常量设计

设计良好的常量是数据结构的骨架。在顺序栈中使用两个关键常量：

#define STACKINITSIZE 10 // 初始容量 #define STACKINCREMENT 2 // 扩容倍数

一、初始容量 STACKINITSIZE

初始容量为 10 意味着第一次分配 10 个ElemType元素的空间（不是 10 字节）。

容量规划建议：

二、扩容倍数 STACKINCREMENT

用 2 倍扩容，每次重新分配时旧空间翻倍。

扩容策略对比：

第三部分：初始化与销毁

一、初始化实现

void InitStack(SeqStack* ps) { assert(ps != NULL); ElemType* p = (ElemType*)malloc(sizeof(ElemType) * STACKINITSIZE); if (p == NULL) return; // 分配失败，静默返回 ps->base = p; ps->top = p; // 空栈，top == base ps->stacksize = STACKINITSIZE; }

初始化后状态：

二、销毁实现

void DestroyStack(SeqStack* ps) { assert(ps != NULL); free(ps->base); ps->base = NULL; ps->top = NULL; ps->stacksize = 0; }

初始化和销毁的对称操作应当严格配对：

• 初始化 →malloc分配空间

• 销毁 →free释放空间，所有指针置NULL

• 不正确的是：初始化后未使用就直接销毁，或同一次栈被多次销毁

第四部分：扩容机制

一、封装的扩容函数

bool expansion(SeqStack* ps) { assert(ps != NULL); int newsize = ps->stacksize * STACKINCREMENT; ElemType* newbase = (ElemType*)malloc(sizeof(ElemType) * newsize); if (newbase == NULL) return false; // 使用 memmove 复制内容，因为原空间和新空间是独立的 memmove(newbase, ps->base, sizeof(ElemType) * ps->stacksize); // 用新的基地址重新设置 top ps->top = newbase + (ps->base - ps->top); // 注意：这里是 base - top（负值） free(ps->base); // 释放原空间 ps->base = newbase; ps->stacksize = newsize; return true; }

二、扩容过程图解

三、扩容检查的时机

bool Push(SeqStack* ps, ElemType val) { assert(ps != NULL); // 先检查是否需要扩容 if (Isfull(ps)) { if (expansion(ps) == false) { printf("扩容失败\n"); return false; } } // 然后入栈 *ps->top++ = val; return true; }

第五部分：核心操作实现

一、Push 入栈操作

bool Push(SeqStack* ps, ElemType val) { assert(ps != NULL); if (Isfull(ps)) { if (expansion(ps) == false) { printf("扩容失败\n"); return false; } } *ps->top++ = val; // ① 存入值 ② top指向下一个空闲位置 return true; }

操作对应的指针移动：

二、Pop 出栈并获取栈顶元素

bool Pop(SeqStack* ps, ElemType* pval) { assert(ps != NULL); assert(pval != NULL); // 不能为 NULL if (Isempty(ps)) return false; *pval = *--ps->top; // ① top先减1 ② 读取元素 return true; }

原因分析：top指向的是空闲位置的上方，出栈时需要先将 top 减1才能读取。

三、GetTop 仅获取栈顶元素

bool GetTop(SeqStack* ps, ElemType* pval) { assert(ps != NULL); assert(pval != NULL); if (Isempty(ps)) return false; *pval = *(ps->top - 1); // 直接读取，不移动 top return true; }

Pop 与 GetTop 的对比：

四、清空栈

void ClearStack(SeqStack* ps) { assert(ps != NULL); ps->top = ps->base; // 仅修改 top 指针，不释放内存 }

清空 vs 销毁的区别：

清空后栈仍可继续使用（已分配空间不会收回），销毁后需要重新初始化。

第六部分：遍历与辅助操作

一、打印（遍历）

void Print(SeqStack* ps) { assert(ps != NULL); // 从 top-1 开始，向 base 方向递减打印 for (ElemType* p = ps->top - 1; p >= ps->base; p--) { printf("%c ", *p); } printf("\n"); }

遍历方向：从栈顶向栈底打印，符合 LIFO 的视觉习惯。

二、各操作时间复杂度

所有操作都是 O(1)，效率极高，这得益于顺序表的连续存储特性。

第七部分：顺序栈的优缺点

优点

// 1. 操作简单，就地存取值 *ps->top++ = val; // 入栈 *--ps->top; // 出栈 // 2. 遍历方便 ps->top - ps->base // 直接计算元素个数

缺点

// 1. 扩容时开销大 // 需要重新 malloc、memmove、free // 2. 空间浪费 // 扩容后可能多出很多未用的空间 // 3. 内存碎片 // 动态分配回收可能产生碎片

第八部分：实用技巧

一、常见错误防范

// ❌ 错误：top 指针忘记更新 *ps->top = val; // 已写入，但 top 未移向下一位置 // ✓ 正确 *ps->top++ = val; // 先写再后移 // ❌ 错误：忘记检查输入参数 bool Pop(SeqStack* ps, ElemType *pval) { *pval = *--ps->top; // 如果 pval==NULL 会崩溃 } // ✓ 正确：加断言 bool Pop(SeqStack* ps, ElemType *pval) { assert(ps != NULL && pval != NULL); if (Isempty(ps)) return false; *pval = *--ps->top; return true; }

二、通用设计模式

// ① 总是用 assert 保护指针参数 void Func(SeqStack* ps) { assert(ps != NULL); // 调试阶段发现调用错误 // ... } // ② 扩容失败时优雅降级 if (expansion(ps) == false) { printf("扩容失败\n"); return false; // 不丢失已有数据 } // ③ 清空不释放内存，可频繁复用 ClearStack(ps); // 只是重置 top 指针 // 继续 Push 无需重新 malloc

总结

一句话总结：顺序栈用三根指针在连续内存上实现 LIFO 行为。Pop 与 Push 都只需要 O(1) 时间，通过覆盖 top 指针实现逻辑上的增减（不实际清除旧元素）。当容量不够时采用倍数扩容策略，确保均摊复杂度仍为 O(1)。