小企业网站建设和管理,温州谷歌优化排名公司,好一点网站建设公司,大连网站制作信ls15227目录
栈的概念及其结构
栈的实现
数组栈
链式栈 栈的常见接口实现
主函数Test.c
头文件函数声明Stack.h
头文件
函数声明
函数实现Stack.c
初始化SLInit
扩容Createcapacity
压栈STPush
出栈STPop
栈顶元素STTop
判断栈是否为空STempty
栈内元素个数STSzi…目录
栈的概念及其结构
栈的实现
数组栈
链式栈 栈的常见接口实现
主函数Test.c
头文件函数声明Stack.h
头文件
函数声明
函数实现Stack.c
初始化SLInit
扩容Createcapacity
压栈STPush
出栈STPop
栈顶元素STTop
判断栈是否为空STempty
栈内元素个数STSzie
数组栈空间释放STDestroy
数组栈总代码 我们已经学习过了【线性表】中的顺序表和链表。今天开始进入栈和队列。栈和队列是顺序表和链表的延续也是一种线性表线性表在逻辑上也是连续的。大体结构上都很相似所以大家学习起来也会很容易的。但是栈和队列也有自己独特的性质学习也需要特别注意哦。
栈的概念及其结构 栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。 栈中的数据元素遵守 后进先出 / 后进先出 LIFOLast In First Out的原则 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。出栈栈的删除操作叫做出栈。出数据也在栈顶。 【先进后出/后进先出】可以类比【弹夹】 栈的实现
了解了栈的概念如何实现栈呢
根据前面博文我们可以【数组栈】和【链式栈】
数组栈 数组栈比较简单也是快速容易实现首先就是【数组栈】实现。 链式栈
链式栈分为【单链表】和【双向链表】去实现栈。毋庸置疑【双向链表实现】栈顶可以是尾巴也可以是头因为双向链表的头插/头删和尾插/尾删都是很方便的。
但是为了节省资源我们用【单链表】该怎样去设计呢 单链表实现栈栈顶只能是单链表头头插/头删易栈底只能是单链表尾头删很复杂 栈的常见接口实现
断言NULL/Pop0情况改变结构体用指针top的指向单个数据直接用多个数据用结构体包含起来数组的数据访问用数组下标即可访问pst和pst-a搞清楚入栈顺序是只有一种但是出栈顺序有多种
主函数Test.c
#includeStack.h
int main()
{ST pst;//创建结构体STInit(pst);//传地址是修改结构体内部STPush(pst, 1);STPush(pst, 2);STPush(pst, 3);STPush(pst, 4);STPush(pst, 5);while (!STempty(pst)){printf(%d , STTop(pst));STPop(pst);}STDestroy(pst);
} 由于栈是其只允许在固定的一端进行插入和删除元素操作。所以栈的访问是必须先Pop弹出元素才能访问下一个元素。 while (!STempty(pst)){printf(%d , STTop(pst));STPop(pst);}
头文件函数声明Stack.h
头文件
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.h
函数声明
创建结构体
typedef int STDatatype;
typedef struct Stack
{STDatatype* a;int top;int capacity;
}ST;
初始化
void STInit(ST* pst);
释放销毁
void STDestroy(ST* pst);
压栈
void STPush(ST* pst, STDatatype x);
出栈
void STPop(ST* pst);
栈顶元素
STDatatype STTop(ST* pst);
判断栈是否为NULL
bool STempty(ST* pst);
栈内的元素个数
int STSize(ST* pst);
函数实现Stack.c
初始化SLInit 如果初始化 top0表示栈内元素的个数。作为a[top]指针指向栈顶元素的下一个。 如果初始化 top-1表示数组元素的下标。作为a[top]指针指向栈顶元素。 #includeStack.h
void STInit(ST* pst)
{assert(pst);pst-a 0;
//表示top指向栈顶元素的下一个位置pst-top 0;
//表示top指向栈顶元素//pst-top -1;pst-capacity 0;
}
扩容Createcapacity
void Createcapacity(ST* pst)
{//扩容if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : 2 * pst-capacity;ST* tmp (ST*)realloc(pst-a, sizeof(ST) * newcapacity);if (tmp NULL){perror(realloc fail);return;}pst-a tmp;pst-capacity newcapacity;}
}
压栈STPush
void STPush(ST* pst, STDatatype x)
{assert(pst);Createcapacity(pst);pst-a[pst-top] x;pst-top;
}
出栈STPop
void STPop(ST* pst)
{assert(pst);assert(pst-top 0);pst-top--;
}
栈顶元素STTop
STDatatype STTop(ST* pst)
{assert(pst);assert(pst-top 0);return pst-a[pst-top-1];
}
判断栈是否为空STempty
bool STempty(ST* pst)
{assert(pst);return pst-top 0;//为0就是true 为0就是为flase
}
栈内元素个数STSzie
int STSize(ST* pst)
{assert(pst);return pst-top;
}
数组栈空间释放STDestroy
void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-top 0;pst-capacity 0;
}
数组栈总代码
//Test.c
#includeStack.h
int main()
{ST pst;STInit(pst);STPush(pst, 1);STPush(pst, 2);STPush(pst, 3);STPush(pst, 4);STPush(pst, 5);while (!STempty(pst)){printf(%d , STTop(pst));STPop(pst);}STDestroy(pst);
}
//Stack.h
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.htypedef int STDatatype;
typedef struct Stack
{STDatatype* a;int top;int capacity;
}ST;void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst, STDatatype x);
void STPop(ST* pst);
STDatatype STTop(ST* pst);
bool STempty(ST* pst);
int STSize(ST* pst);
//Stack.c
#includeStack.h
void STInit(ST* pst)
{assert(pst);pst-a 0;pst-top 0;pst-capacity 0;
}void Createcapacity(ST* pst)
{//扩容if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : 2 * pst-capacity;ST* tmp (ST*)realloc(pst-a, sizeof(ST) * newcapacity);if (tmp NULL){perror(realloc fail);return;}pst-a tmp;pst-capacity newcapacity;}
}void STPush(ST* pst, STDatatype x)
{assert(pst);Createcapacity(pst);pst-a[pst-top] x;pst-top;
}void STPop(ST* pst)
{assert(pst);assert(pst-top 0);pst-top--;
}STDatatype STTop(ST* pst)
{assert(pst);assert(pst-top 0);return pst-a[pst-top-1];
}bool STempty(ST* pst)
{assert(pst);return pst-top 0;//为0就是true 为0就是为flase
}int STSize(ST* pst)
{assert(pst);return pst-top;
}void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-top 0;pst-capacity 0;
} ✔✔✔✔✔最后感谢大家的阅读若有错误和不足欢迎指正各位小伙伴乖乖敲代码哦。
代码---------→【唐棣棣 (TSQXG) - Gitee.com】
联系---------→【邮箱2784139418qq.com】
