数据结构之“栈”（全方位认识）

🌹个人主页🌹：喜欢草莓熊的bear

🌹专栏🌹：数据结构

前言

栈是一种数据结构，具有" 后进先出 "的特点或者也可见说是 ” 先进后出 “。大家一起加油吧冲冲冲！！

前言

一、栈

1.1栈的概念和结构

1.2栈的实现

1.2.1栈的结构体定义

1.2.2初始化和销毁

1.2.3入栈

1.2.4出栈

1.2.5获取栈顶元素

1.2.6获取栈中的有效个数

1.2.7判空

1.3 代码测试

1.4 头文件

总结

一、栈

1.1栈的概念和结构

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

这个栈的数据结构在我们生活中很像羽毛球桶

压栈：栈的插入操作叫做进栈 / 压栈 / 入栈， 入数据在栈顶 。

出栈：栈的删除操作叫做出栈。 出数据也在栈顶 。

除了" 先进后出 "这个特点还有" 入数据和出数据都在栈顶 "

下面是我画的简易图帮助大家理解栈是一个怎么样的数据结构。

1.2栈的实现

栈的实现一般可以使用 数组或者链表实现 ，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

我们这里实现的是动态栈的结构，因为静态栈实际中一般运用不到。

先给大家看一下栈的结构体定义和一些功能。

//静态栈
typedef int STDataType;
#define N 10
typedef struct Stack
{
 STDataType _a[N];
 int _top; // 栈顶
}Stack;


typedef int STDataType;
//动态栈
typedef struct Stack
{
	STDataType* a;
	int top;//这里的top和顺序表的size相似的都是指有效元素的下一个数据。
	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);

1.2.1栈的结构体定义

因为我们这次实现的栈是基于数组实现的，我们就可以参考顺序表的结构体定义来改进。

我们了解的栈的定义发现，栈顶元素一直有被提及。我们要定义栈顶，其次我们定义数组，但是为什么我们这边是用指针呢？其实这里数组等价于指针的，在学习指针的时候我们学习过 a[i] == *(p+i)所以我们就像理解指针那一样的思路就可以了。还有就是结构体里面定义指针动态内存管理、高效的内存管理、还方便栈的各种操作。这边提到了内存，也要定义一个数来计算是否满了。

结构体定义如下：一个指针 STDataType *a、一个栈顶元素下标的下一个元素（这里的top和顺序表的size相似的都是指有效元素的下一个数据，当作顺序表的size来理解这样更容易想通。）、一个计入内存大小的 capacity。

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;//这里的top和顺序表的size相似的都是指有效元素的下一个数据。
	int capacity;
}ST;

1.2.2初始化和销毁

初始化：最前面就还是需要判断指针是否为空，有指针所以我们要置为NULL，其他的都给赋值为0。如果我们把top定义成栈顶元素的下标，那么我们就要把top赋值为-1了。这样赋值就会显得很奇怪。

销毁：最前面就还是需要判断指针是否为空，我们申请了动态空间当然要释放，所以free必不可少，其他的都给赋值为0。

//栈的初始化和销毁
void STInit(ST* pst)
{
	assert(pst);

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

	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity;
}

1.2.3入栈

数组没有满时：很简单就是把当前栈顶元素往后移动一位在赋值就可以了。

数组满时：我们就要重新申请空间了，什么时候是数组满了呢？就那下面这个图理解，top是5，刚好capacity也是5。这时就满了，所以就要扩容了。就和之前顺序表一样写就可以了。

void STPush(ST* pst, STDataType x)
{
	assert(pst);
	//扩容
	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("ralloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = Newcapacity;
	}
	pst->a[pst->top++] = x;
}

1.2.4出栈

出栈就更简单了，把栈顶指针向前移动一位就可以了。但是除了判别为空指针，还要判别数组里面还有数据吗！assert(pst->top > 0);

void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);

	pst->top--;
}

1.2.5获取栈顶元素

这个功能实现也是非常简单，要牢记top是指向栈顶元素的下一个元素。所以我们要top-1。

//获取栈数据
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	
	return pst->a[pst->top-1];
}

1.2.6获取栈中的有效个数

我们定义的top为0还有计数的作用，所以直接返回top就行了。

int STSize(ST* pst)
{
	assert(pst);

	return pst->top;
}

1.2.7判空

我们直接使用具有计数作用的top判断是否等于0就可以知道是否为空栈了。

//栈的判空
bool STEmpty(ST* pst)
{
	assert(pst);

	return pst->top == 0;
}

1.3 代码测试

#define _CRT_SECURE_NO_WARNINGS
#include"Stack.h"
int main()
{
	ST sa;
	STInit(&sa);
	STPush(&sa, 1);
	STPush(&sa, 3);
	STPush(&sa, 5);
	while (!STEmpty(&sa))
	{
		printf("%d ", STTop(&sa));
		STPop(&sa);
	}
	STDestory(&sa);
}

实现了栈先进后出的特点。

1.4 头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>//bool 类型的头文件
#include<assert.h>

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;//这里的top和顺序表的size相似的都是指有效元素的下一个数据。
	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);