数据结构 —— 栈（超详细图解 & 接口函数实现）

系列文章目录

数据结构 —— 顺序表
数据结构 —— 单链表
数据结构 —— 双向链表
数据结构 —— 栈

文章目录

前言

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构是一种十分优秀的解决实际问题的模板，是先进思想的结晶。博主将会用代码结合大量图解，对数据结构进行深度剖析，以便大家更好的学习数据结构的思想。

一、示例问题：弹匣供弹

1.弹匣供弹原理

在最上面的子弹是最后被压入，也是最先被射出的

2.逻辑示意图

先入后出，后入先出

弹匣里的子弹在被压入时的顺序和被射出时的顺序正好相反，最先被压入的子弹在最后一个位置，同时也是最后被射出，而最后被压入的子弹在最上面的位置，也是最先被射出。

3.栈的引入

栈的引入：先入后出，后入先出的数据结构

二、栈的概念

1.定义

栈(stack)：栈是限定仅在表尾进行插入和删除操作的线性表

我们通常把插入和删除的一端称为栈顶(top)，相反的另一端称为栈底(bottom)，而不含任何元素的栈则称为空栈。栈又可以称为后进先出(Last In First Out)的线性表，简称LIFO结构。

2.结构

栈的结构类型

//类型typedefint STDataType;//栈结构typedefstructStack{
    STDataType *array;// 数组int top;// 栈顶int capacity;// 容量} Stack;

3.存储

存储：用动态开辟的一维数组来实现顺序表的存储结构

由于只需要对栈顶元素进行操作，所以可以使用顺序表的物理结构，来实现堆的逻辑结构的操作。

三、栈的接口函数

1.初始化栈

对顺序表的内容进行初始设置

// 初始化栈voidStackInit(Stack *pst){assert(pst);
    pst->array =(STDataType *)malloc(4*sizeof(STDataType));
    pst->top =0;
    pst->capacity =4;}

2.空栈判断

判断一个栈是否为空

// 检测栈是否为空，空(true)，非空返回(false)
bool StackEmpty(Stack *pst){assert(pst);return pst->top ==0;}

3.入栈（压栈）

栈的插入操作

// 入栈voidStackPush(Stack *pst, STDataType data){assert(pst);if(pst->top == pst->capacity){
        STDataType *newSpace =(STDataType *)realloc(pst->array,sizeof(STDataType)* pst->capacity *2);if(newSpace ==NULL){perror("realloc fail:");}
        pst->array = newSpace;
        pst->capacity *=2;}
    pst->array[pst->top]= data;
    pst->top++;}

4.出栈（弹栈）

栈的删除操作

// 出栈voidStackPop(Stack *pst){assert(pst);assert(!StackEmpty(pst));
    pst->top--;}

5.栈顶元素

获取栈顶部存储的元素

// 获取栈顶元素
STDataType StackTop(Stack *pst){assert(pst);assert(!StackEmpty(pst));return pst->array[pst->top -1];}

6.栈的元素个数

// 获取栈中有效元素个数

// 获取栈中有效元素个数intStackSize(Stack *pst){assert(pst);return pst->top;}

7.栈的销毁

释放栈申请的空间

// 销毁栈voidStackDestroy(Stack *pst){assert(pst);free(pst->array);
    pst->array =NULL;
    pst->capacity = pst->top =0;}

四、总结

栈是解决实际问题时极其常用的一种数据结构，是非常重要的解决问题的方式。栈的各种接口的复现，有利于更好的学习数据结构的思想，有利于开阔视野，学习前辈的智慧结晶。对我们后续解决实际问题也会有很大帮助。