万网icp网站备案专题,山东网站建设价格,网站建设考察报告,做网站每年要交不费用吗一、栈的基本概念1、栈的定义2、栈的常见基本操作 二、栈的顺序存储1、栈的顺序存储结构2、顺序栈存储实现#xff08;1#xff09;初始化#xff08;2#xff09;判空#xff08;3#xff09;进栈#xff08;4#xff09;出栈#xff08;5#xff09;取栈顶元素1初始化2判空3进栈4出栈5取栈顶元素6获取元素个数7销毁 三、栈的链式存储1、栈的链式存储结构2、链式栈存储实现1初始化2判空3进栈4出栈5取栈顶元素6 获取元素个数7销毁 四、性能分析 一、栈的基本概念
1、栈的定义
栈stack一种特殊的线性表主要特性是后进先出Last In First Out其只允许在固定的一段进行插入和删除元素操作。进行数据插入和删除操作的一段称为栈顶另一端称为栈底。 进栈栈的插入操作叫左进栈/压栈/入栈入数据在栈顶。出栈栈的删除操作叫做出栈。出数据也在栈顶。栈顶Top线性表允许进行插入删除的那一端。栈底Bottom固定的不允许进行插入和删除的另一端。空栈不含任何元素的空表。 2、栈的常见基本操作
void STInit(ST* ps);//初始化一个空栈S。
void STDestroy(ST* ps);//栈销毁释放其占用的存储空间//从栈顶操作
void STPush(ST* ps, STDateType x);//进栈栈的插入操作若栈未满插入使x成为新栈顶
void STPop(ST* ps);//出栈栈的删除操作若栈非空弹出栈顶元素
STDateType STTop(ST* ps);//返回栈顶元素
int STSize(ST* ps);//返回栈中有效元素个数(top记录有效个数)bool STEmpty(ST* ps);//判断栈是否为空top是否指向0栈主要有两种存储方式来实现一是顺序存储结构数组二是链式存储结构链表
二、栈的顺序存储
栈的顺序存储结构通常由数组和一个记录栈顶元素的下一个位置的变量(下一个入栈的数据插入的位置)组成但是当数组空间大小不够时还需要扩容所以还要存储栈的空间大小的变量。 可以参考我写的另一篇博客理解——顺序表
1、栈的顺序存储结构
采用顺序(数组)存储的栈称为顺序栈它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素同时附设一个指针top指示当前栈顶元素的位置一个整形capacity用于扩容实现动态栈。
typedef int STDateType;//STDateType的类型根据实际情况而定
typedef struct Stack
{STDateType* a;int top;//指向栈顶下一个位置的指针-方便进栈/出栈/判空等操作int capacity;//空间大小-用于动态扩容
}ST;2、顺序栈存储实现
1初始化
用一级指针接收栈的地址将栈的存储空间即a这个动态分配内存的数组置为NULL,表示当前没有分配任何内存将top和capacity置为0来表示栈的起始状态无元素插入和无内存分配。
void STInit(ST* ps)
{assert(ps);//断言确保传入的指针 ps 不为空以避免对无效指针的操作ps-a NULL;ps-top 0;//指向栈顶元素下一个位置ps-capacity 0;
}2判空
判断头指针的下一个位置是否指向0即可如果指向0说明栈为空无元素插入否则说什么栈不为空已有元素插入
bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;//为真返回1说明栈为空否则返回0说明栈不为空
}3进栈
判断是否需要扩容如果栈中有效元素top指向的位置和栈空间大小相同ps-top ps-capacity则需要扩容否则无需扩容。 扩容使用三目运算符如果capactiy是0则置空间大小为4否则空间大小翻倍。随后使用realloc动态内存分配出新空间给临时数组tmp最后更新a数组和空间。将x元素放入a数组有效元素加1。
void STPush(ST* ps, STDateType x)
{assert(ps);//满了扩容if (ps-top ps-capacity){int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDateType* tmp (STDateType*)realloc(ps-a, newcapacity * sizeof(STDateType));//STDateType* tmp ps;if (tmp NULL){perror(realloc fail);return;}ps-a tmp;ps-capacity newcapacity;}//top始终指向栈顶元素//动态内存分配包含 N 个 STDateType 类型元素的内存块可以像数组一样使用。ps-a[ps-top] x;ps-top;
}注意当ps-a为NULL,realloc和malloc作用相同。 realloc(ptr, size)用于调整 ptr 指向的内存块的大小为 size。如果 ptr 是非空的它会尝试在原有内存块上重新分配内存。如果 ptr 为空realloc() 就相当于 malloc(size)即分配一个新的内存块。malloc(size)用于分配一个大小为 size 的内存块并返回指向这块内存的指针。 4出栈
判断栈是否为空如果为空无法出栈top指针-1
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));//调用前面的判空操作ps-top--;
}5取栈顶元素
判断栈是否为空如果为空无法取栈顶元素返回栈顶元素 (top-1 即为栈顶元素的位置)
STDateType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps-a[ps-top - 1];
}6获取元素个数
top的下标即为栈中有效元素的个数直接返回即可
int STSize(ST* ps)
{assert(ps);return ps-top;
}7销毁
释放栈占用的存储空间置栈顶指针top和栈的空间大小置为0即可。
void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity 0;
}三、栈的链式存储
链式存储的栈称为链栈通常采用单链表实现。由于栈是链式存储每次插入时需要申请一个新节点因此我们定义一个结构体存放指向头节点的指针和记录有效元素个数的整形size。再定义一个结构体存放节点的数据和指向下一个节点的指针。 链表具体实现过程可以参考这篇博客——单链表
1、栈的链式存储结构
定义两个结构体
StackNode 存放节点的数据STDataType data; 存放当前节点的下一个节点struct StackNode* next;ST保存栈顶元素StackNode* top; 记录有效数据个数int size;
typedef int STDataType;//STDateType的类型根据实际情况而定
typedef struct StackNode {STDataType data;//当前节点的数据struct StackNode* next;//当前节点的下一个节点的指针
}StackNode;
typedef struct Stack {StackNode* top;//栈顶int size;//有效数据的个数
}ST;2、链式栈存储实现
1初始化
用一级指针接收ST结构体的地址对ST结构体中保存的头结点悬空NULL有效元素个数初始化为0即可
void STInit(ST* ps)
{assert(ps);//ps!NULLps-top NULL;ps-size 0;
}2判空
用一级指针接收ST结构体的地址判断ST结构体中保存的头节点是否为NULL即可
bool StackEmpty(ST* ps)
{assert(ps);//ps!NULLreturn ps-top NULL;
}3进栈
判断栈是否为空如果为空直接将数据给头节点即可否则需要修改指针连接并更新头节点
void StackPush(ST* ps, STDataType x)
{assert(ps);//申请一个新节点StackNode* newnode (StackNode*)malloc(sizeof(StackNode));if (newnode NULL){perror(malloc fail!);exit(1);}newnode-data x;if (StackEmpty(ps)){//如果栈为空将新节点newnode赋给栈顶ps-top newnode;ps-top-next NULL;}else{//如果栈不为空更新栈顶指针并修改指针连接newnode-next ps-top;ps-top newnode;}//有效数据1ps-size;
}4出栈
判空出栈需要栈中有元素因此第一步断言判空assert(!StackEmpty(ps));处理头节点的元素如果栈中只有一个头节点那么直接销毁栈顶free(ps-top); ps-top NULL;否则修改头节点指针指向定义del存放要被删的头节点更新头节点为下一个节点ps-top ps-top-next释放del指向的空间要被删除节点的空间并置空free(del); del NULL;元素个数减1ps-size--;
void StackPop(ST* ps)
{assert(ps);//ps!NULLassert(!StackEmpty(ps));//栈不能为空if (ps-size 1 || ps-top-next NULL){//如果栈中只有一个数据直接销毁栈顶即可free(ps-top);ps-top NULL;}else{//如果栈的数据个数大于1先改变栈顶指针指向再销毁栈顶空间即可StackNode* del ps-top;ps-top ps-top-next;free(del);//释放空间del NULL;//指向空}//每次出栈有效数据减一ps-size--;
}5取栈顶元素
断言非空后返回top指向的元素数据
STDataType StackTop(ST* ps)
{assert(ps);//ps!NULLassert(!StackEmpty(ps));//栈不能为空return ps-top-data;
}6 获取元素个数
直接返回ST结构体中的size即可
int STSize(ST* ps)
{assert(ps);//ps!NULLreturn ps-size;
}7销毁
链式栈的销毁和顺序栈的销毁不一样链式栈的销毁需要遍历节点一一删除和单链表的删除操作一样
void STDestory(ST* ps)
{assert(ps);//ps!NULLassert(!StackEmpty(ps));//栈不能为空while (!StackEmpty(ps)){StackPop(ps);}
}四、性能分析
时间复杂度顺序栈和链式栈在插入、删除和访问栈顶元素等操作上的时间复杂度都是O(1)。这意味着它们在这些基本操作上的性能是相似的。 空间复杂度 顺序栈 顺序栈的空间复杂度是O(n)其中n是栈中元素的数量。这是因为顺序栈使用数组来存储元素而数组的大小确定。尽管数组中可能有一部分空间未被使用特别是当栈未满时但整个数组的空间都被分配给了顺序栈。如果栈的容量不足还需要进行扩容操作这可能会进一步增加空间复杂度。 链式栈 链式栈的空间复杂度也是O(n)但这里的n指的是栈中实际元素的数量而不是预先分配的空间大小。链式栈通过动态地创建和删除节点来管理内存因此它不会浪费未使用的空间。然而每个节点除了存储数据外还需要额外的空间来存储指向下一个节点的指针这增加了每个节点的空间开销。但从整体上看链式栈的空间复杂度仍然是线性的因为它只与栈中元素的数量有关。 总结如果栈的使用过程中元素变化不可预料,有时很小,有时非常大,那么最好是用链栈,反之,如果它的变化在可控范围内,建议使用顺序栈会更好一些。
