【数据结构初阶（4）】栈的基本操作实现
文章目录
- Ⅰ 概念及结构
- 1. 栈的概念
- 2. 栈的操作
- Ⅱ 基本操作实现
- 1. 栈的定义
- 2. 初始化栈
- 3. 元素入栈
- 4. 元素出栈
- 5. 获取栈顶元素
- 6. 获取栈中有效元素个数
- 7. 判断栈空
- 8. 销毁栈
Ⅰ 概念及结构
1. 栈的概念
- 栈：栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。
- 栈顶和栈底：进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出的原则
- 空栈：不含任何元素的栈
2. 栈的操作
- 入栈：在栈顶插入数据称为入栈 (压栈 / 进栈)，入数据在栈顶。
- 出栈：在栈顶删除数据称为出栈 (弹栈)，出数据在栈顶。
Ⅱ 基本操作实现
1. 栈的定义
- 栈一般用数组或链表来实现，使用数组栈在入栈上会更轻松，因此本文使用的为数组栈 (顺序栈)。
代码实现
// 支持动态增长的栈
typedef int STDataType;typedef struct stack
{STDataType* data; //栈空间int top; //栈顶int capacity; //容量
}stack;
2. 初始化栈
实现方法
先将栈空间置空，栈顶置为 -1，栈空间容量置为 0。
- 栈顶置为 -1，表示指向当前元素。因为本文使用的为数组栈，栈顶实际上是最后一个元素的下标，如果栈顶初始化为 0 的话，就没法很好的表示栈内是没有元素还是只有一个元素。
代码实现
// 初始化栈
void StackInit(stack* ps)
{assert(ps);ps->data = NULL; //栈空间置空ps->top = -1; //栈顶ps->capacity = 0;
}
3. 元素入栈
- 栈顶指针 top 指向的是当前的元素，在插入新元素时需要先将栈顶指针 + 1，指向栈顶之上。
代码实现
// 入栈
void StackPush(stack* ps, STDataType data)
{assert(ps);if (ps->top + 1 == ps->capacity) //检查栈空间是否需要扩容{int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * newcapacity);if (NULL == tmp){perror("realloc");exit(-1);}ps->data = tmp;ps->capacity = newcapacity;}ps->top++; //栈顶指针指向栈顶之上ps->data[ps->top] = data; //元素入栈
}
4. 元素出栈
- 若栈不为空，则直接将栈顶指针 - 1 即可，只有在栈顶指针维护下的元素才是有效数据。
// 出栈
void StackPop(stack* ps)
{assert(ps);assert(ps->top > -1); //栈不为空ps->top--; //栈顶指针 - 1
}
5. 获取栈顶元素
- 若栈不为空，则直接返回栈顶指针指向的那块空间的数据即可。
// 获取栈顶元素
STDataType StackTop(stack* ps)
{assert(ps);assert(ps->top > -1); //栈不为空return ps->data[ps->top]; //返回栈顶元素
}
6. 获取栈中有效元素个数
- 因为栈顶指针实际表示的是数组下标，所以栈中有效数据的个数为 top+1。
// 获取栈中有效元素个数
int StackSize(stack* ps)
{assert(ps);return ps->top + 1;
}
7. 判断栈空
- 在初始化栈时将栈顶指针初始化为 -1表示栈空，可以直接用 -1 是否等于 top 来判断是否栈空。
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(stack* ps)
{assert(ps);return -1 == ps->top;
}
8. 销毁栈
// 销毁栈
void StackDestroy(stack* ps)
{assert(ps);free(ps->data); //释放栈空间ps->data = NULL;ps->top = ps->capacity = 0;
}