数据结构之栈（Stack）

数据结构之栈

• 前言（两个栈）
• 一、栈的概念
• • 1.栈的认识
  • 2.栈的分类
• 二、栈的功能实现
• • 1.代码实现前的准备：
  • 2.栈的功能实现（数组栈）
  • • 2.1 栈的结构体定义
    • 2.2 栈结构体的初始化
    • 2.3 数据入栈
    • 2.4 数据出栈
    • 2.5 获取栈顶元素
    • 2.5 判断栈是否为空
    • 2.5 销毁栈
• 三、代码汇总
• • 1. Stack.h 头文件
  • 2. Stack.c 源文件
  • 3. StackTest.c 源文件
• 四、总结

前言（两个栈）

在学习数据结构的的栈之前，我相信很多老铁都在学C语言的时候听过栈。 C语言中我们学习的是操作系统中的栈，这里的栈是内存分区。

内存中有栈区，堆区，全局（静态）区，常量区，代码区五大区。

栈区：存放局部变量，形参，返回值。包括函数调用也会在栈区建立栈帧。

堆区：存放动态分配的空间如malloc()和free()函数。

全局(静态)区：存放全局变量和静态变量。

常量区：存放字符串、数字、const修饰的全局变量等常量。

代码区：存放程序的可执行指令和函数二进制代码，通常为只读区域。

以上就是内存中的栈的概念。但今天小羊主要给老铁介绍的是数据结构中栈的概念。

一、栈的概念

1.栈的认识

数据结构中的栈是一种特殊的线性表。==栈在逻辑上是线性的，但在物理空间上不一定是线性的。==小羊会在栈的分类部分解释。

栈中的数据元遵守后进先出LIFO（Last In First Out）的原则。就像给手枪弹匣装子弹，最先填装的那一刻，最后才会被激发。 最后填装的那一颗，第一个被激发。

栈只能在固定的一端进行进行数据的插入和删除操作。进行操作的这一端我们叫栈顶，另一端我们叫栈底。

栈对数据的插入和删除操作分别叫做：进栈和出栈。 进栈：栈的插入数据操作叫做进栈/压栈/入栈，入数据在栈顶。 出栈：出栈：栈的删除操作叫做出栈。出数据也在栈顶。

栈顶和栈底以及出栈和入栈可以参考下图。

2.栈的分类

小羊在栈的认识里说了一句话：栈在逻辑上是线性的，但在物理空间上不一定是线性的。

逻辑上线性：

物理空间上不一定线性：

这两种实现方式相对而言数组实现栈结构更优一些。因为数组在尾上插入数据的代价比较小且cpu命中率高.虽然需要realloc函数扩容但是可以接受，并不是要经常扩容。 小羊接下来会以数组栈为例，给各位老铁实现栈数据结构。

二、栈的功能实现

1.代码实现前的准备：

如果看来小羊前面的数据结构文章，就会发现每篇文章都有这样下面一段话。

为了代码规范，我不建议老铁们把所有内容都塞进一个.c源文件里。这样对于调试，修改，代码可读性都不清晰。

这边建议老铁们建立一个头文件，和两个源文件。

头文件：SLinkedList.h 负责定义单链表节点的结构体和函数声明等这些需要不断被调用的内容。 源文件1：SLinkedList.c 负责实现各种功能函数的封装实现。 源文件2：Test.c 用于测试各个功能函数是否可以正常运行。

小Tips：建议老铁们写一个功能就测试一下。别等到写了一大段代码再去测试，调试。到最后爆了一堆错，看起来非常头疼。

2.栈的功能实现（数组栈）

2.1 栈的结构体定义

细心的老铁们会发现，其实栈的结构体跟前面小羊介绍的顺序表时候构建的结构体大差不差。事实也确实如此。

我们可以看到数组为元素下表是4, top是栈顶的标识是尾元素的下一个下标是5. 栈结构体构建代码如下：

typedef int STDatatype;
typedef struct Stack
{
STDatatype* a;
int top;
int capacity;
}ST;

2.2 栈结构体的初始化

小羊的理解是：初始化的本质是赋值。 我们这里对结构体初始化，就是对结构体的成员赋值。 这也意味着我们会修改结构体，如果要修改结构体那么传址调用，我们传参就应该传结构体的地址。传值调用的话形参是实参的拷贝，对形参的修改不影响实参。

void STInit(ST* pst)
{
assert(pst); //确保栈已经创建
pst->a = NULL;
pst->top = 0; //可以看作size=0,数组中还没有元素，数组是空的
pst->capacity = 0;
}

2.3 数据入栈

数据入栈，就是在栈顶插入数据。无论是数组栈还是链表栈，在栈顶插入数据对应的操作就是尾插。

void STPush(ST* pst, STDatatype x)
{
assert(pst);
//扩容:
if (pst->top == pst->capacity)
{
//计算要扩容的大小为newcapacity个数组元素类型
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; //把开辟空间的地址赋给a
pst->capacity = newcapacity;
}
//数据压栈(入栈)
pst->a[pst->top] = x;
pst->top++;
}

