（数据结构）栈的实现——再一次保姆级教学

目录

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;
}

---

以上就是今天栈实现的分享，如果喜欢的话请三联支持一下吧，感谢你的收看，我们下期再见！！！