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 StackDestroy(Stack* ps);
3.2.1 初始化栈
void StackInit(Stack* ps) {
assert(ps);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
3.2.2 栈顶入数据
void StackPush(Stack* ps, SDataType x) {
assert(ps);
// 增容
if (ps->capacity == ps->top) {
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SDataType* tmp = (SDataType*)realloc(ps->a, sizeof(SDataType) * newcapacity);
if (tmp == NULL) {
printf("StackPush(): realloc fail\n");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
首先判断栈空间是否足够，不够则扩容。空间足够直接在 top 位置插入数据并更新计数。初始容量为 0 时设置为 4，否则翻倍。
3.2.3 栈是否为空
bool StackEmpty(Stack* ps) {
assert(ps);
return ps->top == 0;
}
top 记录栈中数据元素的个数，top 为 0 表示栈为空。
3.2.4 获取栈顶元素
SDataType StackTop(Stack* ps) {
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}
保证栈不为空，直接返回数组最后一个元素。
3.2.5 删除栈顶元素
void StackPop(Stack* ps) {
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
栈不为空才能删除数据，直接减小 top 即可。
3.2.6 栈的大小
int StackSize(Stack* ps) {
assert(ps);
return ps->top;
}
直接返回 top 值。
3.2.7 销毁栈
void StackDestroy(Stack* ps) {
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
释放动态申请的数组空间，并将成员变量重置。
4. 完整代码实现
Stack.h
#pragma once
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <assert.h>
typedef int SDataType;
typedef struct Stack {
SDataType* a;
int capacity;
int top;
} Stack;
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 StackDestroy(Stack* ps);
Stack.c
#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"
void StackInit(Stack* ps) {
assert(ps);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
void StackPush(Stack* ps, SDataType x) {
assert(ps);
if (ps->capacity == ps->top) {
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SDataType* tmp = (SDataType*)realloc(ps->a, sizeof(SDataType) * newcapacity);
if (tmp == NULL) {
printf("StackPush(): realloc fail\n");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
SDataType StackTop(Stack* ps) {
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}
void StackPop(Stack* ps) {
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
bool StackEmpty(Stack* ps) {
assert(ps);
return ps->top == 0;
}
int StackSize(Stack* ps) {
assert(ps);
return ps->top;
}
void StackDestroy(Stack* ps) {
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
test.c
#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"
void TestStack1() {
Stack st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
StackPush(&st, 5);
SDataType ret = StackTop(&st);
printf("%d ", ret);
StackPop(&st);
StackPop(&st);
int size = StackSize(&st);
printf("%d ", size);
StackDestroy(&st);
}
int main() {
TestStack1();
return 0;
}