数据结构之栈的超详细讲解

目录

引言

一.栈的概念

二.栈的结构

三.栈的实现

栈结构的实现

栈操作函数的声明

栈中方法的实现

栈的初始化

栈的销毁

入栈

出栈

取栈顶元素

判断栈中是否为空

获取栈中数据个数

四.测试 

代码展示:

结构展示:

五.小结

六.完整代码

Stack.h

Stack.c

text.c

---

引言

这个专题是专门对栈进行详细的讲解,栈这个数据结构其实和之前的顺序表和单链表一样,同样是线性结构,但它的限制更大,如果想看之前单链表和顺序表数据结构的实现,或者是之后的数据结构我现在还没出的,都可以订阅我这个数据结构初阶的专栏--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);
	}
 
}