数据结构-栈的实现-阿里云开发者社区

数据结构-栈的实现

2023-11-24 43

版权

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

简介： 数据结构-栈的实现

1.栈的概念及结构

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

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

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

2.栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

2.1定义一个动态栈

1. typedef int STDataType;
2. 
3. typedef struct Stack
4. {
5.  STDataType* a;
6.  int top;
7.  int capacity;
8. }ST;

2.2栈的初始化

1. void STInit(ST* ps)
2. {
3.  assert(ps);
4.  ps->a = NULL;
5.  ps->top = 0;
6.  ps->capacity = 0;
7. 
8. }

2.3栈的销毁

1. void STDestroy(ST* ps)
2. {
3.  assert(ps);
4.  free(ps->a);
5.  ps->a = NULL;
6.  ps->top = ps->capacity = 0;
7. }

2.4数据进栈

数据进栈的话首先要考虑一下是否需要扩容，所以先判断一下top是否等于capacity，如果满了的话再判断一下capacity是否是第一次扩容，如果是的话则扩容至4，不是的话则扩2倍，再对空间进行扩容，这里巧妙地利用了realloc这个库函数，因为如果需要扩容的这个空间是0，则相当于是malloc，扩容完之后就将数据放进top这个位置，然后再将top++，这样才会使得top一直是栈顶元素的下一个位置。

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

2.5数据出栈

先保证这个栈不是空的，top>0才有数据可以出。出栈直接top--就行了。

1. void STPop(ST* ps, STDataType x)
2. {
3.  assert(ps);
4.  //空
5.  assert(ps->top > 0);
6.  --ps->top;
7. }

2.6栈的数据个数

1. int STSize(ST* ps)
2. {
3.  assert(ps);
4.  return ps->top;
5. }

2.7判断栈是否为空

1. bool STEmpty(ST* ps)
2. {
3.  assert(ps);
4.  return ps->top == 0;
5. }

2.8获取栈顶元素

这里需要注意一下，栈顶元素的位置是top-1.

1. STDataType STTop(ST* ps)
2. {
3.  assert(ps);
4.  assert(ps->top > 0);
5.  return ps->a[ps->top - 1];
6. }

完整代码

Stack.h:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  int top;
  int capacity;
}ST;
void STInit(ST* ps);
void STDestroy(ST* ps);
void STPush(ST* ps,STDataType x);
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
STDataType STTop(ST* ps);

Stack.c:

void STInit(ST* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->top = 0;
  ps->capacity = 0;
}
void STDestroy(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->top = ps->capacity = 0;
}
void STPush(ST* ps, STDataType x)
{
  assert(ps);
  if (ps->top == ps->capacity)
  {
    int newCapacity = ps->capacity == 0 ? 4:ps->capacity * 2;
    STDataType* tmp = (STDataType*) realloc(ps->a, sizeof(STDataType) * newCapacity);
    if (tmp == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity = newCapacity;
   }
  ps->a[ps->top] = x;
  ps->top++;
}
void STPop(ST* ps, STDataType x)
{
  assert(ps);
  //空
  assert(ps->top > 0);
  --ps->top;
}
int STSize(ST* ps)
{
  assert(ps);
  return ps->top;
}
bool STEmpty(ST* ps)
{
  assert(ps);
  return ps->top == 0;
}
STDataType STTop(ST* ps)
{
  assert(ps);
  assert(ps->top > 0);
  return ps->a[ps->top - 1];
}