【数据结构】栈

🍃 如果觉得本系列文章内容还不错，欢迎订阅🚩
🎊个人主页:小编的个人主页
🎀 🎉欢迎大家点赞👍收藏⭐文章
✌️ 🤞 🤟 🤘 🤙 👈 👉 👆 🖕 👇 ☝️ 👍

🐼前言

🌟在上一节我们实现了双链表，如果感兴趣的小伙伴，可以阅读我的上一篇文章:> 双链表，这一节小编给大家介绍一种特殊的线性表：栈

🐼栈

✨栈是一种特殊的线性表，它只允许在一端进行操作，进行操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

我们之前学习了链表和数组存储数据结构，那么栈底层是什么存储的呢?
其实用链表和数组都可以实现栈。刚刚说了，栈都是在栈顶进行插入和删除数据，那么如果是链表，每次都要找尾，时间复杂度为O(N),不过如果颠倒，把栈顶放在链表的头部，那么操作和删除元素即头插和头删时间复杂度都为O(1),不过为了方便，而且数组在尾上插入数据的代价比较小，在栈顶(数组尾部)插入和删除数据，时间复杂度都为O(1),因此数组的实现更优一点，我们这里选择数组来作为栈的底层结构。

🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟

✨既然是用数组来存储，我们希望是动态数组，即可增容，这不就和顺序表的结构定义一样吗？
动态顺序栈定义如下:

typedef int STDataType;
//定义顺序栈的结构
typedef struct Stack
{STDataType* arr;int top;//栈顶指针int capacity;//容量
}ST;

下面我们实现栈14`532

🐼初始化栈

void StackInit(ST* ps)
{assert(ps);ps->arr = (STDataType*)malloc(sizeof(STDataType) * 4);if (ps->arr == NULL){perror("malloc fail");exit(-1);}ps->capacity = 4;ps->top = 0;
}

🌻代码解析

💫初始我们先给栈结构成员变量数组指针申请了四个整形空间的大小。将容量初始设为4，栈顶指针置为0。
(注意:top也可以置为-1，置为-1即top即是元素下标；如果top = 0即top指向当前元素的下一个位置，也就是有效的数据个数，所以不一定只有这种写法)
💫时间复杂度为O(1),程序执行常数次，空间复杂度为O(1),只创建有效个变量

🐼入栈

//入栈
void StackPush(ST* ps, STDataType x)
{assert(ps);//判断是否需要增容if (ps->capacity == ps->top){STDataType* tmp =(STDataType*)realloc(ps->arr, ps->capacity*sizeof(STDataType) * 2);if (tmp == NULL){perror("relloc fail");exit(-1);}ps->arr = tmp;ps->capacity *= 2;}ps->arr[ps->top++] = x;
}

🌻代码解析

因为这里是动态栈，所以入栈首先要检查栈容量是否足够，如果不够，对数组进行增容，然后更新capacity，插入元素x，最后更新栈顶指针。
时间复杂度为O(1),程序执行常数次，空间复杂度为O(1),只创建有效个变量
🍂画图剖析:

🍀测试结果:

🐼判空

//判空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

🌻代码解析

通过布尔类型的返回值，如果栈为空，即top = 0;
时间复杂度为O(1),程序执行常数次，空间复杂度为O(1),只创建有效个变量

🐼出栈

//出栈
void StackPop(ST* ps)
{assert(!StackEmpty(ps));ps->top--;
}

🌻代码解析

💫断言保证栈不为空，接着只需要更新top的值，完成出栈操作。(并不是真正把栈顶元素删除了，而是通过栈顶指针的指向，这样操作不会影响到其他函数，跟真正删除效果是一样的)
💫时间复杂度为O(1),程序执行常数次，空间复杂度为O(1),只创建有效个变量
🍂画图剖析:

🐼取栈顶元素

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

🌻代码解析

断言保证栈不为空，直接返回栈顶元素，由于top指向栈顶的下一个位置，所以top要-1

💫时间复杂度为O(1),程序执行常数次，空间复杂度为O(1),只创建有效个变量
🍂画图剖析:

🍀测试结果:

🐼栈的有效元素个数

//栈的有效元素个数
int STsize(ST* ps)
{assert(!StackEmpty(ps));return ps->top;
}

🌻代码解析

断言保证栈不为空，直接返回有效元素top。
时间复杂度为O(1),程序执行常数次，空间复杂度为O(1),只创建有效个变量

🐼销毁栈

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

🌻代码解析

如果指向数组的那块连续空间存在，直接销毁，并将capacity和top的值置为初始值,并将指向数组的指针置为空，防止野指针解引用。
💫时间复杂度为O(1),程序执行常数次，空间复杂度为O(1),只创建有效个变量

🍀测试结果:

🍀栈整体测试:

🐼全部源码

Stack.h

#define  _CRT_SECURE_NO_WARNINGS#include<stdio.h>
#include<assert.h>
#include <stdlib.h>
#include <stdbool.h>typedef int STDataType;
//定义顺序栈的结构
typedef struct Stack
{STDataType* arr;int top;//栈顶指针int capacity;//容量
}ST;//初始化栈
void StackInit(ST* ps);
//销毁栈
void STDestory(ST* ps);
//入栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
//取栈顶元素
STDataType StackTop(ST* ps);
//判空
bool StackEmpty(ST* ps);
//栈的有效元素个数
int STsize(ST* ps);

Stack.c

#include "Stack.h"
//初始化栈
void StackInit(ST* ps)
{assert(ps);ps->arr = (STDataType*)malloc(sizeof(STDataType) * 4);if (ps->arr == NULL)//第一次发现少了个等号{perror("malloc fail");exit(-1);}ps->capacity = 4;ps->top = 0;
}//销毁栈
void STDestory(ST* ps)
{assert(ps );if(ps->arr)free(ps->arr);ps->capacity = ps->top = 0;ps->arr = NULL;
}//入栈
void StackPush(ST* ps, STDataType x)
{assert(ps);//判断是否需要增容if (ps->capacity == ps->top){STDataType* tmp =(STDataType*)realloc(ps->arr, ps->capacity*sizeof(STDataType) * 2);if (tmp == NULL){perror("relloc fail");exit(-1);}ps->arr = tmp;ps->capacity *= 2;}ps->arr[ps->top++] = x;
}
//判空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出栈
void StackPop(ST* ps)
{assert(!StackEmpty(ps));ps->top--;
}//取栈顶元素
STDataType StackTop(ST* ps)
{assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}//栈的有效元素个数
int STsize(ST* ps)
{assert(!StackEmpty(ps));return ps->top;
}

test.c

void test01()
{ST sl;StackInit(&sl);StackPush(&sl, 1);StackPush(&sl, 2);StackPush(&sl, 3);StackPush(&sl, 4);while (!StackEmpty(&sl)){int tmp = StackTop(&sl);printf("%d ", tmp);StackPop(&sl);}printf("\n");STDestory(&sl);}

🐼文末

感谢你看到这里，如果觉得本篇文章对你有帮助，点个赞👍 吧，你的点赞就是我更新的最大动力 ⛅️🌈 ☀️