数据结构与算法：栈

博客大纲

数据结构与算法：栈

栈的定义

定义：

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

此处其实可以把栈理解为一个只有一端开口的盒子，当我们放一个球进去，球一定会落在这个盒子的顶部，当我们从盒子里取球，也只能取最上面的球。

在这个结构中，我们把“封口”的一端称为栈底，“开口”的一端称为栈顶。

此博客就是用C语言来实现这样一个栈结构。

栈

结构分析

栈只是一种数据结构，我们可以用非常多的方式去实现它，可以用数组来承载元素，用顺序表来承载元素，用链表来承载元素等等。

此博客使用的方式则是动态内存管理，开辟一块连续的内存来放数据，本质上来说是数组形式的栈，但是可以动态开辟空间，会更加灵活。

对于整个栈结构，我们用一个结构体来承载其所有信息，此处我们需要：

1.维护动态内存的指针成员a

2.标识栈顶位置的成员top

3.计算当前栈空间大小的成员capacity，（以能承载几个元素为单位）

这相当于是一个栈的“身份证”，体现了栈的一部分信息，但不是栈的实体。真正的栈是a指向的那一块动态内存。

结构体如下：

typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  int top;//标识栈顶位置
  int capacity;//当前栈结构总空间大小
}ST;

数据结构没有对栈的元素类型规定的，也就是说栈的元素可以是任意类型的。所以我们此处用typedef来定义一个STDataType，他表示当前栈结构适用的类型是什么，当我们需要使用这个栈结构来存储其它类型的数据时，只需要修改此处的typedef即可。

栈的名称为stack，此处我们将其typedef为ST，方便后续使用。

栈的实现结构示意图如下：

栈的初始化

对栈的初始化，就是对其结构体初始化。我们在栈的结构体内有一个指针，一个top指向栈顶，一个capacity标记空间大小。在初始化的时候，由于我们只是给这个栈注册了一个“身份证”，此时栈的动态内存还没有开辟出来，所以a指针也就无处可指，所以要将a置空，而由于没有空间，那么元素个数top与空间大小a毫无疑问就初始化为0了。

传参分析：

由于我们只有这个栈的结构体，我们传参也就只能传入结构体了。但是我们不论是在初始化，还是在后续使用这个栈的时候，都难免需要改动这个结构体的信息。所以此处我们要传址调用，不然无法对这个结构体内容进行修改。ST表示栈，我们就用pst来表示结构体的地址了。

代码如下:

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

栈顶插入接口

由于栈的定义，我们只能对栈的顶部进行的插入与删除。故对元素改动的接口只有栈顶插入与栈顶删除，我们先实现栈顶的插入。

空间是否充足的判定：

既然要插入元素，那必然会涉及到，空间够不够的问题。所以我们在插入空间之前，需要判断空间是否充足，如果不足，就需要扩容。

那么什么时候空间就满了呢？

我们的top标记当前栈中有几个元素，而capacity标记当前栈最多容纳几个元素。那么当capacity == top的时候，就是栈满了。

我们先展示这个判断的代码，再解析细节。

判断空间是否充足与开辟空间的代码：

if (pst->top == pst->capacity)
  {
    int newcapacity = pst->capacity == 0 ? pst->capacity * 2 : 4;
    STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
    if (tmp == NULL)
    {
      perror("realloc fail");
      return ;
    }
    pst->a = tmp;
    pst->capacity = newcapacity;
  }

首先利用if语句，一旦capacity = top，说明当前的元素刚好占满了空间；或者capacity = top =0，说明此时还没有开辟空间给顺序表。

int newcapacity = pst->capacity ? pst->capacity * 2 : 4;

为了实现第一次开辟内存与后续增加内存的统一，我们利用了三目操作符，当问号前的条件(pst->capacity == 0 )成立说明此次为第一次开辟内存，程序指向冒号前的值赋给NewCapacity，即(int NewCapacity = 4)，相当于给栈分配四个内存空间；当条件不成立说明此次不是第一次开辟内存了，我们将原先的内存乘二，即(int NewCapacity = 2 * pst->capacity)。这样就可以让内存变成原来的两倍。

上述操作还没有真正实现内存的开辟，只是在决定要开辟多少内存，第三条语句才是内存开辟的语句：

STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);

realloc的返回值有两种情况，1.内存开辟成功，返回新的内存的地址 2.内存开辟失败，返回NULL

不妨设想，这里的内存一旦开辟失败，如果直接用a接收这个NULL，那么我们的整个栈的数据就无法访问了，还会出现内存泄漏问题。

为了防止这种情况，我们用中间值tmp接收返回值，并后续判断其是否为NULL，如果为NULL说明开辟失败。利用perror函数报错；如果不为NULL，说明开辟成功，此时才可以将地址传给a。

当内存开辟好后，内存的大小就发生了改变，此时capacity要得到新的内存大小(pst->capacity = NewCapacity;)

插入元素

我们要在栈顶插入元素，那就需要找到当前栈顶在哪里，由于我们存了一个top，我们就可以利用top来找到栈顶。

