数据结构---栈的实现

目录

一、栈

二、栈的实现

2.1 void StackInit(ST* ps);

2.2 void StackDestory(ST* ps);

2.3 void StackPush(ST* ps, STDataSType x);

2.4 void StackPop(ST* ps);

2.5 bool StackEmpty(ST* ps);

2.6 int StackSize(ST* ps);

2.7 STDataSType StackTop(ST* ps);

---

一、栈

学习栈之前我们需要认识栈究竟是什么东西。

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素 *** 作。

进行数据插入和删除 *** 作的一端称为栈顶，另一端称为栈底。

栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

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

出栈：栈的删除 *** 作叫做出栈。

出数据也在栈顶

图解↓：

 图中数据都是从栈顶进入，当图中1，2，3，4都进入，先出栈的只能是4，但也可以边进边出，举例：所以不一定出栈顺序就是4 3 2 1。

二、栈的实现

栈的实现一般可以用数组或链表实现，相对而言数组的结构实现更优一些。

因为数组在尾上插入的代价比较小，而链表需要找尾，要遍历链表（单链表）。

实现栈，一般需要实现以下几个接口：

// 支持动态增长的栈

typedef int STDataSType; //方便改变栈中存储元素的类型

typedef struct Stack
{
    STDataSType* a;
    int top;//栈顶
    int capacity;//栈的容量
}ST;

//初始化 
void StackInit(ST* ps);
//销毁栈
void StackDestory(ST* ps);
//进栈 
void StackPush(ST* ps, STDataSType x);
//出栈 
void StackPop(ST* ps);
//判断栈空 
bool StackEmpty(ST* ps);
//栈中有几个数据 
int StackSize(ST* ps);
//取栈顶元素
STDataSType StackTop(ST* ps);

接下来我们来一一实现 

2.1 void StackInit(ST* ps);

void StackInit(ST* ps)
{
	assert(ps);//检查结构体不为空
    //数组为空，栈顶和容量都为0；
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

2.2 void StackDestory(ST* ps);

也要先断言结构体不为空，释放掉我们开辟的数组的空间，并将地址置为空。

void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

2.3 void StackPush(ST* ps, STDataSType x);

top开始在0的位置，所以我们填一个数据，要将top++一下。

void StackPush(ST* ps, STDataSType x)
{
	assert(ps);
	//判断栈满了
	if (ps->top == ps->capacity)
	{
		int newcapycity = ps->capacity == 0 ? 4 : (ps->capacity) * 2;
		ps->a = realloc(ps->a, sizeof(STDataSType) * newcapycity);
		//开辟内存失败直接退出
		if (ps->a == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}
		ps->capacity = newcapycity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

2.4 void StackPop(ST* ps);

本来有5个数据，top在5的下一个位置，要出栈就是5出，只需要将top往前移一步就好。

void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);//检查是否有数据
	ps->top--;
}

2.5 bool StackEmpty(ST* ps);

判断栈是不是空的只需要判断top是不是等于0，是0就是空，就返回真，不是0就返回假；

 

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

2.6 int StackSize(ST* ps);

这个非常简单，只需要返回top就可以了，top是最后一个数据的下一个位置，因为是数组，下标是从0开始的，所以top就是元素个数。

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

2.7 STDataSType StackTop(ST* ps);

判断栈中有元素，那么栈顶元素的下标为top-1，返回就可以了。

STDataSType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

---

以上就是我对栈的理解，如有错误欢迎批评指正！！