栈是计算机科学中最基础且重要的数据结构之一，它遵循"后进先出"（LIFO）的原则。想象一下一叠盘子，你只能从最上面取放，这就是栈的直观体现。本文将用C语言带你一步步实现一个顺序栈，即使你是编程小白也能轻松理解！

什么是顺序栈？

顺序栈是使用数组实现的栈结构，具有以下特点：

• 元素在内存中连续存储

• 有一个指针(top)始终指向栈顶位置

• 支持基本的入栈(push)和出栈(pop)操作

代码实现详解

1. 头文件定义(Stack.h)

首先我们需要定义栈的结构和声明相关操作函数：

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>// 定义栈中元素的数据类型
typedef int STDataType;// 栈的结构定义
typedef struct Stack
{STDataType* _a;    // 指向动态数组的指针int _top;          // 栈顶位置int _capacity;     // 当前容量
}Stack;// 函数声明
void StackInit(Stack* ps);                 // 初始化栈
void StackPush(Stack* ps, STDataType data);// 入栈
void StackPop(Stack* ps);                  // 出栈
STDataType StackTop(Stack* ps);            // 获取栈顶元素
int StackSize(Stack* ps);                  // 获取元素个数
int StackEmpty(Stack* ps);                 // 检查栈是否为空
void StackDestroy(Stack* ps);              // 销毁栈

2. 栈的实现(Stack.c)

初始化栈

void StackInit(Stack* ps) {assert(ps);  // 确保指针有效ps->_a = NULL;ps->_top = 0;      // 栈顶指向下一个空闲位置ps->_capacity = 0; // 初始容量为0
}

初始化时，我们将数组指针设为NULL，栈顶位置和容量都设为0。

入栈操作

void StackPush(Stack* ps, STDataType data) {assert(ps);// 检查栈是否已满，需要扩容if (ps->_capacity == ps->_top) {// 如果容量为0，初始分配4个元素空间，否则容量翻倍int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;// 重新分配内存STDataType* tmp = (STDataType*)realloc(ps->_a, sizeof(STDataType) * newcapacity);if (tmp == NULL) {perror("malloc error");return;}ps->_capacity = newcapacity;ps->_a = tmp;}// 将数据放入栈顶并更新栈顶位置ps->_a[ps->_top++] = data;
}

这里使用了动态内存分配，当栈满时自动扩容，这是实现可变大小栈的关键。

出栈操作

void StackPop(Stack* ps) {assert(ps);assert(ps->_top > 0); // 确保栈不为空ps->_top--; // 简单地将栈顶指针下移
}

出栈操作实际上只是移动栈顶指针，并不真正删除数据。

其他辅助函数

// 获取栈顶元素
STDataType StackTop(Stack* ps) {assert(ps);assert(ps->_top > 0); // 确保栈不为空return ps->_a[ps->_top - 1]; // 返回栈顶元素
}// 获取栈中元素个数
int StackSize(Stack* ps) {assert(ps);return ps->_top; // 栈顶位置就是元素个数
}// 检查栈是否为空
int StackEmpty(Stack* ps) {assert(ps);return ps->_top == 0; // 如果栈顶为0，栈为空
}// 销毁栈，释放内存
void StackDestroy(Stack* ps) {free(ps->_a);        // 释放数组内存ps->_a = NULL;       // 指针置空防止野指针ps->_top = 0;        // 重置栈顶ps->_capacity = 0;   // 重置容量
}

3. 测试代码(test.c)

#include "Stack.h"void TestStack(Stack* p) {// 测试初始化StackInit(p);// 测试入栈 - 添加6个元素StackPush(p, 1);StackPush(p, 2);StackPush(p, 3);StackPush(p, 4);StackPush(p, 5);StackPush(p, 6);// 测试栈是否为空且查看栈顶元素if (!StackEmpty(p))printf("栈顶元素: %d \n", StackTop(p));else printf("栈为空\n");// 测试出栈 - 弹出5个元素StackPop(p);StackPop(p);StackPop(p);StackPop(p);StackPop(p);// 测试栈元素个数printf("栈中元素个数: %d \n", StackSize(p));// 销毁栈StackDestroy(p);
}int main() {Stack p;TestStack(&p);return 0;
}

运行结果分析

运行测试代码，你会看到以下输出：

栈顶元素: 6
栈中元素个数: 1

这是因为我们依次压入了1-6六个数字，然后弹出了五个，最后只剩下一个元素。

关键点解析

1. 动态扩容：当栈满时，我们通过realloc函数将容量翻倍，这是常见的扩容策略

2. 栈顶指针：_top指向的是下一个空闲位置，而不是当前栈顶元素的位置

3. 断言使用：使用assert确保函数参数的有效性，提高代码健壮性

4. 内存管理：记得在不再使用栈时调用StackDestroy释放内存，防止内存泄漏

常见问题

1. Q: 为什么出栈操作不真正删除数据？
   A: 只需要移动栈顶指针，下次入栈时会覆盖该位置，提高效率

2. Q: 初始容量为什么设为4？
   A: 这是一个经验值，太小会导致频繁扩容，太大浪费内存

3. Q: 如何修改栈中存储的数据类型？
   A: 只需修改Stack.h中的STDataType定义即可