顺序栈与动态扩展：从数组到指针的实现

本文主要探讨了栈的两种常见结构——顺序栈（基于数组）和动态扩展的顺序栈（基于指针），以及它们的基本操作。在顺序栈中，作者提到了固定大小数组可能导致的空间浪费和不足问题，并介绍了如何通过使用指针和`realloc()`函数来动态调整空间，以避免这些问题。 在数据结构中，栈是一种非常重要的抽象数据类型，它遵循“后进先出”（LIFO）的原则。栈通常用于函数调用、表达式求值、内存管理等多种场景。这里主要讨论了两种栈的实现方式： 1. **固定大小的顺序栈**： - 使用数组作为底层存储，结构简单，易于理解和实现。 - 优点是访问速度快，因为数组元素在内存中是连续的，且所有操作的时间复杂度都是O(1)。 - 缺点是栈的大小在创建时必须预设，可能导致空间浪费（如果实际元素数量少于预设值）或空间不足（如果元素数量超过预设值）。 2. **动态扩展的顺序栈**： - 用指针指向动态分配的一块内存区域，初始大小可设定，如文中定义的`size`。 - 当空间不足时，通过`realloc()`函数扩展内存，保持数据的连续性并避免数据丢失。 - 这种方法解决了固定大小栈的局限性，但操作相对复杂，如需要检查内存分配是否成功，且在频繁的扩展操作中可能增加额外的时间开销。 文中还展示了使用C语言实现的动态扩展顺序栈的一些基本操作函数： - `InitStack(sqstack *s)`：初始化栈，分配`MAXSIZE`大小的内存，设置栈顶指针`top`，并检查分配失败的情况。 - 其他可能的操作包括：`Push()`（入栈，增加栈顶指针），`Pop()`（出栈，减少栈顶指针），`GetTop()`（获取栈顶元素但不删除），`IsEmpty()`（检查栈是否为空），`IsFull()`（检查栈是否满），以及`DestroyStack()`（释放栈所占内存）等。 在实际编程中，选择栈的实现方式取决于具体的应用场景。对于对空间效率有较高要求且元素数量可预估的场景，固定大小的顺序栈可能是更好的选择。而在元素数量不确定或可能大幅变化的情况下，动态扩展的顺序栈能提供更大的灵活性。无论哪种实现，都需要考虑到性能和内存管理的平衡。