当前位置：首页 > news >正文

栈：隐匿于计算机科学长卷的璀璨明珠

news 来源：原创 2025/7/14 23:05:02

🚀前言

大家好！我是 EnigmaCoder。

在计算机科学的宏大版图中，栈是一颗虽小却极为耀眼的明珠。它是一种基础且重要的数据结构，在程序的运行、算法的实现以及系统的底层操作等诸多方面都扮演着不可或缺的角色。栈的应用场景广泛，从编译器对代码的解析，到浏览器中页面的前进后退功能，都能看到它的身影。理解栈的概念、实现方式及其应用，是掌握编程技术的关键一步，它为开发者提供了高效组织和管理数据的方法，帮助我们更好地构建复杂的软件系统。

🌟栈的概念

栈本质上是一种线性数据结构，遵循后进先出（Last In First Out，LIFO）的原则。想象一下食堂里堆叠起来的餐盘，后放上去的餐盘总是先被取走，这便是栈的工作方式。
从操作层面看，栈提供了一系列核心操作。入栈（push）操作就像是往餐盘堆上放一个新餐盘，将元素添加到栈顶；出栈（pop）操作则是从餐盘堆取走最上面的餐盘，移除并返回栈顶元素；查看栈顶元素（peek）功能类似看一眼餐盘堆最上面的餐盘是什么样子，获取栈顶元素的值但不移除它；判断栈是否为空（isEmpty）用于确定餐盘堆里有没有餐盘；获取栈的大小（size）能让我们知道餐盘堆里一共有多少个餐盘。这些操作构成了栈数据结构的基本接口，为我们管理和操作数据提供了便利。

🤔栈的两种实现形式

💯数组栈实现

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include <limits.h> // 用于INT_MAXconst int MAX_SIZE = 100; // 定义栈的最大容量// 定义数组栈结构体
typedef struct {int* data; // 指向存储栈元素的动态数组int size;  // 栈中当前元素的个数
} ArrayStack;// 创建一个新的数组栈
ArrayStack* newArrayStack() {// 分配栈结构体的内存ArrayStack* stack = malloc(sizeof(ArrayStack));// 分配存储栈元素的数组内存stack->data = malloc(sizeof(int) * MAX_SIZE);// 初始化栈的大小为0（空栈）stack->size = 0;return stack;
}// 销毁数组栈
void delArrayStack(ArrayStack* stack) {// 释放存储栈元素的数组内存free(stack->data);// 释放栈结构体的内存free(stack);
}// 获取栈的大小
int size(ArrayStack* stack) {return stack->size; // 返回栈中元素的个数
}// 判断栈是否为空
bool isEmpty(ArrayStack* stack) {return stack->size == 0; // 如果栈的大小为0，则栈为空
}// 入栈操作
void push(ArrayStack* stack, int num) {// 检查栈是否已满if (stack->size == MAX_SIZE) {printf("Error: Stack is full!\n");return;}// 将新元素添加到数组的末尾stack->data[stack->size] = num;// 栈的大小加1stack->size++;
}// 查看栈顶元素
int peek(ArrayStack* stack) {// 检查栈是否为空if (isEmpty(stack)) {printf("Error: Stack is empty!\n");return INT_MAX; // 返回错误值}// 返回数组的最后一个元素（栈顶）return stack->data[stack->size - 1];
}// 出栈操作
int pop(ArrayStack* stack) {// 检查栈是否为空if (isEmpty(stack)) {printf("Error: Stack is empty!\n");return INT_MAX; // 返回错误值}// 获取栈顶元素的值int val = stack->data[stack->size - 1];// 栈的大小减1stack->size--;return val; // 返回出栈的值
}int main() {// 创建一个新的数组栈ArrayStack* stack = newArrayStack();// 入栈操作push(stack, 10); // 将10压入栈push(stack, 20); // 将20压入栈push(stack, 30); // 将30压入栈// 输出栈的大小printf("栈的元素总数：%d\n", size(stack)); // 输出3// 查看栈顶元素printf("栈顶元素: %d\n", peek(stack)); // 输出30// 出栈操作printf("出栈元素: %d\n", pop(stack));  // 输出30printf("出栈元素: %d\n", pop(stack));  // 输出20// 再次查看栈顶元素printf("栈顶元素: %d\n", peek(stack)); // 输出10// 销毁栈delArrayStack(stack);return 0;
}

在这段代码中，首先定义了一个ArrayStack结构体，它包含一个指向整数数组的指针data，用于存储栈中的元素，以及一个表示栈中当前元素个数的size。newArrayStack函数负责创建一个新的数组栈，为结构体和存储元素的数组分配内存，并初始化size为0。入栈时，先检查栈是否已满，若未满则将新元素添加到数组的size位置，并增加size的值。出栈时，先检查栈是否为空，若不为空则取出栈顶元素，减小size的值。查看栈顶元素操作类似，只是不改变栈的状态。最后在main函数中对这些功能进行了测试。

