徐州网站开发口碑好,自己做网站投入,主流网站建设服务器有哪些,湖南网站备案要多少天数据结构——栈 一、栈的结构和概念二、 栈的两种构建方式①、用数组进行构建②、用链表进行构建 三、栈的创建四、栈的初始化五、栈的销毁六、压栈七、出栈八、判空九、获取栈顶元素十、获取栈的size 一、栈的结构和概念
栈#xff1a;栈是一种特殊的线性表#xff0c;其只… 数据结构——栈 一、栈的结构和概念二、 栈的两种构建方式①、用数组进行构建②、用链表进行构建 三、栈的创建四、栈的初始化五、栈的销毁六、压栈七、出栈八、判空九、获取栈顶元素十、获取栈的size 一、栈的结构和概念
栈栈是一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。
二、 栈的两种构建方式
①、用数组进行构建 ②、用链表进行构建 本篇我们采用数组构建的方式为大家进行讲解。本篇博客主要从栈的初始化、栈的销毁、压栈出栈等七个方面为大家全面进行栈的讲解。
//初始化
void InitST(ST* pst);
//销毁
void DestoryST(ST* pst);
//压栈
void PushST(ST* pst, STDatatype x);
//出栈
void PopST(ST* pst);
//判空
bool STEmpty(ST* pst);
//获取栈顶元素
STDatatype TopST(ST* pst);
//获取栈的size
int STSize(ST* pst);
三、栈的创建
typedef struct STack
{STDatatype* a;//数组int capacity;//容量int top;//栈顶元素的下一个
}ST;我们采用结构体的方式创建一个结构体成员变量其中定义了数组指针a,capacity容量和top。其中a指向的是栈的开始位置capacity指向的是栈的结束位置至于top,则既可以指向栈顶位置也可以指向栈顶元素的下一个位置这取决于你对其如何进行初始化。
四、栈的初始化
栈的初始化中最为重要的一步便是如何对pst-top进行相应的初始化如果我们将pst-top初始化为0则top将指向栈顶元素的下一个位置。但是如果我们将其初始化为-1则top将指向栈顶元素。但是如果将其初始化为-1也会带来一些不必要的麻烦例如一些不懂的栈结构的人可能会以为这里初始化错误。所以我们在这里将其初始化为0.
void InitST(ST* pst)
{assert(pst);pst-a NULL;pst-capacity 0;//栈顶元素的下一个位置pst-top 0;
}五、栈的销毁
利用free函数将开辟的内存空间进行释放并将其置为NULL,并把capacity和top置为0。
void DestoryST(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-capacity pst-top 0;
}六、压栈
由于栈的后进先出特性我们便只能对栈顶元素进行出栈操作不能随意的对其他元素进行出栈操作。出栈函数非常简单首先是扩容部分如果数组内存不够便对其进行扩容操作。然后在栈顶处插入数据即可。
void PushST(ST* pst, STDatatype x)
{if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDatatype *tmp (STDatatype*)realloc(pst-a, sizeof(STDatatype) * newcapacity);if (tmp NULL){perror(realloc fail);return;}pst-a tmp;pst-capacity newcapacity;}//插入数据pst-a[pst-top] x;pst-top;七、出栈
出栈操作我们直接对pst-top进行–操作即可。但是这里需要注意的是当数组元素全部删除完毕之后便不能对其进行删除操作了所以这里需要对其进行判空。
oid PopST(ST* pst)
{assert(pst);assert(!STEmpty(pst));pst-top--;
}八、判空
直接判断pst-top是否等于0如果pst-top等于0则返回true,否则返回false。
bool STEmpty(ST* pst)
{assert(pst);return pst-top 0;
}九、获取栈顶元素
这里需要注意的是由于我们定义的是pst-top0,即表示的是栈顶元素的下一个位置所以当我们想要获取栈顶元素时我们需要对其进行-1操作返回栈顶元素。
//获取栈顶元素
STDatatype TopST(ST* pst)
{assert(pst);assert(!STEmpty(pst));return pst-a[pst-top-1];
}十、获取栈的size
直接将pst-top进行返回操作。
//获取栈的size
int STSize(ST* pst)
{assert(pst);return pst-top;
}
