深入理解栈（Stack）(纯小白进)

一、栈是什么？

1. 栈的概念

栈（Stack）：⼀种特殊的线性表，是一种常见的数据结构，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。栈的应用非常广泛，例如函数调用栈、表达式求值、括号匹配等。

栈的基本操作包括：

入栈（Push）：将元素压入栈顶。
出栈（Pop）：将栈顶元素弹出。
查看栈顶元素（Top）：获取栈顶元素的值，但不弹出。
判断栈是否为空（Empty）：检查栈是否为空。
查看栈的大小（Size）：获取栈内元素的个数。

栈就像是一叠摞在一起的盘子，我们放盘子只能放到盘子的最上面，同理取盘子，也只能从栈的最上方来取。放盘子称为入栈，去盘子称为出栈。
数据结构入门】栈（Stack）的实现（定义、销毁、入栈、出栈等） | 图解数据结构，超详细哦~_销毁栈-CSDN博客" />

2.栈的结构选择

栈底层结构选型：

栈的实现⼀般可以使⽤数组或者链表实现，相对⽽⾔数组的结构实现更优⼀些。因为数组在尾上插⼊数据的代价⽐较⼩。

对比：

数组实现的栈是一种固定大小的栈，其优点是实现简单，缺点是大小固定。

链表实现的栈是一种动态大小的栈，其优点是大小可变，缺点是实现稍微复杂。

定长的静态栈，实际中我们一般不使用，所以我们下面主要实现的就是支持动态增长的栈。

二、栈的实现

1. 栈结构体的定义

基于下面这张图，再类比顺序表，我们可以发现，栈的实现需要三个元素。
在这里插入图片描述

typedef int STDataType;
typedef struct Stack
{STDataType* arr;        //栈数组int capacity;           //栈的空间大小int top;                //栈顶位置
}ST;

对数据类型进行重命名，这样以后需要更换其他数据类型使用的时候只需要更改这一个地方就可以了。

ps: 定义一个数组动态的开辟空间，top用来记录栈顶元素的位置，capacity来表示栈的总容量大小。

2. 栈的初始化

先将栈中所有的数据都初始化为空，因为栈只需要在容量满的时候进行扩容，这里可以不需要先开辟空间，这一步可以节省。
具体的实现是：

//栈的初始化
void STInit(ST* ps)
{assert(ps);ps->arr = NULL;ps->capacity = 0;ps->top = 0;
}

3. 栈的销毁

有初始化必然有销毁。

我们需要释放栈中的空间，别忘了将其置为NULL,防止内存泄漏。
释放掉栈中所有的元素。

注意：

这里不能直接对ps进行释放，因为ps中的arr是动态开辟来的，所以需要先对arr进行free，然后将其他成员置空。

//栈的销毁
void STDestroy(ST* ps)
{assert(ps);if(ps->arr)free(ps->arr);ps->arr = NULL;ps->capacity = 0;ps->top = 0;
}

4. 入栈

//数据入栈
void STPush(ST* ps, STDataType x); //STDataType x 是我们需要插入的数据

在这里插入图片描述

在入栈之前我们需要判断数组容量够不够，需不需要扩容。
在这里插入图片描述

具体实现是

void STPush(ST* ps, STDataType x) {assert(ps);if (ps->top == ps->capacity) {STDataType* temp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);if (temp == NULL) {perror("realloc fail");return;}ps->a = temp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;
}

5.出栈

注意，如果栈为空，则不能出数据。

//数据出栈
void STPop(ST* ps);
//栈判空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

在这里插入图片描述

开始出栈

//数据出栈
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}

6. 取栈顶元素

//取栈顶元素
STDataType STTop(ST* ps);
//取栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->arr[ps->top - 1];
}

那么只要栈不为空，就可以一直取栈顶元素
在这里插入图片描述

7. 栈中元素的个数

//获取栈中有效元素个数
int STSize(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}

8. 判断栈是否为空

bool  STEmpty(ST* ps) {assert(ps);return ps->top == 0;
}

总结

栈是一种简单且高效的数据结构，适用于需要“后进先出”操作的场景。通过掌握栈的基本操作和实现方式，我们可以更好地理解和应用这一数据结构，从而提高程序的效率和可靠性。希望这篇博客可以帮租到你，下一站：队列。