视频网站开发前景,手机模板网站生成制作软件,海外网站怎么浏览,做家旅游的视频网站好个人主页#xff1a;17_Kevin-CSDN博客 专栏#xff1a;《数据结构》 一、栈的概念 栈#xff08;Stack#xff09;是一种特殊的线性表#xff0c;它遵循后进先出#xff08;Last-In-First-Out#xff0c;LIFO#xff09;的原则。栈可以被看作是一个只能在一端进行操作… 个人主页17_Kevin-CSDN博客 专栏《数据结构》 一、栈的概念 栈Stack是一种特殊的线性表它遵循后进先出Last-In-First-OutLIFO的原则。栈可以被看作是一个只能在一端进行操作的线性表进行数据插入和删除操作的一端称为栈顶另一端称为栈底它的基本操作包括入栈Push和出栈Pop。 栈可以想象成一个垂直放置的木板上面有一些盘子。栈的特点是最后放入的盘子会被放在最上面而要取出盘子时只能从最上面开始取。这就是后进先出的原则也就是说最后放入栈的元素会首先被取出。 二、栈的结构 栈的大致结构如上只能从固定的端口栈顶压栈和出栈。 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。 出栈栈的删除操作叫做出栈。出数据也在栈顶。 三、栈的代码实现 以C语言作为语言基础数组作为储存结构实现栈的压栈出栈等操作 为什么使用数组实现栈 原因如下 随机访问数组可以通过索引快速地访问任何元素而链表需要遍历才能找到指定的元素。在栈的操作中我们通常只关心栈顶元素因此数组的随机访问特性可以提供更好的性能。内存效率数组在内存中是连续存储的而链表中的每个节点都需要额外的指针空间。对于栈来说数组的内存效率更高因为它不需要额外的指针来维护栈的结构。常数时间操作数组的入栈和出栈操作可以在常数时间内完成因为它们只需要修改栈顶指针。而链表的入栈和出栈操作需要遍历链表因此时间复杂度为 O(n)。 栈的创建
typedef int STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST; 栈的初始化
void STInit(ST* ps)
{assert(ps);ps-a NULL;ps-top 0;ps-capacity 0;
} 栈的销毁
void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity 0;
} 压栈和出栈 压栈
void STPush(ST* ps, STDataType x)
{assert(ps);// 如果空间不够扩容if (ps-top ps-capacity){int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp (STDataType*)realloc(ps-a, newcapacity * sizeof(STDataType));if (tmp NULL){perror(realloc fail);return;}ps-a tmp;ps-capacity newcapacity;}ps-a[ps-top] x;ps-top;
} 我们用数组来实现栈用指针指向的区域扩容来表示数组往进存结构体。当 ps-top ps-capacity 的时候说明数组内的空间满了不足以进行压栈所以进行if内的扩容处理。
在数组容量足够的时候直接在对应的top位置上进行赋值实现压栈最终用top来实现数据的同步刷新。 出栈
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps-top--;
}
出栈的处理简单粗暴。
我们将 top-- 后其实就无法修改和读取之前top - 1位置的值了而在压栈的时候他是对top位置的空间直接赋值所以不用担心之前的该位置存的值是多少。 读取栈顶
STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps-a[ps-top - 1];
} 栈内数据数量
int STSize(ST* ps)
{assert(ps);return ps-top;
} 四、栈的应用 栈在编程中有很多应用例如 函数调用在函数调用中栈用于保存函数的参数、局部变量和返回地址。表达式求值在表达式求值中栈用于按照运算符的优先级和结合性对表达式进行求值。括号匹配在处理括号嵌套的代码时栈可以用于检查括号是否匹配。递归在递归算法中栈用于保存函数的调用信息和返回地址。 五、总结 栈是一种重要的数据结构它遵循后进先出的原则。栈的基本操作包括入栈、出栈、查看栈顶元素和检查栈是否为空。栈可以使用数组或链表来实现并且在编程中有很多应用。希望这篇博客对你理解栈有所帮助