2.4 数据出栈

数据出栈，就是在栈顶删除数据。在栈顶插入数据对应的操作就是尾删。

分析思路：跟顺序表尾删一样，我们不用一定要删除掉数据。本来数组大小是【0，top】，我们把最后一个元素赶出数组的范围，数组大小变为【0，top-1】.也是实现了把数据从数组中删除。

分析边界：首先栈结构体要已经创建，不得为空；其次栈结构体内部的数组不得为空，不然我们删除啥。

void STPop(ST* pst)
{
assert(pst); //确保栈已经创建
assert(pst->top > 0); //保证数组里面有数据
pst->top—;
}

2.5 获取栈顶元素

分析思路：我们已知栈结构体的top成员,是数组尾元素的下一个下标. 数组尾元素就是当前的栈顶元素.

分析边界：首先栈结构体要已经创建，不得为空；其次栈结构体内部的数组不得为空，不然根本没有栈顶元素.

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

2.5 判断栈是否为空

分析思路：判断栈为空本质是判断栈里的数组是否是空.

实现: 利用布尔值, 为空返回true, 不为空返回false. 下面代码块中给出两种方法.

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

2.5 销毁栈

栈的销毁本质上是释放掉给数组通过realloc开辟或扩容的空间, 并让栈结构体回归初始状态.

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

三、代码汇总

1. Stack.h 头文件

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

typedef int STDatatype; //数组里的数据类型重定义为 STDatatype

typedef struct Stack
{
STDatatype* a;
int top; //与顺序表不同的是,我们这里没有取名叫size,而是top, 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);

// 获取栈中有效元素个数
int STSize(ST* pst);

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool STEmpty(ST* pst);

2. Stack.c 源文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"

//初始化函数封装
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
pst->capacity = 0;
pst->top = 0; //可以理解为a[top-1]是现存的数组栈顶元素, 运维数组元素是从下标0开始, top表示元素总个数
}

//数据压栈函数封装,(栈顶插入)
void STPush(ST* pst, STDatatype x)
{
assert(pst);

//此为初始化pst->top=0;
//扩容:
if (pst->top == pst->capacity)
{
//计算要扩容的大小为newcapacity个数组元素类型
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; //我们开辟空间是为了存储数据,站结构体里的指针a相当于数组首元素地址, 把开辟空间的地址赋给a
pst->capacity = newcapacity;
}
//数据压栈(入栈)
pst->a[pst->top] = x;
pst->top++;

}

//数据出栈函数封装,(栈顶删除)
void STPop(ST* pst)
{
assert(pst);
//top初始化为0,指向栈顶元素的下一个元素. 暴力检查数组栈是否空了(断言)
assert(pst->top > 0);
pst->top—;
}

// 获取栈顶元素函数封装
STDatatype STTop(ST* pst)
{
assert(pst);
//top初始化为0,返回栈顶元素
assert(pst->top > 0);
return pst->a[pst->top–1];

////top初始化为-1,返回栈顶元素
//assert(pst->top > -1);
//return pst->a[pst->top];
}

// 获取栈中有效元素个数
int STSize(ST* pst)
{
assert(pst);
return pst->top; //栈顶元素的下标为top-1,栈的数据总个数就是top个
}

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool STEmpty(ST* pst)
{
/*if (pst->top == 0)
{
return true;
}
else
{
return false;
}*/
return pst->top == 0;
}

3. StackTest.c 源文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"

void Test1()
{
ST s;
STInit(&s);
//数据入栈
STPush(&s, 1);
STPush(&s, 2);
STPush(&s, 3);
STPush(&s, 4);
STPush(&s, 5);

//不需要写打印函数,因为STTop会返回栈顶元素
while (!STEmpty(&s)) //栈数组不为空
{
printf("%d ", STTop(&s)); //后入先出,访问元素只能访问栈顶
STPop(&s); //访问完栈顶的元素,像访问下一个怎么操作? 先pop弹出栈,再访问新的栈顶元素
}
printf("\\n");
}

void Test2()
{
ST s;
STInit(&s);
//数据入栈
STPush(&s, 1);
STPush(&s, 2);

//3虽然不是最后输入的但是是最先出栈的, 因为后续数据还没入栈的时候,3是栈顶元素,我们此时就让3出栈了
STPush(&s, 3);
printf("%d ", STTop(&s));
STPop(&s);

//4也比最后输入的5先出栈, 因为后续数据5还没入栈的时候,4是栈顶元素,我们此时就让4出栈了
STPush(&s, 4);
printf("%d ", STTop(&s));
STPop(&s);

STPush(&s, 5);

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

int main()
{
//Test1();
Test2(); //入栈顺序与出栈顺序是一对多的关系,入栈顺序只有一种,(出栈顺序是对于此时栈内的数据而言是先入后出.)
return 0;
}

四、总结

今天这一章节,我给各位老铁从栈的定义,到栈的原理,再到栈的代码实现进行介绍. 觉得小羊写的不错的可以点点赞和关注. 欢迎老铁在评论区讨论.互三必回.