数据结构篇其四---栈：后进先出的魔法世界

前言

栈的学习难度非常简单，前提是如果你学过顺序表和单链表的话，我直接说我的观点了，栈就是有限制的顺序表和单链表。

栈只允许一端进行插入删除。栈去除了各种情况复杂的插入删除，只允许一端插入删除的特性，这一种数据结构在实际应用场景非常有价值。

栈的概念

栈是一种线性表，其中只允许固定的一段进行插入删除元素操作。

其中进行数据插入和删除操作的一端称为栈顶；

另一端称为栈底。

栈中数据遵循一个元素LIFO（Last In Fast Out）,后进先出原则。

栈有一句话概括了它的特点：先进后出，后进先出。

进栈与出栈一图流搞定。

栈的定义

栈分两种存储结构：

1.顺式存储结构，比如前面的顺序表。顺序表可以通过静态数组和动态数组实现。

那么栈的顺式存储结构也能通过静态数组和动态数组实现。这种栈称为数组栈。

2.链式存储结构，比如链表（这里指单链表）。栈也能像单链表那样的结构定义，这种栈称为链表栈。

数组栈（顺序栈）

数组有定长数组和动态数组。

选择数组下标为0为栈底，选择存储有效数据最远的为栈顶。

对于静态数组的栈，不妨我们称做静态（数组）栈。

要素：

1.定长数组。

2.栈顶指针（用于记录当前位置）。

注意：栈顶指针不一定是真的指针，这里可以数数组下标，因为数组在内存中连续存储的特性，用下标也就是在用指针。

对于复杂数据类型，还是离不开结构体。如下：

#define NUM_MAX 100//看情况调整
typedef int STDataType;
typedef struct Stack
{
	STDataType arr[NUM_MAX];//定长数组
	int top;//栈顶指针
}ST;

tip：这里的top其实就是静态顺序表的size，只是换了一个变量名。

这里换成top其实是要养成良好的取名风格，方便后续的学习。 

 后面针对动态数组实现的栈，我们不妨称为动态（数组）栈

要素：

1.栈数据类型的一级指针；用于动态内存分配

2.栈顶指针；（前面解释过，不在解释）

3.容量大小；（动态数组不会记住当前已有的空间大小，需要额外引入变量记录）

总结：用结构体，和动态顺序表一模一样，除了size改了个名叫top。

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

链式栈  

首先选择什么类型链表结构，链表结构合计8种，由于进栈出栈限定在一端操作，单链表就适合。（栈不适合带头结点的单链表）

哪端作为栈顶，另一端作为栈底呢？

由于单链表的单向性且要符合栈的LIFO特性。

头指针指向处为栈顶，尾结点处为栈底。

typedef int STDataType;
typedef struct Stack
{
	struct Stack* next;
	STDataType data;
}ST;

您可能想问，这不就是单链表吗，跟链式栈有什么区别？

不不不，单链表还有一个关键的东西----头指针。

头指针和栈顶指针合二为一了。接下来只要用该结构体实现栈的相关函数，就可以明显区分单链表和链式栈的差别了。

ST* top = NULL;//创建一个链式栈

栈的实现（用动态数组栈实现）

数组栈比链式栈更简单，所以我们优先实现数组栈。

这里出栈进栈等价于顺序表的尾删和尾插，顺序表处理这方面效率是最高的。

显然用顺序栈（数组栈），前排提醒：实现顺序表可以说相当简单。

这里选择数组栈的动态数组的方式实现。

#include<stdio.h>
#include<stdbool.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 STDestroy(ST* pst);

//压栈/进栈/入栈
void STPush(ST* pst,STDataType x);

//出栈
void STPop(ST* pst);

//获取栈顶元素
STDataType STTop(ST* pst);

//判空
bool STEmpty(ST* pst);

//栈上合计多少个元素个数
int STsize(ST* pst);

栈的初始化

void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	//pst->top = -1;//top指向最新插入的数据

	//以这个为例
	pst->top = 0;//top指向当前有效数据的下一个位置。
	pst->capacity = 0;//容量大小

}

栈的销毁 

void STDestroy(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 newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
		STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));//给动态数组开辟空间
		if (tmp == NULL)//判断空间是否开辟失败
		{
			perror("realloc fail");
			return;
		}

		pst->a = tmp;//开辟成功赋值
		pst->capacity = newcapacity;
	}
	pst->a[pst->top++] = x;
}

出栈函数

void STPop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));//空栈不能删除
	pst->top--;//直接改变栈顶即可
}

栈顶元素函数

STDataType STTop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));//空栈没有元素了
	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;//返回当前栈上的元素个数。
}

总源代码

请自行迁移用静态数组和单链表表示栈。

#include<stdio.h>
#include<stdbool.h>//bool类型
#include<stdlib.h>//realloc动态内存函数
#include<assert.h>//assert断言

//结构体声明定义
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

//栈的初始化
void STInit(ST* pst);

//栈的销毁
void STDestroy(ST* pst);

//压栈/进栈/入栈
void STPush(ST* pst, STDataType x);

//出栈
void STPop(ST* pst);

//获取栈顶元素
STDataType STTop(ST* pst);

//判空
bool STEmpty(ST* pst);

//栈上合计多少个元素个数
int STsize(ST* pst);


void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	//pst->top = -1;//top指向最新插入的数据

	//以这个为例
	pst->top = 0;//top指向当前有效数据的下一个位置。
	pst->capacity = 0;//容量大小

}

void STDestroy(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 newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
		STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));//给动态数组开辟空间
		if (tmp == NULL)//判断空间是否开辟失败
		{
			perror("realloc fail");
			return;
		}

		pst->a = tmp;//开辟成功赋值
		pst->capacity = newcapacity;
	}
	pst->a[pst->top++] = x;
}

void STPop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));//空栈不能删除
	pst->top--;//直接改变栈顶即可
}

STDataType STTop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));//空栈没有元素了
	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;//返回当前栈上的元素个数。
}

int main()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);
	STPush(&st, 6);
	while (!STEmpty(&st))
	{
		printf("%d", STTop(&st));
		STPop(&st);
	}

	STDestroy(&st);
	return 0;
}