💯链表栈实现

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include <limits.h> // 用于INT_MAX// 定义链表节点结构体
typedef struct {int val;           // 节点存储的值struct ListNode* next; // 指向下一个节点的指针
} ListNode;// 定义链表栈结构体
typedef struct {ListNode* top;     // 栈顶指针（指向栈顶节点）int size;          // 栈中元素的个数
} LinkedListStack;// 创建一个新的链表栈
LinkedListStack* newLinkListStack() {// 分配链表栈的内存LinkedListStack* s = malloc(sizeof(LinkedListStack));// 初始化栈顶指针为NULL（空栈）s->top = NULL;// 初始化栈的大小为0s->size = 0;// 返回创建的栈return s;
}// 销毁链表栈
void delLinkListStack(LinkedListStack* s) {// 遍历栈中的所有节点while (s->top) {// 保存当前栈顶节点的下一个节点ListNode* n = s->top->next;// 释放当前栈顶节点的内存free(s->top);// 更新栈顶指针为下一个节点s->top = n;}// 释放栈本身的内存free(s);
}// 获取栈的大小
int size(LinkedListStack* s) {// 返回栈中元素的个数return s->size;
}// 判断栈是否为空
bool isEmpty(LinkedListStack* s) {// 如果栈的大小为0，则栈为空return size(s) == 0;
}// 入栈操作
void push(LinkedListStack* s, int num) {// 分配新节点的内存ListNode* node = (ListNode*)malloc(sizeof(ListNode));// 设置新节点的值node->val = num;// 新节点的next指针指向当前栈顶node->next = s->top;// 更新栈顶指针为新节点s->top = node;// 栈的大小加1s->size++;
}// 查看栈顶元素
int peek(LinkedListStack* s) {// 如果栈为空，输出错误信息并返回错误值if (isEmpty(s)) {printf("Error: Stack is empty!\n");return INT_MAX;}// 返回栈顶节点的值return s->top->val;
}// 出栈操作
int pop(LinkedListStack* s) {// 首先调用peek检查栈是否为空int val = peek(s);// 如果栈为空，返回错误值if (val == INT_MAX) {return INT_MAX;}// 保存当前栈顶节点ListNode* tmp = s->top;// 更新栈顶指针为下一个节点s->top = s->top->next;// 释放当前栈顶节点的内存free(tmp);// 栈的大小减1s->size--;// 返回出栈的值return val;
}int main() {// 创建一个新的链表栈LinkedListStack* s = newLinkListStack();// 入栈操作push(s, 10); // 将10压入栈push(s, 20); // 将20压入栈push(s, 30); // 将30压入栈// 输出栈的大小printf("栈的元素总数：%d\n", size(s)); // 输出3// 查看栈顶元素printf("栈顶元素: %d\n", peek(s)); // 输出30// 出栈操作printf("出栈元素: %d\n", pop(s));  // 输出30printf("出栈元素: %d\n", pop(s));  // 输出20// 再次查看栈顶元素printf("栈顶元素: %d\n", peek(s)); // 输出10// 销毁栈delLinkListStack(s);return 0;
}

这里定义了链表节点结构体ListNode和链表栈结构体LinkedListStack。LinkedListStack中的top指针指向栈顶节点，size记录栈中元素个数。创建链表栈时，初始化top为NULL，size为0。入栈操作通过创建新节点，将其next指针指向当前栈顶，再更新top指针实现。出栈时，先检查栈是否为空，若不为空则保存栈顶节点的值，更新top指针指向下一个节点，释放原栈顶节点内存，并减小size。查看栈顶元素直接返回top节点的值。main函数对链表栈的功能进行了验证。

⚙️数组栈与链表栈对比

对比项	数组栈	链表栈
内存分配	初始化时分配固定大小内存，若栈满需手动扩容或报错。比如设置最大容量为100，当栈中元素达到100时就无法再添加，除非手动调整容量。	动态分配内存，按需增加节点，无固定容量限制。每添加一个元素就分配一个新节点的内存，不会出现容量不足的情况。
操作效率	入栈、出栈、查看栈顶操作时间复杂度均为O(1)，但栈满时处理复杂。如果栈满后想继续添加元素，需要重新分配更大的内存空间并复制数据，这一过程较为耗时。	入栈、出栈、查看栈顶操作时间复杂度均为O(1)，内存管理开销稍大。每次操作都涉及到内存的分配和释放，相比数组栈多了一些额外的开销。
空间复杂度	平均情况下空间利用率高，栈不满时存在内存浪费；最坏情况下栈满需扩容。若只使用了数组容量的一小部分，其余部分就被闲置。	每个节点有额外指针开销，空间利用率相对较低，但无内存浪费问题。每个节点除了存储数据，还需要一个指针指向下一个节点，会占用更多内存。
应用场景	适用于元素数量可预估且变化不大的场景，如编译器的词法分析。词法分析过程中，符号的数量通常不会有太大波动，可以预先设定合适的数组大小。	适用于元素数量不确定、频繁插入删除的场景，如函数调用栈。函数调用的次数和时机难以预测，链表栈可以灵活地适应这种变化。

🐧递归与栈

递归是一种强大的编程技术，函数在执行过程中调用自身。
在递归执行时，系统会利用栈来管理函数调用的状态。以计算阶乘的递归函数为例，当函数开始递归调用时，每一层函数调用的参数、局部变量等信息会像餐盘一样被依次压入栈中。随着递归的深入，栈中的数据越来越多。当递归开始返回时，这些信息会按照后进先出的顺序从栈中弹出，用于计算最终的结果。这完美地体现了栈的特性，栈就像是递归过程的幕后助手，有条不紊地管理着函数调用的各种状态，确保递归的正确执行。

💻总结

栈作为计算机科学中基础的数据结构，其重要性不言而喻。数组栈和链表栈两种实现方式各有千秋，它们在不同的场景下发挥着各自的优势。无论是处理固定规模的数据，还是应对动态变化的数据需求，都能找到合适的栈实现方式。理解栈的原理和应用，不仅有助于我们编写更高效的代码，还能让我们深入理解递归等复杂的编程概念。在未来的编程学习和实践中，栈将继续作为重要的工具，助力开发者解决各种实际问题，推动技术的不断进步。

目录

🚀前言