栈是遵循后进先出原则的数据结构，仅允许在栈顶进行元素的插入和删除操作，核心操作包括入栈、出栈、获取栈顶元素、判断栈空等。在C语言中实现栈主要有数组和链表两种常见方式，二者各有适用场景。
栈的核心操作定义
无论采用哪种实现方式，栈的基础操作逻辑是一致的，我们先定义统一的操作接口，方便后续两种实现的对比：
- 初始化栈：为栈分配初始资源，设置栈的初始状态
- 入栈：将新元素添加到栈顶位置
- 出栈：移除栈顶元素并返回该元素的值
- 获取栈顶元素：返回栈顶元素但不移除它
- 判断栈空：检查栈中是否还有元素
- 销毁栈：释放栈占用的所有资源
基于数组的栈实现
数组实现的栈会预先分配一块连续的内存空间存储栈元素，用变量记录当前栈顶的索引位置。这种实现方式逻辑简单，访问速度快，但容量固定，扩容需要重新分配内存。
结构体定义与初始化
我们先定义数组栈的结构体，包含存储元素的数组、栈顶索引和栈的最大容量：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 定义栈存储的元素类型，这里以int为例
typedef int StackData;
// 数组栈结构体
typedef struct {
StackData* data; // 存储栈元素的数组
int top; // 栈顶索引，初始为-1表示空栈
int capacity; // 栈的最大容量
} ArrayStack;
// 初始化数组栈，传入初始容量
ArrayStack* array_stack_init(int capacity) {
ArrayStack* stack = (ArrayStack*)malloc(sizeof(ArrayStack));
if (stack == NULL) {
return NULL;
}
stack->data = (StackData*)malloc(sizeof(StackData) * capacity);
if (stack->data == NULL) {
free(stack);
return NULL;
}
stack->top = -1;
stack->capacity = capacity;
return stack;
}
核心操作实现
接下来实现数组栈的入栈、出栈等核心操作：
// 判断数组栈是否为空
bool array_stack_is_empty(ArrayStack* stack) {
if (stack == NULL) {
return true;
}
return stack->top == -1;
}
// 入栈操作，成功返回true，失败返回false
bool array_stack_push(ArrayStack* stack, StackData value) {
if (stack == NULL || stack->data == NULL) {
return false;
}
// 栈满判断
if (stack->top + 1 >= stack->capacity) {
printf("栈已满，无法入栈n");
return false;
}
stack->top++;
stack->data[stack->top] = value;
return true;
}
// 出栈操作，成功返回true，元素值通过参数返回，失败返回false
bool array_stack_pop(ArrayStack* stack, StackData* value) {
if (stack == NULL || array_stack_is_empty(stack)) {
return false;
}
*value = stack->data[stack->top];
stack->top--;
return true;
}
// 获取栈顶元素，成功返回true，元素值通过参数返回，失败返回false
bool array_stack_peek(ArrayStack* stack, StackData* value) {
if (stack == NULL || array_stack_is_empty(stack)) {
return false;
}
*value = stack->data[stack->top];
return true;
}
// 销毁数组栈，释放所有资源
void array_stack_destroy(ArrayStack* stack) {
if (stack == NULL) {
return;
}
if (stack->data != NULL) {
free(stack->data);
}
free(stack);
}
使用示例
下面是数组栈的简单使用测试代码：
int main() {
// 初始化容量为5的数组栈
ArrayStack* stack = array_stack_init(5);
if (stack == NULL) {
printf("栈初始化失败n");
return 1;
}
// 入栈测试
for (int i = 1; i <= 5; i++) {
if (array_stack_push(stack, i)) {
printf("入栈元素：%dn", i);
}
}
// 测试栈满情况
array_stack_push(stack, 6);
// 获取栈顶元素
StackData top_val;
if (array_stack_peek(stack, &top_val)) {
printf("当前栈顶元素：%dn", top_val);
}
// 出栈测试
StackData pop_val;
while (!array_stack_is_empty(stack)) {
if (array_stack_pop(stack, &pop_val)) {
printf("出栈元素：%dn", pop_val);
}
}
// 销毁栈
array_stack_destroy(stack);
return 0;
}
基于链表的栈实现
链表实现的栈不需要预先分配固定大小的内存，每个节点动态分配，栈顶对应链表的头节点，这种实现方式容量灵活，但每个节点需要额外存储指针，内存开销更大。
结构体定义与初始化
链表栈的结构体包含栈顶节点指针和栈的大小，节点结构体包含数据域和指向下一个节点的指针：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 定义栈存储的元素类型
typedef int StackData;
// 链表节点结构体
typedef struct StackNode {
StackData data; // 节点存储的数据
struct StackNode* next; // 指向下一个节点的指针
} StackNode;
// 链表栈结构体
typedef struct {
StackNode* top; // 栈顶节点指针
int size; // 栈的当前大小
} LinkedStack;
// 初始化链表栈
LinkedStack* linked_stack_init() {
LinkedStack* stack = (LinkedStack*)malloc(sizeof(LinkedStack));
if (stack == NULL) {
return NULL;
}
stack->top = NULL;
stack->size = 0;
return stack;
}
核心操作实现
链表栈的入栈操作相当于在链表头部插入新节点，出栈操作相当于删除链表头节点：
// 判断链表栈是否为空
bool linked_stack_is_empty(LinkedStack* stack) {
if (stack == NULL) {
return true;
}
return stack->top == NULL;
}
// 入栈操作，成功返回true，失败返回false
bool linked_stack_push(LinkedStack* stack, StackData value) {
if (stack == NULL) {
return false;
}
// 创建新节点
StackNode* new_node = (StackNode*)malloc(sizeof(StackNode));
if (new_node == NULL) {
return false;
}
new_node->data = value;
// 新节点指向原栈顶
new_node->next = stack->top;
// 更新栈顶为新节点
stack->top = new_node;
stack->size++;
return true;
}
// 出栈操作，成功返回true，元素值通过参数返回，失败返回false
bool linked_stack_pop(LinkedStack* stack, StackData* value) {
if (stack == NULL || linked_stack_is_empty(stack)) {
return false;
}
StackNode* temp = stack->top;
*value = temp->data;
// 更新栈顶为下一个节点
stack->top = temp->next;
free(temp);
stack->size--;
return true;
}
// 获取栈顶元素，成功返回true，元素值通过参数返回，失败返回false
bool linked_stack_peek(LinkedStack* stack, StackData* value) {
if (stack == NULL || linked_stack_is_empty(stack)) {
return false;
}
*value = stack->top->data;
return true;
}
// 销毁链表栈，释放所有节点资源
void linked_stack_destroy(LinkedStack* stack) {
if (stack == NULL) {
return;
}
StackNode* current = stack->top;
StackNode* temp;
// 遍历释放所有节点
while (current != NULL) {
temp = current;
current = current->next;
free(temp);
}
free(stack);
}
使用示例
下面是链表栈的简单使用测试代码：
int main() {
// 初始化链表栈
LinkedStack* stack = linked_stack_init();
if (stack == NULL) {
printf("栈初始化失败n");
return 1;
}
// 入栈测试
for (int i = 1; i <= 5; i++) {
if (linked_stack_push(stack, i)) {
printf("入栈元素：%dn", i);
}
}
// 获取栈顶元素
StackData top_val;
if (linked_stack_peek(stack, &top_val)) {
printf("当前栈顶元素：%dn", top_val);
}
// 出栈测试
StackData pop_val;
while (!linked_stack_is_empty(stack)) {
if (linked_stack_pop(stack, &pop_val)) {
printf("出栈元素：%dn", pop_val);
}
}
// 销毁栈
linked_stack_destroy(stack);
return 0;
}
两种实现方式对比
我们从多个维度对比数组栈和链表栈的特点，方便开发者选择合适的实现方案：
| 对比维度 | 数组实现 | 链表实现 |
|---|---|---|
| 内存分配 | 预先分配连续内存，容量固定，扩容需要重新分配内存并拷贝数据 | 动态分配离散内存，容量无上限，不需要预先指定大小 |
| 内存开销 | 仅存储元素本身，无额外指针开销 | 每个节点需要额外存储一个指针，内存开销更大 |
| 访问效率 | 栈顶元素通过索引直接访问，时间复杂度O(1) | 栈顶元素直接通过指针访问，时间复杂度O(1) |
| 入栈出栈效率 | 不涉及内存分配释放时O(1)，扩容时O(n) | 每次入栈出栈都需要分配或释放节点内存，效率略低 |
| 适用场景 | 栈容量可预估、对访问速度要求高的场景 | 栈容量不确定、需要动态扩展的场景 |
总结
在C语言中实现栈结构，数组和链表是两种最基础的实现方式。如果开发中能明确栈的最大容量，且对性能要求较高，优先选择数组实现；如果栈的容量无法提前确定，需要灵活扩展，链表实现会更合适。实际开发中可以根据具体需求选择对应的实现方案，也可以基于这两种基础实现做进一步优化，比如给数组栈添加动态扩容逻辑，结合二者的优势。掌握这两种实现方式，也能帮助开发者更深入理解栈的特性以及C语言中内存管理的相关知识点。