上海网站建设推广河北百度推广seo
目录
1. 栈
编辑
1.2 栈的实现
2. 代码的实现
2.1 初始化栈和销毁栈
2.2栈顶元素的插入
2.3栈顶元素的删除
栈元素删除
2.4栈顶元素的获取和栈元素的个数
1. 栈
1.1 栈的概念和结构
栈(Stack)是一种线性存储结构，它具有如下特点：
（1）栈中的数据元素遵守”先进后出”(First In Last Out)的原则，简称FILO结构。
（2）限定只能在栈顶进行插入和删除操作。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶
注意：我们在进行数据插入和删除操作中，都是在栈顶实现的，而另一端叫做栈底。
我们借用一下这个图来说明：
1.2 栈的实现
我们这里可以通过两种方法实现，顺序表或链表。
这里我们会发现链表要尾插或者尾删需要便利一遍链表，效率低；顺序表尾插尾删很快，但是还要解决扩容问题。
所以这里我们就引出了栈这个东西
2. 代码的实现
这里我们需要说明一下，之前我们在实现链表或者顺序表双向链表中都用的是size，为了更好的明确个数。
这里top指的是栈顶元素，如果初始化为 ” -1 “ ，指的是栈顶元素；如果为 “ 0 ” ，指的是栈顶的下一个元素。
这里面我建议是初始化为0：
- top还可以表示元素的个数，可以用来判断栈是否满了
- 插入元素的时候直接在top的位置插入就行，然后再top++即可
废话不多先来个头文件
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);2.1 初始化栈和销毁栈
我们首先要检查一下结构体是否为空，这里我们要注意一下
void STInit(ST* pst)
{assert(pst);pst->a = NULL;//pst->top = -1; // top 指向栈顶数据pst->top = 0; // top 指向栈顶数据的下一个位置pst->capacity = 0;
}这里我们断言结构体不为空在继续，释放我们开辟的空间，将其他数据置为0
void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}2.2栈顶元素的插入
这里面我们要判断储存空间是否足够，如果没有开辟，我们可以先开辟一些空间出来；如果栈空间满了，直接将栈空间扩大二倍
void STPush(ST* pst, STDataType x)
{if (pst->top == pst->capacity){int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newCapacity;}pst->a[pst->top] = x;pst->top++;
}2.3栈顶元素的删除
注意：当top为0，代表我们没有元素，不能再减下去，需要一个函数判断一下
判断函数
bool STEmpty(ST* pst)
{assert(pst);/*if (pst->top == 0){return true;}else{return false;}*/return pst->top == 0;
}栈元素删除
void STPop(ST* pst)
{assert(pst);assert(!STEmpty(pst));pst->top--;
}2.4栈顶元素的获取和栈元素的个数
这里面我们初始化为0，所以我们返回栈顶元素前一个元素即可；如果为空，需要我们断言一下
STDataType STTop(ST* pst)
{assert(pst);assert(!STEmpty(pst));return pst->a[pst->top - 1];
}元素个数
int STSize(ST* pst)
{assert(pst);return pst->top;
}以上就是今天栈实现的分享，如果喜欢的话请三联支持一下吧，感谢你的收看，我们下期再见！！！