前言

  前面学习的一些结构都比较普通，今天就让我们来看一个比较特殊的结构——栈，它的特殊之处是后进先出，也就是后进来的数据先出去。

1.栈

1.1 栈的概念及结构

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

1.2 栈的实现

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

2.栈功能的解析及实现

2.1 栈的创建

  我们采用数组的形式进行实现。

typedef int DataType;
typedef struct Stack
{
	DataType* data;
	int top; //栈顶
	int capacity;容量
}Stack;

2.2 初始化

  将所有数据赋个初值。

void StackInit(Stack* ps)
{
	assert(ps);
	ps->data = NULL;
	ps->top = 0; //指向栈顶元素的下一个位置，同时也代表这栈中有多少元素
	ps->capacity = 0;//栈的容量
}

2.3 入栈

  入栈也就是要增加元素，那么首先需要做的就是判断容量够不够，不够的话就需要增容，然后再将元素放进去即可。

void StackPush(Stack* ps, DataType x)
{
	assert(ps);
	//判断是否需要增容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		DataType* tmp = (DataType*)realloc(ps->data,sizeof(DataType) * newcapacity);
		if (tmp == NULL)
		{
			return;
		}
		ps->data = tmp;
		ps->capacity = newcapacity;
	}
	ps->data[ps->top] = x;
	ps->top++;
}

2.4 出栈

  出栈的话我们只能从栈顶出元素，不能从其他位置出。既然要删除元素，那么我们就需要判断栈中是否还有剩余元素，没有的话就不需要删除。这里我写了一种方式，不过后面还会写一个判断栈是否为空的函数，大家看个人喜好采用。

void StackPop(Stack* ps)
{
	assert(ps);
	//assert(ps->top > 0);
	assert(!StackEmpty(ps));
	ps->top--;
}

2.5 检查栈是否为空

  写的比较简洁，返回的是ps->top == 0，也就是如果条件成立，这个表达式就代表着true（也就是栈为空），如果不成立就代表着false（栈不为空）。

bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

2.6 获取栈顶元素

  我们的top指向的是栈顶元素的下一个位置，所以在数组中最后一个元素也就是栈顶的元素位置是top - 1。

DataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//判断是否为空
	return ps->data[ps->top - 1];
}

2.7 栈中的有效元素个数

  在创建栈哪里就提到了，top既指向栈顶元素的后一个位置，也代表着栈中的元素个数。

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}

2.8 销毁

  动态开辟的空间在程序结束时都需要被回收，用来防止出现内存泄漏。

void StackDestroy(Stack* ps)
{
	ps->top = 0;
	ps->capacity = 0;
	free(ps->data);
	ps->data = NULL;
}

3.代码实现

3.1 Stack.h

   栈的创建以及各个函数声明。

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
typedef int DataType;
typedef struct Stack
{
	DataType* data;
	int top;
	int capacity;
}Stack;

// 初始化栈
void StackInit(Stack* ps);

// 入栈
void StackPush(Stack* ps, DataType x);

// 出栈
void StackPop(Stack* ps);

// 获取栈顶元素
DataType StackTop(Stack* ps);

// 获取栈中有效元素个数
int StackSize(Stack* ps);

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool StackEmpty(Stack* ps);

// 销毁栈
void StackDestroy(Stack* ps);

3.2 Stack.c

  栈的各功能的函数。

#include"Stack.h"

void StackInit(Stack* ps)
{
	assert(ps);
	/*DataType* tmp = (DataType*)malloc(sizeof(DataType));
	if (tmp == NULL)
	{
		return;
	}*/

	ps->data = NULL;
	ps->top = 0;      //指向栈顶元素的下一个位置，同时也代表这栈中有多少元素
	ps->capacity = 0;
}

void StackPush(Stack* ps, DataType x)
{
	assert(ps);
	//判断是否需要增容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		DataType* tmp = (DataType*)realloc(ps->data,sizeof(DataType) * newcapacity);
		if (tmp == NULL)
		{
			return;
		}
		ps->data = tmp;
		ps->capacity = newcapacity;
	}
	ps->data[ps->top] = x;
	ps->top++;
}

bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

void StackPop(Stack* ps)
{
	assert(ps);
	//assert(ps->top > 0);
	assert(!StackEmpty(ps));
	ps->top--;
}

DataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->data[ps->top - 1];
}

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}

void StackDestroy(Stack* ps)
{
	ps->top = 0;
	ps->capacity = 0;
	free(ps->data);
	ps->data = NULL;
}

3.3 test.c

  用来测试实现的栈功能有没有问题。

#include"Stack.h"

void test()
{
	Stack st;
	StackInit(&st);//初始化

	StackPush(&st, 1);//测试:入栈
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	while(!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	printf("
");


	StackPush(&st, 5);//入栈一些元素进行测试
	StackPush(&st, 6);

	StackPop(&st);//测试:中途出栈的效果,实际就是将6提前出栈

	StackPush(&st, 7);
	StackPush(&st, 8);
	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	printf("
");


	StackPush(&st, 1);//入栈一些数据进行测试
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);

	int sz = StackSize(&st);//测试:计算栈中元素个数
	printf("%d
", sz);

	StackDestroy(&st);
}
int main()
{
	test();
	return 0;
}

4.总结

  单纯从代码实现角度来看，栈的实现还是比较简单的，因此可以不用在代码实现方面下太大的功夫，将更多的注意力转移到做题方面，感觉会有更好的效率性。
  栈的讲解就先告一段落了，如果发现文章哪里有问题可以在评论区提出来或者私信我嗷。接下来我会继续深入学习数据结构的其他知识，开启新的篇章，那么本期就到此结束，让我们下期再见！！觉得不错可以点个赞以示鼓励喔！！