这里的a指向的是动态内存的第一个元素的地址，而我们需要访问其它地址，就需要指针偏移量了，第一个元素就是a[0],第n的元素就是a[n-1]。top代表当前有top个元素，那最后一个元素的下标就是top-1。所以我们插入新元素，只要在下标为top的位置插入即可。即：pst->a[pst->top] = x;。由于我们插入了一个元素，那么此时top就要加一，来表示元素增加了一个。

最终代码如下：

//栈顶插入
void STPush(ST* pst, STDataType x)
{
  assert(pst);
  if (pst->top == pst->capacity)
  {
    int newcapacity = pst->capacity ? pst->capacity * 2 : 4;
    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++;
}

栈顶删除接口

想要删除栈顶的元素，其实只需要将top-1即可，我利用一张图解释，如下：

在一开始我们的栈上有6个元素，然后我们在删除栈顶元素的过程中，没有真的把6给删掉，只是将top后移了一位。为什么可以这样做？我们从栈顶插入与读取栈顶来分析：

读取栈顶：

此时如果我们从栈顶取出元素，其实就是在偏移量为a[top-1]的位置取出元素，由于top退了一位，此时取出的栈顶就已经是5了。

栈顶插入：

此时如果我们在栈顶插入一个元素，无非就是直接将a[top]变为目标元素。比如我们要再插入一个10，由于top退了一位，此时新元素刚好把6给覆盖掉了。

可以发现，这样操作，对以上两个操作都没有造成影响，所以我们直接top–是可行的。

断言分析：

由于我们进行了删除操作，在删除操作前，就要确保目前有元素可以删除。top标识了当前元素个数，所以只要top>0，就说明栈中还有元素。所以我们需要对top进行断言：assert(pst->top > 0)

代码如下：

//栈顶删除
void STPop(ST* pst)
{
  assert(pst);
  assert(pst->top > 0);
  pst->top--;
}

读取栈顶接口

由于我们有top标识栈顶，所以要访问栈顶元素，只要利用top来充当a的偏移量即可。

第n给元素的下标为n-1，栈顶就是第top个元素，那它的下标就是top-1。

代码如下：

//读取栈顶
STDataType STTop(ST* pst) 
{
  return pst->a[pst->top - 1];
}

判断栈是否为空

由于top就是当前元素个数，所以判断栈是否为空，就是判断top是否为0。

此处我们有三种不同的写法，我们一一分析：

写法1：

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

这种写法是最直观的，非常明显的看出来：top为0就返回ture（真的为空），否则就返回false（假的为空）。

写法2：

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

这种写法利用了？：三目操作符。相比于写法1确实简介不少。但是这两种写法都有些拐弯抹角了，我们隆重介绍第三种写法：

写法3：

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

我们直接将pst->top == 0的表达式的返回值作为函数的返回值。由于栈为空与top为0，在真假上是一致的。所以只要top = 0为真，就返回真，否则就返回假。

栈的销毁接口

想要销毁这个栈，无非就是将a指向的空间释放掉。这块空间释放后，所有数据也就会跟着销毁。那么此时的top和capacity就要一起变为0。而a由于被释放，变为了野指针，也要进行置空。

代码如下：

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

栈的访问

我们的接口已经实现完了，但是好像还缺少一个遍历整个栈中的元素的接口。此处并非难以实现，只是如果实现了这样一个接口，不就破坏了栈的定义吗？在我们需要访问所有元素时，就要每访问一个栈顶元素，就删除删除一次栈顶，这样下一次访问栈顶才能访问到下一个元素。

比如这样：

while (!STEmpty(&s))
{
  printf("%d ", STTop(&s));
  STPop(&s);
}

只要栈不为空，就输出当前的栈顶，然后将栈顶删除，一直循环到栈中没有元素为止。

代码展示

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* pst);
void STDestroy(ST* pst);
//栈顶插入
void STPush(ST* pst, STDataType x);
//栈顶删除
void STPop(ST* pst);
STDataType STTop(ST* pst);
bool STEmpty(ST* pst);

stack.c

#include "stack.h"
void STInit(ST* pst)
{
  assert(pst);
  pst->a = NULL;
  pst->capacity = 0;
  pst->top = 0;
}
void STDestroy(ST* pst)
{
  assert(pst);
  free(pst->a);
  pst->a = NULL;
  pst->top = pst->capacity = 0;
}
//栈顶插入
void STPush(ST* pst, STDataType x)
{
  assert(pst);
  if (pst->top == pst->capacity)
  {
    int newcapacity = pst->capacity ? pst->capacity * 2 : 4;
    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(pst->top > 0);
  pst->top--;
}
//找到栈顶
STDataType STTop(ST* pst) 
{
  return pst->a[pst->top - 1];
}
//判空
bool STEmpty(ST* pst)
{
  assert(pst);
  return pst->top == 0;
}

test.c

#include "stack.h"
int main()
{
  ST s;
  STInit(&s);
  STPush(&s, 1);
  STPush(&s, 2);
  STPush(&s, 3);
  STPush(&s, 4);
  STPush(&s, 5);
  while (!STEmpty(&s))
  {
    printf("%d ", STTop(&s));
    STPop(&s);
  }
  printf("\n");
  return 0;
}

博客制作不易，还请留下一个免费的赞！

有问题欢迎指出，博主非常喜欢讨论问题！