【数组栈】实现

简介: 【数组栈】实现



我们已经学习过了【线性表】中的顺序表和链表。今天开始进入栈和队列。栈和队列是顺序表和链表的延续,也是一种线性表(线性表在逻辑上也是连续的)。大体结构上都很相似,所以大家学习起来也会很容易的。但是栈和队列也有自己独特的性质,学习也需要特别注意哦。

栈的概念及其结构

:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。

栈中的数据元素遵守 后进先出 / 后进先出 LIFO(Last In First Out)的原则

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

【先进后出/后进先出】可以类比【弹夹】

栈的实现

了解了栈的概念,如何实现栈呢?

根据前面博文我们可以【数组栈】和【链式栈】

数组栈

数组栈比较简单,也是快速容易实现,首先就是【数组栈】实现。

链式栈

链式栈分为【单链表】和【双向链表】去实现栈。毋庸置疑,【双向链表实现】栈顶可以是尾巴,也可以是头,因为双向链表的头插/头删和尾插/尾删都是很方便的。

但是为了节省资源,我们用【单链表】该怎样去设计呢?

单链表实现栈栈顶只能是单链表头(头插/头删易),栈底只能是单链表尾(头删很复杂)

栈的常见接口实现

  • 断言NULL/Pop==0情况
  • 改变结构体用指针
  • top的指向
  • 单个数据直接用,多个数据用结构体包含起来
  • 数组的数据访问用数组下标即可访问
  • pst和pst->a搞清楚!
  • 入栈顺序是只有一种,但是出栈顺序有多种!!

主函数Test.c

#include"Stack.h"
int main()
{
  ST pst;//创建结构体
  STInit(&pst);//传地址是修改结构体内部
  STPush(&pst, 1);
  STPush(&pst, 2);
  STPush(&pst, 3);
  STPush(&pst, 4);
  STPush(&pst, 5);
  while (!STempty(&pst))
  {
    printf("%d ", STTop(&pst));
    STPop(&pst);
  }
  STDestroy(&pst);
}

由于栈是其只允许在固定的一端进行插入和删除元素操作。所以栈的访问是必须先Pop弹出元素才能访问下一个元素。

while (!STempty(&pst))
  {
    printf("%d ", STTop(&pst));
    STPop(&pst);
  }

头文件&函数声明Stack.h

头文件

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

函数声明

  • 创建结构体
typedef int STDatatype;
typedef struct Stack
{
  STDatatype* a;
  int top;
  int capacity;
}ST;
  • 初始化
void STInit(ST* pst);
  • 释放销毁
void STDestroy(ST* pst);
  • 压栈
void STPush(ST* pst, STDatatype x);
  • 出栈
void STPop(ST* pst);
  • 栈顶元素
STDatatype STTop(ST* pst);
  • 判断栈是否为NULL
bool STempty(ST* pst);
  • 栈内的元素个数
int STSize(ST* pst);

函数实现Stack.c

初始化SLInit

如果初始化 top=0:表示栈内元素的个数。作为a[top]指针指向栈顶元素的下一个。

如果初始化 top=-1:表示数组元素的下标。作为a[top]指针指向栈顶元素。

#include"Stack.h"
void STInit(ST* pst)
{
  assert(pst);
  pst->a = 0;
//表示top指向栈顶元素的下一个位置
  pst->top = 0;
//表示top指向栈顶元素
  //pst->top = -1;
  pst->capacity = 0;
}

扩容Createcapacity

void Createcapacity(ST* pst)
{
  //扩容
  if (pst->top == pst->capacity)
  {
    int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
    STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(ST) * newcapacity);
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    pst->a = tmp;
    pst->capacity = newcapacity;
  }
}

压栈STPush

void STPush(ST* pst, STDatatype x)
{
  assert(pst);
  Createcapacity(pst);
  pst->a[pst->top] = x;
  pst->top++;
}

出栈STPop

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

栈顶元素STTop

STDatatype STTop(ST* pst)
{
  assert(pst);
  assert(pst->top > 0);
  return pst->a[pst->top-1];
}

判断栈是否为空STempty

bool STempty(ST* pst)
{
  assert(pst);
  return pst->top == 0;//为0就是true 为!=0就是为flase
}

