一、概念
1.定义：栈是一种特殊的线性表，它只允许在固定的一端进行插入和删除元素操作。其中进行数据插入和删除操作的一端叫做栈顶，另一端叫做栈底。
栈中数据元素遵守后进先出的原则。
2.栈的实现：栈的实现一般可以使用数组或链表实现，但链表实现较为复杂一般不考虑，相对而言数组的结构实现就更优一些，因为数组在尾上插入数据的代价较小。
3.栈的应用场景：（1）可借助栈修改元素序列次序；（2）可借助栈解决括号匹配问题。
二、结构体定义
// 支持动态增长的栈 typedef int STDataType; typedef struct Stack { STDataType* array; int top; // 栈顶 int capacity; // 容量 }Stack;
三、接口实现
考虑到实用性，这里实现的是空间可动态增长的栈及其基本操作。
void StackInit(Stack* ps, int capacity);// 初始化栈 void StackPush(Stack* ps, STDataType data);// 入栈 void StackPop(Stack* ps);// 出栈 STDataType StackTop(Stack* ps);// 获取栈顶元素 int StackSize(Stack* ps);// 获取栈中有效元素个数 int StackEmpty(Stack* ps);// 检测栈是否为空，为空返回1，非空返回0 void StackDestroy(Stack* ps);// 销毁栈 void Stack_Test();//功能测试函数
1.栈的初始化
// 初始化栈 void StackInit(Stack* ps, int capacity) { assert(ps); if (capacity < 3) {//初始化容量为3 capacity = 3; } ps->array = (STDataType*)malloc(sizeof(STDataType) * capacity); if (ps->array == NULL) {//申请失败 assert(0); return; } ps->capacity = capacity; ps->top = 0; }
2.栈的判满&扩容
void StackCheckCapacity(Stack* ps) {//判满&扩容 assert(ps); if (ps->top == ps->capacity) {//栈满 int newCapacity = ps->capacity * 2;//每次扩容扩大两倍 STDataType* temp = (STDataType*)malloc(sizeof(STDataType) * newCapacity);//开辟新空间 memcpy(temp, ps->array, sizeof(STDataType) * ps->capacity);//将元数据拷贝到新空间中 free(ps->array);//释放旧空间，使用新空间 ps->array = temp; ps->capacity = newCapacity; } }
3.入栈
void StackPush(Stack* ps, STDataType data) {//入栈 StackCheckCapacity(ps);//判断是否栈满，栈满则扩容 ps->array[ps->top] = data; ps->top++; }
4.栈判空
int StackEmpty(Stack* ps) {//栈判空 assert(ps); return 0 == ps->top;//空返回1，非空返回0 }
5.出栈
void StackPop(Stack* ps) {//出栈 if (StackEmpty(ps)) {//判空 return; } ps->top--; }
6.获取栈顶元素
STDataType StackTop(Stack* ps) {//获取栈顶元素 assert(ps); return ps->array[ps->top - 1]; }
7.获取栈中有效元素个数
int StackSize(Stack* ps) {//获取栈中有效元素个数 assert(ps); return ps->top; }
8.栈销毁
void StackDestroy(Stack* ps) {//栈销毁 assert(ps); if (ps->array) { free(ps->array); ps->capacity = 0; ps->top = 1; } }
四、功能测试
1.测试函数
void Stack_Test() {//功能测试函数 Stack s; StackInit(&s, 3); StackPush(&s, 1); StackPush(&s, 2); StackPush(&s, 3); printf(" size = %d\n", StackSize(&s)); printf(" top = %d\n", StackTop(&s)); StackPush(&s, 4); // 扩容 StackPush(&s, 5); StackPush(&s, 6); StackPush(&s, 7); // 扩容 printf("\n size = %d\n", StackSize(&s)); printf(" top = %d\n", StackTop(&s)); StackPop(&s); StackPop(&s); StackPop(&s); printf("\n size = %d\n", StackSize(&s)); printf(" top = %d\n", StackTop(&s)); StackDestroy(&s);//销毁 }
2.测试结果
五、完整代码
#include<stdio.h> #include<assert.h> #include<string.h> #include<malloc.h> // 支持动态增长的栈 typedef int STDataType; typedef struct Stack { STDataType* array; int top; // 栈顶 int capacity; // 容量 }Stack; void StackInit(Stack* ps, int capacity);// 初始化栈 void StackCheckCapacity(Stack* ps);//判满&扩容 void StackPush(Stack* ps, STDataType data);// 入栈 void StackPop(Stack* ps);// 出栈 STDataType StackTop(Stack* ps);// 获取栈顶元素 int StackSize(Stack* ps);// 获取栈中有效元素个数 int StackEmpty(Stack* ps);// 检测栈是否为空，为空返回1，非空返回0 void StackDestroy(Stack* ps);// 销毁栈 void Stack_Test();//功能测试函数 int main() { Stack_Test();//功能测试函数 return 0; } // 初始化栈 void StackInit(Stack* ps, int capacity) { assert(ps); if (capacity < 3) {//初始化容量为3 capacity = 3; } ps->array = (STDataType*)malloc(sizeof(STDataType) * capacity); if (ps->array == NULL) {//申请失败 assert(0); return; } ps->capacity = capacity; ps->top = 0; } void StackCheckCapacity(Stack* ps) {//判满&扩容 assert(ps); if (ps->top == ps->capacity) {//栈满 int newCapacity = ps->capacity * 2;//每次扩容扩大两倍 STDataType* temp = (STDataType*)malloc(sizeof(STDataType) * newCapacity);//开辟新空间 memcpy(temp, ps->array, sizeof(STDataType) * ps->capacity);//将元数据拷贝到新空间中 free(ps->array);//释放旧空间，使用新空间 ps->array = temp; ps->capacity = newCapacity; } } void StackPush(Stack* ps, STDataType data) {//入栈 StackCheckCapacity(ps);//判断是否栈满，栈满则扩容 ps->array[ps->top] = data; ps->top++; } int StackEmpty(Stack* ps) {//栈判空 assert(ps); return 0 == ps->top;//空返回1，非空返回0 } void StackPop(Stack* ps) {//出栈 if (StackEmpty(ps)) {//判空 return; } ps->top--; } STDataType StackTop(Stack* ps) {//获取栈顶元素 assert(ps); return ps->array[ps->top - 1]; } int StackSize(Stack* ps) {//获取栈中有效元素个数 assert(ps); return ps->top; } void StackDestroy(Stack* ps) {//栈销毁 assert(ps); if (ps->array) { free(ps->array); ps->capacity = 0; ps->top = 1; } } void Stack_Test() {//功能测试函数 Stack s; StackInit(&s, 3); StackPush(&s, 1); StackPush(&s, 2); StackPush(&s, 3); printf(" size = %d\n", StackSize(&s)); printf(" top = %d\n", StackTop(&s)); StackPush(&s, 4); // 扩容 StackPush(&s, 5); StackPush(&s, 6); StackPush(&s, 7); // 扩容 printf("\n size = %d\n", StackSize(&s)); printf(" top = %d\n", StackTop(&s)); StackPop(&s); StackPop(&s); StackPop(&s); printf("\n size = %d\n", StackSize(&s)); printf(" top = %d\n", StackTop(&s)); StackDestroy(&s);//销毁 }
