上海静安网站建设,人设生成器网站,长沙网站制作案例,页面设计图标本文属于数据结构专栏文章#xff0c;适合数据结构入门者学习#xff0c;涵盖数据结构基础的知识和内容体系#xff0c;文章在介绍数据结构时会配合上动图演示#xff0c;方便初学者在学习数据结构时理解和学习#xff0c;了解数据结构系列专栏点击下方链接。 博客主页适合数据结构入门者学习涵盖数据结构基础的知识和内容体系文章在介绍数据结构时会配合上动图演示方便初学者在学习数据结构时理解和学习了解数据结构系列专栏点击下方链接。 博客主页Duck Bro 博客主页 系列专栏数据结构专栏 关注博主后期持续更新系列文章 如果有错误请大家批评指出博主会及时修改 感谢大家点赞收藏⭐评论✍ 数据结构入门 — 栈
本文关键字栈、概念及结构、动图、接口实现 文章目录 数据结构入门 — 栈一、 栈的概念及结构1. 栈的概念2. 栈的结构 二、栈的实现1. 动态增长栈结构2. 初始化栈3. 入栈4. 出栈5. 获取栈顶元素6. 获取栈中有效元素个数7. 检测栈是否为空8. 销毁栈 一、 栈的概念及结构
1. 栈的概念
栈Stack是一种特殊的线性数据结构它的特点是仅允许在一端进行插入和删除操作。这一端被称为栈顶Top另一端称为栈底Bottom。栈的操作模式为后进先出Last In First OutLIFO是一种简单的“先进后出”的顺序结构。
栈通常可以用数组或链表实现常用的操作包括入栈Push和出栈Pop。入栈操作是将新的元素插入到栈顶出栈操作是将栈顶的元素删除并返回。此外栈还有一些其他的操作如获取栈顶元素Top、判断栈是否为空IsEmpty等。往栈中插入元素的操作叫做push从栈中删除元素的操作叫做pop查看栈顶元素的操作叫做top。
2. 栈的结构
栈结构可以用数组或链表实现 数组实现栈栈底用数组下标为0的位置栈顶用数组下标为n-1的位置n为数组长度。入栈操作就是将元素插入到数组末尾出栈操作就是将数组末尾元素删除并返回。由于数组有固定的大小因此当栈满时就无法再插入元素这种情况称为栈溢出。 链表实现栈链表中的每个节点保存一个元素和一个指向下一个节点的指针。栈顶指针指向链表的头部入栈操作就是将新元素插入到链表头部出栈操作就是将链表头部元素删除并返回。由于链表的大小能够动态地调整因此它即使在没有预留额外空间的情况下也能灵活地添加或删除元素。 在实现栈时还需要考虑一些细节问题比如空栈的情况如何判断栈满或栈空等。 二、栈的实现
1. 动态增长栈结构
使用动态增长的结构top为栈内元素个数、capacity表示栈内的容量
typedef int STDatatype;typedef struct StackList
{STDatatype* a;int top;int capacity;
}STL;2. 初始化栈
初始化先将指针a置为空top、capacity置为0
void STInit(STL* pc)
{assert(pc);pc-a NULL;pc-top 0;pc-capacity 0;
}3. 入栈
这里使用realloc函数的特性当指针为空时跟malloc函数的效果相同入栈即尾插
void STPush(STL* pc, STDatatype x)
{assert(pc);if (pc-capacity pc-top){int newcapacity pc-capacity 0 ? 4 : pc-capacity * 2;STDatatype* temp (STDatatype*)realloc(pc-a, sizeof(STDatatype) * newcapacity);if (temp NULL){perror(realloc fail);exit(-1);}pc-a temp;pc-capacity newcapacity;}pc-a[pc-top] x;pc-top;
}4. 出栈
这里的出栈即尾删
void STPop(STL* pc)
{assert(pc);assert(pc-top 0);--pc-top;
}5. 获取栈顶元素
top指向栈顶的后一个获取栈顶元素时要将top减1
STDatatype STTop(STL* pc)
{assert(pc);assert(pc-top 0);return pc-a[pc-top - 1];
}6. 获取栈中有效元素个数
top中记录了栈内的元素个数直接返回top即可
int STSize(STL* pc)
{assert(pc);return pc-top;
}7. 检测栈是否为空
如果栈内为空则top为0就是栈是空的
bool STEmpty(STL* pc)
{assert(pc);return pc-top 0;
}8. 销毁栈
释放a内的内存。将top\capacity置为0
void STDestroy(STL* pc)
{assert(pc);free(pc-a);pc-a NULL;pc-top pc-capacity 0;
}