栈内元素个数STSize

int STSize(ST* pst)
{
  assert(pst);
  return pst->top;
}

数组栈空间释放STDestroy

void STDestroy(ST* pst)
{
  assert(pst);
  free(pst->a);
  pst->a = NULL;
  pst->top = 0;
  pst->capacity = 0;
}

数组栈总代码

//Test.c
#include"Stack.h"
int main()
{
  ST pst;
  STInit(&pst);
  STPush(&pst, 1);
  STPush(&pst, 2);
  STPush(&pst, 3);
  STPush(&pst, 4);
  STPush(&pst, 5);
  while (!STempty(&pst))
  {
    printf("%d ", STTop(&pst));
    STPop(&pst);
  }
  STDestroy(&pst);
}
//Stack.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int STDatatype;
typedef struct Stack
{
  STDatatype* a;
  int top;
  int capacity;
}ST;
void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst, STDatatype x);
void STPop(ST* pst);
STDatatype STTop(ST* pst);
bool STempty(ST* pst);
int STSize(ST* pst);
//Stack.c
#include"Stack.h"
void STInit(ST* pst)
{
  assert(pst);
  pst->a = 0;
  pst->top = 0;
  pst->capacity = 0;
}
void Createcapacity(ST* pst)
{
  //扩容
  if (pst->top == pst->capacity)
  {
    int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
    ST* tmp = (ST*)realloc(pst->a, sizeof(ST) * newcapacity);
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    pst->a = tmp;
    pst->capacity = newcapacity;
  }
}
void STPush(ST* pst, STDatatype x)
{
  assert(pst);
  Createcapacity(pst);
  pst->a[pst->top] = x;
  pst->top++;
}
void STPop(ST* pst)
{
  assert(pst);
  assert(pst->top > 0);
  pst->top--;
}
STDatatype STTop(ST* pst)
{
  assert(pst);
  assert(pst->top > 0);
  return pst->a[pst->top-1];
}
bool STempty(ST* pst)
{
  assert(pst);
  return pst->top == 0;//为0就是true 为!=0就是为flase
}
int STSize(ST* pst)
{
  assert(pst);
  return pst->top;
}
void STDestroy(ST* pst)
{
  assert(pst);
  free(pst->a);
  pst->a = NULL;
  pst->top = 0;
  pst->capacity = 0;
}

✔✔✔✔✔最后,感谢大家的阅读,若有错误和不足,欢迎指正!各位小伙伴乖乖敲代码哦。

代码---------→【唐棣棣 (TSQXG) - Gitee.com

联系---------→【邮箱:2784139418@qq.com】

目录
相关文章
|
12天前
|
消息中间件 存储 搜索推荐
深入理解栈和队列(二):队列
深入理解栈和队列(二):队列
29 0
|
1月前
【栈】数据结构栈的实现
【栈】数据结构栈的实现
|
5天前
|
存储 算法 调度
数据结构期末复习(3)栈和队列
数据结构期末复习(3)栈和队列
13 0
|
17天前
|
存储 缓存 算法
【算法与数据结构】栈的实现详解
【算法与数据结构】栈的实现详解
|
17天前
|
存储 算法 编译器
【数据结构】栈算法(算法原理+源码)
【数据结构】栈算法(算法原理+源码)
【数据结构】栈算法(算法原理+源码)
|
21天前
|
存储
【数据结构】什么是栈?
【数据结构】什么是栈?
24 0
【数据结构】什么是栈?
|
25天前
|
存储 设计模式 算法
【C/C++ 数据结构 线性表】深入理解与实现栈:从基础到应用的全面探索
【C/C++ 数据结构 线性表】深入理解与实现栈:从基础到应用的全面探索
52 0
|
26天前
|
存储 算法 Serverless
【软件设计师备考 专题 】数据结构深度解析:从数组到图
【软件设计师备考 专题 】数据结构深度解析:从数组到图
56 0
|
26天前
|
机器学习/深度学习 存储 Java
揭秘数组:数据结构的基石与代码实践解析
揭秘数组:数据结构的基石与代码实践解析
8 0
|
26天前
|
存储
用队列和栈分别实现栈和队列
用队列和栈分别实现栈和队列
15 1

热门文章

最新文章