【数据结构】“栈”的模拟实现-阿里云开发者社区

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

2023-10-09 35

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 文章目录⭐️一、什么是栈💬二、栈的分类📅三、用动态数组实现栈1.栈的结构体定义2.初始化3.栈的销毁

💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤

📃个人主页：阿然成长日记 👈点击可跳转

📆 个人专栏： 🔹数据结构与算法🔹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;
}

8断栈是否为空

代码：

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