1. 栈的概念
栈是一种特殊的线性表,只允许在固定一端插入和删除操作,进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守先进后出(LIFO, Last In First Out)的原则。
- 压栈:栈的插入操作叫做进栈(压栈、入栈),数据在栈顶。
- 出栈:栈的删除操作叫做出栈,数据也在栈顶。
2. 栈的底层结构选择
实现栈时,可以选择顺序表或链表作为底层结构。
- 数组实现:插入元素时在指定位置操作,删除元素时移动 top 指针。缺点是可能存在空间浪费。
- 链表实现:按需申请和释放空间,无空间浪费。但每次插入或删除都需要遍历链表,时间复杂度为 O(N)。
综合来看,采用数组结构实现栈更为合适,解决了动态扩容问题后效率更高。
3. 栈的实现
3.1 栈的定义
typedef int SDataType;
typedef struct Stack {
SDataType* a; // 栈底指针
int capacity; // 栈的容量大小
int top; // 栈实际存储数据的个数
} Stack;
3.2 栈的接口
// 初始化栈
void StackInit(Stack* ps);
// 栈顶入数据
void StackPush(Stack* ps, SDataType x);
// 获取栈顶元素
SDataType StackTop(Stack* ps);
// 删除栈顶数据
void StackPop(Stack* ps);
// 栈是否为空
bool StackEmpty(Stack* ps);
// 栈的大小
int StackSize(Stack* ps);
// 销毁栈
void ;


