【数据结构】--- 几分钟走进栈和队列(详解-上)

2023-06-28 47

版权

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

简介： 数据结构学习第十弹——栈和队列

🌟一、栈

🌏1.1栈的概念及结构：

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

压栈: 栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈: 栈的删除操作叫做出栈。出数据也在栈顶。

🌏1.2实现栈的两种方式：

数组栈

链式栈

对于链式栈是不建议第一种写法的因为尾删需要找到前一个结点(单链表)

🌟二、栈实现(数组栈)

🌏2.1结构：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Strack
{
  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);
//获取size
int STSize(ST* pst);

🌏2.2初始化：

对于初始化有两种写法，可不要小看这两种，对后面的代码每种都有每种的情况所以要分情况写。

💫2.2.1第一种代码：

void STInit(ST* pst)
{
  assert(pst);//判空不然为空就需要传二级指针或者返回值
  pst->a = NULL;
  pst->top = -1;
  pst->capacity = 0;
}

💫2.2.2流程图：

💫2.2.3第二种代码：

void STInit(ST* pst)
{
  assert(pst);//判空不然为空就需要传二级指针或者返回值
  pst->a = NULL;
  pst->top = 0;
  pst->capacity = 0;
}

💫2.2.4流程图：

总结：两种的区别就在于top指向哪到底是栈顶元素还是栈顶后一个元素，我们选择第二种写法

🌏2.3：释放内存

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

🌏2.4：入栈

void STPush(ST* pst, STDataType x)
{
  if (pst->top == pst->capacity)
  {
    int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
    STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newCapacity);
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    pst->a = tmp;
    pst->capacity = newCapacity;
  }
  pst->a [pst->top ] = x;
  pst->top++;
}

对于初始化第一种扩容要判断pst->top+1 == pst->capacity

🌏2.5：出栈

void STPop(ST* pst)
{
  assert(pst);
  assert(!STEmpty(pst));
  pst->top--;//这里要注意top不能为空
}

🌏2.6：访问栈顶元素

STDataType STTop(ST* pst)
{
  assert(pst);
  assert(!STEmpty(pst));
  return pst->a[pst->top - 1];//当top为空时-1就越界了所以要判空
}

对于初始化第一种写法，返回return pst->a[pst->top ];

🌏2.7：判空

bool STEmpty(ST* pst)
{
  assert(pst);
  return pst->top == 0;
}

🌏2.8：获取元素个数

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

对于初始化第一种获取元素个数要返回return pst->top+1;

🌟二、栈实现完整代码

//Stack.h
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Strack
{
  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);
//获取size
int STSize(ST* pst);
//Stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void STInit(ST* pst)
{
  assert(pst);//判空不然为空就需要传二级指针或者返回值
  pst->a = NULL;
  pst->top = 0;
  pst->capacity = 0;
}
void STDestroy(ST* pst)
{
  assert(pst);
  free(pst->a);
  pst->a = NULL;
  pst->capacity =pst->top = 0;
}
void STPush(ST* pst, STDataType x)
{
  if (pst->top == pst->capacity)
  {
    int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
    STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newCapacity);
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    pst->a = tmp;
    pst->capacity = newCapacity;
  }
  pst->a [pst->top ] = x;
  pst->top++;
}
void STPop(ST* pst)
{
  assert(pst);
  assert(!STEmpty(pst));
  pst->top--;//这里要注意top不能为空
}
STDataType STTop(ST* pst)
{
  assert(pst);
  assert(!STEmpty(pst));
  return pst->a[pst->top-1 ];
}
bool STEmpty(ST* pst)
{
  assert(pst);
  return pst->top == 0;
}
int STSize(ST* pst)
{
  assert(pst);
  return pst->top;
}
//Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void  TestStack()
{
  ST st;
  STInit(&st);
  STPush(&st, 1);
  STPush(&st, 2);
  printf("%d ", STTop(&st));
  STPop(&st);
  STPush(&st, 3);
  STPush(&st, 4);
  while (!STEmpty(&st))
  {
    printf("%d ", STTop(&st));
    STPop(&st);
  }
  STDestroy(&st);
}
int main()
{
  TestStack();
  return 0;
}

😽总结

😽Ending,今天的栈和队列(上)的内容就到此结束啦~，如果后续想了解更多，就请关注我吧。