网站建设 自适应,专业开发小程序公司,比亚迪新能源汽车车型,动漫网页设计作业文章目录 Ⅰ 概念及结构1. 栈的概念2. 栈的操作 Ⅱ 基本操作实现1. 栈的定义2. 初始化栈3. 元素入栈4. 元素出栈5. 获取栈顶元素6. 获取栈中有效元素个数7. 判断栈空8. 销毁栈 Ⅰ 概念及结构
1. 栈的概念
栈#xff1a;栈是一种特殊的线性表#xff0c;其只允许在固定的一端… 文章目录 Ⅰ 概念及结构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. 获取栈中有效元素个数
因为栈顶指针实际表示的是数组下标所以栈中有效数据的个数为 top1。
// 获取栈中有效元素个数
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;
}
