☃️个人主页:fighting小泽
🌸作者简介:目前正在学习C语言和数据结构
🌼博客专栏:数据结构
🏵️欢迎关注:评论👊🏻点赞👍🏻留言💪🏻
1.栈
1.1栈的概念及结构
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。
我们的顺序表链表的作用就是单纯的增删查改数据,但是栈除了存储数据还有一个后进先出的性质。
假如说我们要在栈中存储1、2、3、4,那么它们就会依次入栈,1在栈底,4在栈顶
但是当我们想出栈的时候是不是只能4、3、2、1呢?
其实不是的,我们可以入一个元素出一个元素,也可以入一个出两个,总之按自己的需求来定,但也要确保出栈顺序正确。
我们来看两个题:
- 一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈,然后再依次出栈,则元素出
栈的顺序是( )。
A 12345ABCDE
B EDCBA54321
C ABCDE12345
D 54321EDCBA - 若进栈序列为 1,2,3,4 ,进栈过程中可以出栈,则下列不可能的一个出栈序列是()
A 1,4,3,2
B 2,3,4,1
C 3,1,4,2
D 3,4,2,1
大家可以仔细想一想哦
1.2栈的实现
我们实现栈可以用两种方式,一种是通过顺序表来实现,一种是通过链表来实现。哪种方式好呢?
- 在前面线性表的学习中我们知道,顺序表的优点是尾插尾删很方便,但是链表想要尾插尾删还要遍历一遍链表,效率就会很低。
- 顺序表虽然存在空间不足问题,需要不断扩容。但是扩容的代价很低,而且到后面扩的会越来越慢
这样想一想用顺序表来实现栈是不是更好一些。
如果想用链表来实现栈,可以用链表尾当栈底,链表头当栈顶。插入删除数据就进行头插头删,感兴趣的朋友可以试一试。
栈的结构体的定义
栈的结构体其实和顺序表差不多,一个动态开辟的数组,一个栈的容量。
- 注意 top 我们要决定它指向栈顶还是栈顶的下一个元素。如果top初始化为0,则它指向栈顶的下一个元素。如果top初始化为-1,则它指向栈顶元素。
- 我比较喜欢初始化为0,1是top还可以表示元素的个数,可以用来判断栈是否满了。2是插入元素的时候直接在top的位置插入就行,然后再top++即可。
这里根据大家喜好设定就行。
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
Stack.h
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<stdio.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);//获得栈顶元素
bool STEmpty(ST* pst);//判断栈是否为空
int STSize(ST* pst);//获得栈的元素个数
Stack.c
1.初始化栈和销毁栈
初始化的时候要注意参数传的是形参,要用assert判断一下。
初始化时我们可以先给栈开辟一些空间,也可以不开辟,等到要插入数据时再开辟。
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
pst->top = 0;
pst->capacity = 0;
}
对栈进行销毁,我们只需要把动态开辟的空间a给释放置空了,把其它数据置为0即可。
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->capacity = 0;
pst->top = 0;
}
2.栈顶插入元素
首先我们要判断栈是否满了,若栈的容量为0,则开辟一部分空间。若栈的空间满了,就将栈的空间扩大二倍。
如果栈没满,我们可以直接在top位置插入我们想插入的元素,然后top++即可。
void STPush(ST* pst, STDataType x)
{
assert(pst);
if (pst->capacity == pst->top)
{
pst->capacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
pst->a = (STDataType*)realloc(pst->a,sizeof(STDataType) * pst->capacity);
}
pst->a[pst->top] = x;
pst->top++;
}
3.栈顶删除元素
删除元素的话,我们直接让top 减一即可。
注意当top为0,即没有元素的时候我们就不能再减下去了,不然会访问到不属于我们的空间。所以我们可以用一个STEmpty函数判断栈是否为空。
void STPop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
pst->top--;
}
如果栈为空,就返回真。如果栈不为空,就返回假
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}
4.获得栈顶元素和元素个数
我们直接返回栈顶的前一个元素即可。
注意:若栈为空,则不能获得栈的元素。所以要判断栈是否为空。
STDataType STTop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
return pst->a[pst->top - 1];
}
直接返回栈顶的下标即可。之所以写这个函数,是因为别人不知道我们的top指向栈顶还是栈顶的下一个元素。所以直接让别人用就完了。
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
5.结尾
这些就是我给大家分享的关于栈的知识啦,是不是很简单啊。希望我们都能有所收获!
先赞后看,养成习惯!!^ _ ^
码字不易,大家的支持就是我坚持下去的动力,点赞后不要忘了关注我哦!文章来源:https://www.toymoban.com/news/detail-450190.html
如有错误,还请您批评改正(。ì _ í。)文章来源地址https://www.toymoban.com/news/detail-450190.html
到了这里,关于【数据结构】栈的详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!