目录
引言
这个专题是专门对栈进行详细的讲解,栈这个数据结构其实和之前的顺序表和单链表一样,同样是线性结构,但它的限制更大,如果想看之前单链表和顺序表数据结构的实现,或者是之后的数据结构我现在还没出的,都可以订阅我这个数据结构初阶的专栏--http://t.csdnimg.cn/sz4xS.好了,话不多说,点赞关注我们开始!
一.栈的概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
栈这个数据结构可以总结为四个字:后进先出
二.栈的结构
因为栈也是一种线性结构,所以并不复杂,如下图所示:
栈这种结构在我们生活中其实并不少见,比如我们打羽毛球用的羽毛球桶,装子弹的弹匣,都满足后进先出的一个特性.
三.栈的实现
栈结构的实现
我们可以用三种方法实现栈这个结构:
方法一:
我们用双向链表构建栈,如下图所示:
这样做的好处是:双向链表能很轻松的寻找前面的节点
方法二:
我们用单链表构建栈,如下图所示:
我们用单链表构建栈时,我们入栈时需要头插,因为单链表找前面的节点是不好找的
方法三:
我们用动态数组构建栈:
这个方法就类似于基于动态数组构建顺序表
那么这三种方法选择哪一种呢?
首先因为单链表的原因,我们先把双向链表PASS掉
接下来就在单链表和动态数组中选择
其实两者相差不大,但由于动态数组具有元素高效率存储,所以这里选择动态数组实现栈
代码展示:
//栈的结构
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;注意:这里的STDataType和之前的链表和顺序表一样,方便后面进行类型的替换
a时我们的动态数组
top是我们的栈顶指针
capacity是我们的空间容量
栈操作函数的声明
对于线性表来说,操作函数大同小异,所以栈的操作函数其实跟单链表和顺序表差不多
下面便是操作函数的声明:
//函数的声明
//初始化和销毁
void STInit(ST* pst);
void STDestory(ST* pst);
//入栈和出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
//取栈顶元素
STDataType STTop(ST* pst);
//判空
bool STEmpty(ST* pst);
//获取数据个数
int STSize(ST* pst);栈中方法的实现
栈的初始化
注意:
栈这里的初始化分为两种方式:
1.top指向-1,top指向栈顶元素,如下图所示:
注意:这里的top不能指向为0,因为这样的话,当top指为0时,不知道是否含有数据
2.top指向0,top指向栈顶元素的下一位,如下图所示:
这里我用了第二种,因为这里的top即为元素个数,对于后面的操作会方便一点.
//初始化和销毁
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
//top指向栈顶数据的下一个位置
pst->top = 0;
//top指向栈顶数据
//pst->top = -1;
pst->capacity = 0;
}栈的销毁
void STDestory(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = pst->capacity = 0;
}注意最后要将top和capacity置为0
入栈
和顺序表的插入数据类似,首先进行断言处理,再看空间是否够用,不够用就进行两倍扩容.
注意:这里使用了三目操作符,因为我们初始化capacity为0,两倍扩容之后还是为0,所以当它为0时,直接初始化为4,或者其他值.
void STPush(ST* pst, STDataType x)
{
assert(pst);
//扩容
if (pst->top == pst->capacity)
{
int newcapcacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, newcapcacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail!");
return;
}
pst->a = tmp;
pst->capacity = newcapcacity;
}
pst->a[pst->top] = x;
pst->top++;
}出栈
这个很简单,只需top--即可
void STPop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
pst->top--;
}取栈顶元素
注意:这里需要额外对top进行判空处理
//取栈顶元素
STDataType STTop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
return pst->a[pst->top - 1];
}判断栈中是否为空
top即为我们栈中元素的个数
//判空
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}获取栈中数据个数
//获取数据个数
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}四.测试
我们入栈一些元素,再将它们打印出来.
代码展示:
#include "Stack.h"
int main()
{
ST s;
STInit(&s);
STPush(&s, 1);
STPush(&s, 2);
STPush(&s, 3);
STPush(&s, 4);
//遍历栈中的元素
while (!STEmpty(&s))
{
printf("%d ", STTop(&s));
STPop(&s);
}
}结构展示:
后进先出没有问题
五.小结
栈这个数据结构对比顺序表和单链表的实现真的简单了不少,但它的OJ题可不简单,后面我会更新关于栈的经典OJ练习,如果觉得这篇博客对你有帮助的话,一定要点赞关注哦!如果你有任何问题后可以打在评论区,大家一起学习,共同进步!
六.完整代码
Stack.h
#pragma once
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//栈的结构
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
//函数的声明
//初始化和销毁
void STInit(ST* pst);
void STDestory(ST* pst);
//入栈和出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
//取栈顶元素
STDataType STTop(ST* pst);
//判空
bool STEmpty(ST* pst);
//获取数据个数
int STSize(ST* pst);
Stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"
//初始化和销毁
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
//top指向栈顶数据的下一个位置
pst->top = 0;
//top指向栈顶数据
//pst->top = -1;
pst->capacity = 0;
}
void STDestory(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 newcapcacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, newcapcacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail!");
return;
}
pst->a = tmp;
pst->capacity = newcapcacity;
}
pst->a[pst->top] = x;
pst->top++;
}
void STPop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
pst->top--;
}
//取栈顶元素
STDataType STTop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
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;
}text.c
#include "Stack.h"
int main()
{
ST s;
STInit(&s);
STPush(&s, 1);
STPush(&s, 2);
STPush(&s, 3);
STPush(&s, 4);
//遍历栈中的元素
while (!STEmpty(&s))
{
printf("%d ", STTop(&s));
STPop(&s);
}
}