栈

• • • 栈的概念：
    • • • 栈：
        • 栈顶和栈底
        • 压栈和出栈
    • 栈的实现
    • • • 用结构体自定义一个栈的数据类型
        • 初始化栈
        • 检测栈的容量是否充足(不充足进行扩容)
        • 入栈
        • 检测栈是否为空(为空返回非0结果，不为空返回0）
        • 出栈
        • 获取栈顶元素
        • 获取栈中有效元素个数
        • 销毁栈
    • C语言实现栈的具体代码

栈的概念：

---

栈：

一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作，是操作受到限制的线性表，遵行后进先出LIFO（Last In First Out）的原则。

简单理解就是一个一端封口，另一端没有封口的管子，你往里面放直径与管子的直径相同的球，不管你放多少球，你先取的一定是最后放的球，最里面的球要把前面的球全部取出来才能取到。这个管子里的空间就相当于栈的空间，球就相当于你所要放入栈的数据

---

栈顶和栈底

进行数据插入和删除操作的一端称为栈顶，另一端称为栈底，非空栈中的栈顶指针始终在栈顶元素的下一个位置上，空栈时，栈顶指针和栈底指针指向同一块位置。

借助管子和球的例子，简单理解就是管子封口那里就是栈底，管子中最外层的球的下一个可以存放球的空间，但还没有存放球的位置就是栈顶，不能直接理解为管口就是栈顶。

当管子中没有球时（空栈），栈顶和栈底所指向的位置相等，都指向管子最里面所能存放一个球的空间

---

压栈和出栈

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

入栈gif动画

出栈gif动画

---

栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾部插入数据的代价比较小，可以根据下标直接锁定尾部。
用链表(无头单向非循环链表)在尾部插入数据的代价比较大，需要先遍历一遍才能找到尾部，但也不是不可以，不过尽量用数组比较好一些。

对于栈的实现，有这几个功能，

1. 初始化栈
2. 检测栈的容量是否充足(不充足进行扩容)
3. 入栈
4. 出栈
5. 获取栈顶元素
6. 获取栈中有效元素个数
7. 检测栈是否为空(为空返回非0结果，不为空返回0）
8. 销毁栈

我们将用函数对这些功能进行封装

---

用结构体自定义一个栈的数据类型

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;

因为我们不知道存放在栈中的数据的类型，所以将存放数据的类型用typedef重命名为STDataType，以方便随时更改。（这里我们存放数据的类型是int）

Stack就是我们定义并重命名的栈的数据类型
STDataType* a指向栈用数组存放数据的地方起始位置，即栈底
top是栈顶，也是用来访问数组尾部的下标
capacity是栈的容量，指栈所能容纳多少的数据

---

初始化栈

void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

将栈的地址传过来，对其成员进行初始化

assert(ps)对传过来的地址进行空指针的判断，因为传过来的地址不能为空
ps->a = NULL将指针为空，表明栈的容量为0
ps->top = ps->capacity = 0top记录栈顶位置，capacity记录栈的容量，当容量不足时(也就是ps->top == ps->capacity)进行扩容

---

检测栈的容量是否充足(不充足进行扩容)

void CheckCapacity(Stack* ps)
{
	assert(ps);//传过来的指针不能为空
	
	if (ps->top == ps->capacity)//相等表明容量不足
	{
		//创建一个新的变量，表示新的容量
		int newcapacity = ps->capacity;
		
		//对容量的不足类型判断：
		//第一种是未扩容过的空栈，则扩容为4个空间；
		//第二种是扩容过，但是容量不足，则扩容为原来容量的二倍
		newcapacity = ps->capacity == 0 ? 4 : newcapacity * 2;

		//使用realloc函数对ps->a扩容为sizeof(STDataType) * newcapacity个字节的空间，并把扩容后空间的起始地址保存在tmp
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)//判断是否扩容成功，不成功则停止运行并报错
		{
			perror("realloc fail");
			exit(-1);
		}

		ps->a = tmp;//将扩容后空间的起始地址重新赋予给ps->a
		ps->capacity = newcapacity;//把新的容量记录到ps的成员capacity中
	}
}

未扩容过的空栈

扩容过的栈

注：栈空间起始位置的下标为0

---

入栈

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	CheckCapacity(ps);//检查容量，容量不足则扩容

	ps->a[ps->top] = data;
	ps->top++;
}

动画演示举例，对5个数据进行入栈，且此时的栈为空栈：

---

检测栈是否为空(为空返回非0结果，不为空返回0）

int StackEmpty(Stack* ps)
{
	assert(ps);

	return ps->top == 0;//栈顶指向下标0，则栈为空，返回非零，若不指向下标0，则栈不为空，返回假
}

---

出栈

void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//判断栈是否为空，为空则不能出栈

	ps->top--;
}

将栈顶top-1即可出栈，类似这个动画，但仅仅是出栈，未对出栈的数据进行存储

---

获取栈顶元素

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//判断栈是否为空，为空则不能获取到元素

	ps->top--;//获得栈顶元素的下标
	return ps->a[ps->top];//返回栈顶的元素
}

这一步对出栈的数据进行了返回，可以进行存储出栈返回的数据

---

获取栈中有效元素个数

int StackSize(Stack* ps)
{
	assert(ps);

	return ps->top;
}

把栈顶top的存储的下标返回，可获得栈中元素的个数

---

销毁栈

void StackDestroy(Stack* ps)
{
	assert(ps);

	free(ps->a);//free函数可以将从堆区开辟的空间释放，但不能反复释放，所以需要释放后置为空指针，防止再次释放
	ps->a = NULL;//置为NULL，防止重复释放堆区开辟的空间
	ps->top = ps->capacity = 0;//空间释放，栈的容量为0
}

---

C语言实现栈的具体代码

//Stack.h

#pragma once
#include<stdlib.h>
#include<assert.h>
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;

// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);

//Stack.c

#define _CRT_SECURE_NO_WARNINGS

#include "Stack.h"

void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = ps->capacity = 0;

}

void CheckCapacity(Stack* ps)
{
	assert(ps);//传过来的指针不能为空
	
	if (ps->top == ps->capacity)//相等表明容量不足
	{
		//创建一个新的变量，表示新的容量
		int newcapacity = ps->capacity;
		
		//对容量的不足类型判断：
		//第一种是未扩容过的空栈，则扩容为4个空间；
		//第二种是扩容过，但是容量不足，则扩容为原来容量的二倍
		newcapacity = ps->capacity == 0 ? 4 : newcapacity * 2;

		//使用realloc函数对ps->a扩容为sizeof(STDataType) * newcapacity个字节的空间，并把扩容后空间的起始地址保存在tmp
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)//判断是否扩容成功，不成功则停止运行并报错
		{
			perror("realloc fail");
			exit(-1);
		}

		ps->a = tmp;//将扩容后空间的起始地址重新赋予给ps->a
		ps->capacity = newcapacity;//把新的容量记录到ps的成员capacity中
	}
}

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
 	CheckCapacity(ps);

	ps->a[ps->top] = data;
	ps->top++;
}

void StackDestroy(Stack* ps)
{
	assert(ps);

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

void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	ps->top--;
}

int StackEmpty(Stack* ps)
{
	assert(ps);

	return ps->top == 0;
}

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	ps->top--;
	return ps->a[ps->top];
}

int StackSize(Stack* ps)
{
	assert(ps);

	return ps->top;
}