[数据结构]栈的实现与应用

一、引言

栈，作为一种基础且重要的数据结构，在计算机科学领域中有着广泛的应用。它不仅为函数调用提供了必要的支持，还在算法设计和问题解决中发挥着关键作用。本文将对栈的基本概念、实现方式以及函数栈帧进行详细的介绍和分析。

---

二、栈的基本概念

1、栈是什么

栈是一种特殊的线性数据结构，其只允许在固定的一端进行插入和删除操作。插入和删除的这一端被称为栈顶，而另一端则被称为栈底。栈遵循后进先出的原则，即最后插入的元素会最先被删除。这种特性使得栈在算法设计和问题解决中具有独特的优势。

2、栈的实现方式对比

• 数组实现：将数组的尾部充当栈顶，数据的插入与删除操作变得非常高效。同时数组的结构，使得其CPU高速缓存的命中率较高。唯一的缺陷就是，扩容或缩容会有一定的性能开销。
• 链表实现：采用单链表结构，将链表头部设为栈顶，数据的插入与删除操作同样能高效完成。但链表需要额外的存储空间来保存指针信息，且由于链表的结构，CPU高速缓存的命中率相对较低。此外，链表实现的复杂度相较于数组实现也更高一些。

3、函数栈帧

在函数调用过程中，系统会为每个函数分配一个栈帧。栈帧中存储了函数的局部变量、参数以及返回地址等信息。当函数执行完毕后，其栈帧会被销毁，从而释放占用的栈空间。函数栈帧的分配和销毁过程体现了栈的后进先出原则。

函数栈帧的存在使得函数调用具有嵌套性，即一个函数可以调用另一个函数，而被调用的函数又可以继续调用其他函数。这种嵌套调用关系通过栈来维护，确保了函数调用的正确性和稳定性。

---

三、栈的实现

1、结构体定义

首先，定义了栈的数据结构。栈使用动态数组来存储元素，同时记录了栈顶索引和栈的容量。

typedef int DataType;
typedef struct Stack {DataType* array;int top;int capacity;
}S;

2、初始化

接下来，实现了栈的初始化函数。该函数为栈分配内存，并初始化栈顶索引和容量。

void Init(S* ps, int capacity)
{assert(ps != NULL && capacity >= 0);DataType* pos = (DataType*)malloc(sizeof(DataType) * capacity);if (pos == NULL){fprintf(stderr, "内存分配失败");exit(EXIT_FAILURE);}ps->array = pos;ps->capacity = capacity;ps->top = -1;
}

3、销毁

实现了栈的销毁函数。该函数释放栈所占用的内存，并将栈的指针、容量和栈顶索引重置为初始状态。

void Destroy(S* ps)
{if (ps == NULL)return;free(ps->array);ps->array = NULL;ps->capacity = 0;ps->top = -1;
}

4、显示

实现了栈的显示函数。该函数遍历栈中的元素，并调用用户定义的打印函数来打印每个元素。

void Print(S* ps, void (*Prin)(DataType))
{assert(ps != NULL);for (int i = ps->top; i >= 0; i--){Prin(ps->array[i]);}printf("\n");
}

5、数据操作

void Push(S* ps, DataType data)
{assert(ps != NULL);if (ps->top == ps->capacity - 1){int capacity = ps->capacity == 0 ? 2 : ps->capacity * 2;DataType* pos = (DataType*)realloc(ps->array, sizeof(DataType) * capacity * 2);if (pos == NULL){fprintf(stderr, "内存分配失败");exit(EXIT_FAILURE);}ps->array = pos;ps->capacity = capacity;}ps->array[++(ps->top)] = data;
}void Pop(S* ps)
{assert(ps != NULL && ps->top != -1);if (ps->capacity > 64 && ps->top < ps->capacity / 3){int capacity = ps->capacity / 3;DataType* pos = (DataType*)realloc(ps->array, sizeof(DataType) * capacity);if (pos == NULL){fprintf(stderr, "内存分配失败");exit(EXIT_FAILURE);}ps->array = pos;ps->capacity = capacity;}ps->top--;
}DataType Top(S* ps)
{assert(ps != NULL);return ps->array[ps->top];
}

---

四、分析栈

1、优点

• 操作简便：栈提供了简洁的接口，如push（入栈）和pop（出栈），使得元素的操作非常直观和方便。
• 高效性：对于大多数栈实现，push和pop操作的时间复杂度均为O(1)，保证了高效的元素访问速度。
• 应用场景广泛：栈在多种算法和数据结构中都有重要应用，如深度优先搜索（DFS）、表达式求值、括号匹配等。

2、缺点

• 访问限制：栈只允许在栈顶进行元素的插入和删除操作，无法直接访问栈内的其他元素，限制了其灵活性。

---

五、总结

1、练习题

• 有效的括号
• 最小栈
• 用栈操作构建数组
• 堆盘子

2、源代码

对于栈的源代码我已经开源在GItee：传送门。

---