栈的定义与特性
栈(Stack):一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出(LIFO, Last In First Out)的原则。
注意:本文讨论的是数据结构中的栈,而非操作系统中的栈,二者概念不同。
1. 后进先出(LIFO)
后进先出,即先进去的数据后出来,而后进去的数据先出来。如同枪上的弹夹,先压进去的子弹后打出去,后压进去的子弹先打出去。

2. 压栈与出栈
- 压栈:栈的插入操作叫做进栈、压栈或入栈,入数据在栈顶。
- 出栈:栈的删除操作叫做出栈,出数据也在栈顶。
栈的实现思路
1. 实现方式
栈的实现一般可以使用数组或者链表实现。相对而言,数组的结构实现更优一些。因为栈只允许在固定的一端进行插入和删除元素操作,而在数组中避免了中间数据的插入与删除,尾插尾删的代价较小。
2. 成员定义
与顺序表同理,栈的实现应该有三名成员:
- 指向一个数组的指针
- 栈内的总元素个数
- 栈内的总容量
3. 注意事项
栈只允许在固定的一端进行插入和删除元素操作。不能在两端同时进行操作,必须遵循先进后出的基本原则。因此,在插入数据时选择尾插,而在取出数据时,选择头取(实际上是修改 size 下标)。
代码实现
本文以创建一个 int 类型的栈为例。
1. 文件结构
- Stack.h:存放函数声明和库函数头文件。
- Stack.c:存放函数定义(栈的主体)。
- Test.c:测试实现的栈的运行效果。
2. 定义栈
在头文件 Stack.h 中定义:
// 重定义,方便修改类型
typedef int STDataType;
// 定义栈
typedef struct Stack {
STDataType* a; // 数组指针
int size; // 总元素
int capacity; // 容量
} Stack;
3. 初始化栈
内容全部置 NULL / 0。


