一.栈

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

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

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

可以类比成，羽毛球和弹夹。

上图理解一下：

栈的实现一般是顺序表。

如果是顺序表的话，我们的栈顶应该要在数组末尾！如果在数组头部的话，数据进栈时还需要挪动其余数据以便数据的存入！效率很低！

这是实现需要的头文件:

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int SLDatatype;
typedef struct stack
{
    SLDatatype* a;
    int top;
    int capacity;
}SL;
//初始化
void SLinio(SL* ps);
//销毁
void SLdestroy(SL* ps);
//入栈
void SLpush(SL* ps, SLDatatype x);
//出栈
void SLpop(SL* ps);
//栈数据个数
int SLSize(SL* ps);
//判空
bool SLempty(SL* ps);
//栈顶数据
SLDatatype SLtop(SL* ps);

 

初始化

我们要将栈中各个变量进行初始化。

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

入栈

入栈要在数组尾部，记得每次入栈需要判断空间是否够用。

void STpush(ST* p, STDateType x)
{
	assert(p);
	if (p->top == p->capacity)
	{
		int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;
		STDateType* tmp = (STDateType*)realloc(p->a, newcapacity * sizeof(STDateType));
		if (tmp == NULL)
		{
			perror("realloc failed!");
			return;
		}
		p->a = tmp;
		p->capacity = newcapacity;
	}
	p->a[p->top++] = x;
}

出栈

入栈要在尾部，出栈也要在尾部，后入先出的原则要时刻记住，需要判断是否为空！

void STpop(ST* p)
{
	assert(p);
	//出栈的话要判断一下空的情况
	assert(!STEmpty(p));
	p->top--;
}

 销毁

void STDestroy(ST* p)
{
	assert(p);
	free(p->a);
	p->capacity = p->top = 0;
}

栈顶数据

在访问栈顶数据时，我们也要先判断栈是否为空，否则当栈为空时，访问栈顶数据便会越界访问！

//栈顶的数据
STDateType STtop(ST* p)
{
	assert(p);
	//出栈的话要判断一下空的情况
	assert(!STEmpty(p));
	return p->a[p->top-1];
}

 数据个数

//栈的数据个数
int STsize(ST* p)
{
	assert(p);
	return p->top;
}

判空

//判空
bool STEmpty(ST* p)
{
	assert(p);
	return p->top == 0;
}

好了，我们下期见！