【数据结构】栈的实现

🚩纸上得来终觉浅，绝知此事要躬行。
🌟主页：June-Frost
🚀专栏：数据结构

🔥该文章主要了解实现栈的相关操作。

🌍 栈的概念

栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素——压栈和出栈都是在栈顶。

🌎栈的实现

栈的实现一般可以使用数组或者链表实现，如果使用数组，以尾部为栈顶，压栈和出栈的时间消耗都为O(1)，唯一的缺陷就是需要扩容。如果考虑单链表，若以尾节点为栈顶，那么时间复杂度为O(N)，如果以头节点为栈顶，时间复杂度就是O(1)。相较于链表，数组结构的缓存利用率较高，相对而言更优一些。这里采用数组结构实现。
结构体：

typedef int STDataType;
typedef struct Stack
{STDataType* arr;int capacity; // 记录容量int top;//栈顶
}ST;

✉️ 初始化栈和销毁栈

void STInit(ST* ps)
{assert(ps);ps->arr = NULL;ps->top = ps->capacity = 0;
}void STDestroy(ST* ps)
{assert(ps);free(ps->arr);ps->arr = NULL;ps->capacity = ps->top = 0;
}

这里将top初始化为0，意味着top标记的是栈顶元素的下一个元素。top如果初始化为-1，那么标记的就是栈顶元素，初始化的不同，后续相关操作的实现方式也是不同的。

✉️ 入栈

void STPush(ST* ps, STDataType x)
{assert(ps);//扩容if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4: ps->capacity * 2;//如果 ps->a 为NULL，realloc的功能和malloc一样 STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType) * newCapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->arr = tmp;ps->capacity = newCapacity;}ps->arr[ps->top] = x;ps->top++;
}

✉️ 出栈

void STPop(ST* ps)
{assert(ps->top > 0 && ps);ps->top--;
}

✉️ 获取栈顶元素

STDataType STTop(ST* ps)
{assert(ps->top > 0 && ps);return ps->arr[ps->top-1];
}

✉️ 获取栈中有效元素个数

void STSize(ST* ps)
{assert(ps);return ps->top;
}

✉️ 判空

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

✉️ 接口测试

这样的逻辑就可以实现栈的特性。

void test()
{ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);STPush(&st, 5);STPush(&st, 6);STPush(&st, 7);STPush(&st, 8);while (!STEmpty(&st)){printf("%d ", STTop(&st));STPop(&st);}STDestroy(&st);
}