目录
- 1、栈的概念
- 2、栈的数组构建方法
- 2.1 前言
- 2.2 正文
- 2.2.1 栈的初始化
- 2.2.2 栈的销毁
- 2.2.3 压栈
- 2.2.4 出栈
- 2.2.5 取栈顶数据
- 2.2.6 对栈内数组判断是否为空
- 2.2.7 栈内数据的数量
- 3、完整代码展示
- 4、结语
1、栈的概念
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。
通俗一点的理解就是,栈就像是一个羽毛球筒一样,先放进去的羽毛球,最后才能拿出来,反而后放进去的可以先拿出来,也就是我们上面提到的LIFO:Last In First Out。
而栈我们可以通过顺序表来构建,也可以通过链表来构建,本文讲述的是顺序表构建内容。
下面进入正文。
2、栈的数组构建方法
2.1 前言
构建栈的需求有三个文件,包括Stact.c(用来书写逻辑的内容)、Stact.h(用来书写逻辑的声明)、test.c(用来测试我们所书写的代码)。
2.2 正文
我们先将我们的逻辑申明书写完成,这样后面的内容我们就可以按照逻辑声明的顺序一步一步完成。
首先我们需要有一个顺序表如下,在书写的时候我们就直接将它重命名,以便我们后面代码的书写。
typedef struct Stact
{
int* a;
int top;
int capacity;
}ST,*pST;//分别为结构体类型名,和结构体指针
书写完会发现,我们结构体中的数组类型已经被定死了,如果我们以后想要往栈中存储不同类型的数据,需要一个一个在代码中查找 int 然后修改,十分麻烦,不如直接将类型重命名为一个新的名字,之后的代码中如果需要修改,则直接修改重命名的内容即可。
typedef int STDataType;
typedef struct Stact
{
STDataType* a;
int top;
int capacity;
}ST,*pST;//分别为结构体类型名,和结构体指针
在此之后,我们则需要在书写几个函数来执行我们的初始化,压栈,出栈,等操作。
代码如下:
//初始化
void STInit(pST pst);
//顺序表的销毁
void STDestroy(pST pst);
//压栈
void STPush(pST pst, STDataType x);
//出栈
void STPop(pST pst);
//取栈顶数据
STDataType STTop(pST pst);
//栈判空
bool STEmpty(pST pst);
//栈的大小
int STSize(pST pst);
下面我们对应其顺序一步一步书写
2.2.1 栈的初始化
对于栈的初始化,代码如下:
void STInit(pST pst)
{
assert(pst);
pst->a = NULL;
//让栈顶指向下一个位置
pst->top = 0;
//让栈顶指向当前位置
//pst->top = -1;
pst->capacity = 0;
}
我们可以看到代码块中书写了两种方法,一种是让栈顶指向下一个位置,一种是让栈顶指向当前位置,两者皆可,本文采用的是令栈顶指向下一个位置的方法。
2.2.2 栈的销毁
对于栈的销毁,代码如下:
void STDestroy(pST pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = pst->capacity = 0;
}
2.2.3 压栈
对于数据的压栈,我们在开头就需要判断一下数组的空间是否足够,或者数组空间是否为NULL,如果不足或为NULL,我们需要对其进行空间开辟,使用 realloc 函数进行,其中我们知道本文采用的方法是将 top 指向下一个位置所处的下表,故代码如下:
void STPush(pST pst, STDataType x)
{
if (pst->top == pst->capacity)
{
int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("STPush:realloc");
return;
}
pst->a = tmp;
}
pst->a[pst->top] = x;
pst->top++;
}
2.2.4 出栈
对于出栈,就十分容易了,我们每一次压栈时使用的都是 top 来定位栈顶的位置,这里我们可以直接进行 top-- 操作,此时不用对栈顶的内容改变,下一次入栈时便会直接覆盖此时需要删除的内容。
代码如下
void STPop(pST pst)
{
assert(pst);
assert(pst->top > 0);
pst->top--;
}
2.2.5 取栈顶数据
取栈顶的数据代码如下:
STDataType STTop(pST pst)
{
assert(pst);
assert(pst->top > 0);
return pst->a[pst->top - 1];
}
2.2.6 对栈内数组判断是否为空
判空代码如下:
bool STEmpty(pST pst)
{
assert(pst);
return pst->top == 0;
}
2.2.7 栈内数据的数量
查看栈内数据的数量的代码如下:
int STSize(pST pst)
{
assert(pst);
return pst->top;
}
3、完整代码展示
Stact.h:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int STDataType;
typedef struct Stact
{
STDataType* a;
int top;
int capacity;
}ST,*pST;
//初始化
void STInit(pST pst);
//顺序表的销毁
void STDestroy(pST pst);
//压栈
void STPush(pST pst, STDataType x);
//出栈
void STPop(pST pst);
//取栈顶数据
STDataType STTop(pST pst);
//栈判空
bool STEmpty(pST pst);
//栈的大小
int STSize(pST pst);
Stact.c:
#include "Stact.h"
//初始化
void STInit(pST pst)
{
assert(pst);
pst->a = NULL;
//让栈顶指向下一个位置
pst->top = 0;
//让栈顶指向当前位置
//pst->top = -1;
pst->capacity = 0;
}
//顺序表的销毁
void STDestroy(pST pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = pst->capacity = 0;
}
//压栈
void STPush(pST pst, STDataType x)
{
if (pst->top == pst->capacity)
{
int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("STPush:realloc");
return;
}
pst->a = tmp;
}
pst->a[pst->top] = x;
pst->top++;
}
//出栈
void STPop(pST pst)
{
assert(pst);
assert(pst->top > 0);
pst->top--;
}
//取栈顶数据
STDataType STTop(pST pst)
{
assert(pst);
assert(pst->top > 0);
return pst->a[pst->top - 1];
}
//栈判空
bool STEmpty(pST pst)
{
assert(pst);
return pst->top == 0;
}
//栈的大小
int STSize(pST pst)
{
assert(pst);
return pst->top;
}
test.c:
#include "Stact.h"
int main()
{
// 入栈:1 2 3 4
// 出栈:4 3 2 1 / 2 4 3 1
ST s;
STInit(&s);
STPush(&s, 1);
STPush(&s, 2);
printf("%d ", STTop(&s));
STPop(&s);
STPush(&s, 3);
STPush(&s, 4);
while (!STEmpty(&s))
{
printf("%d ", STTop(&s));
STPop(&s);
}
STDestroy(&s);
}
4、结语
十分感谢您观看我的原创文章。
本文主要用于个人学习和知识分享,学习路漫漫,如有错误,感谢指正。
如需引用,注明地址。