【数据结构】“栈”的模拟实现

💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃个人主页 ：阿然成长日记 👈点击可跳转
📆 个人专栏： 🔹数据结构与算法🔹C语言进阶
🚩 不能则学，不知则问，耻于问人，决无长进
🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍

⭐️一、什么是栈

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

🔸压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
🔸出栈：栈的删除操作叫做出栈。出数据也在栈顶

💬二、栈的分类

1️⃣ Ⅰ 顺序存储结构

实用性不高。
2️⃣ Ⅱ 链式存储结构

📅三、用动态数组实现栈

使用动态内存管理函数，实现数组动态化。有关动态内存函数的详细讲解可点击查看
👉 内存函数详解

1.栈的结构体定义

注意：这里我们将栈顶初始化是-1。你也可以是0；
代码:

typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;

2.初始化

代码:

//初始化
void STInit(ST* p)
{p->a = NULL;p->capacity = 0;p->top = 0;
}

3.栈的销毁

代码:

//栈的销毁
void STDesdroy(ST* p)
{assert(p);free(p->a);p->a = NULL;p->capacity = p->top = 0;
}

4.压栈

代码:

//压栈
void STPush(ST* p, STDataType x)
{assert(p);//开辟空间if (p->capacity = p->top){int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;//开辟空间个数 STDataType* tmp = (STDataType*)realloc(p->a, sizeof(STDataType) * newcapacity);//开辟if (tmp == NULL){perror("realloc fail\n");}p->a = tmp;//将开辟好的空间指回原指针p->capacity = newcapacity;}p->a[p->top] = x;p->top++;
}

5.出栈

代码:

//出栈
void STPop(ST* p)
{assert(p);assert(p->top >= 0);p->top--;
}

6.获取栈顶元素

//获取栈顶元素
STDataType STTop(ST* p)
{assert(p);assert(p->top > 0);return p->a[p->top];
}

7.获取栈内元素

//大小
int STSize(ST* p)
{assert(p);return p->top;
}

判断栈是否为空

代码：

//是否为空
bool STisEmpty(ST* p)
{if (p->top == 0){return false;}return true;
}