[ 数据结构-C实现 ] 栈 Stack_c语言实现栈

目录

1.栈

1.1栈的概念和结构

2.栈的实现

2.1接口

2.2接口的实现

2.2.1初始化

2.2.2销毁

2.2.3入栈--进栈--压栈

2.2.4出栈

2.2.5判断栈是否为空

2.2.6栈的大小

2.2.7栈顶

完整代码：

---

1.栈

1.1栈的概念和结构

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

为了加深对这个概念的理解，大家可以把压栈和出栈类比为弹夹中的子弹，先放进去的子弹后被打出。

1. 一个栈的初始状态为空。现将元素 1 、 2 、 3 、 4 、 5 、 A 、 B 、 C 、 D 、 E 依次入栈，然后再依次出栈，则元素出

栈的顺序是（ B  ）。

A 12345ABCDE

B EDCBA54321

C ABCDE12345

D 54321EDCBA

2.栈的实现

2.1接口

其中接口包括栈的初始化，栈的销毁，入栈，出栈，判断栈是否为空，栈的大小，以及栈顶元素。

由于我们实现栈使用数组的结构，大致原理和顺序表相同，因此如果大家对顺序表掌握的比较好，那么我相信栈也不在话下，如果大家对顺序表掌握的还不够拿捏，欢迎大家参考此博文：(1条消息) [ 数据结构 - C实现] 顺序表_小白又菜的博客-CSDN博客

//初始化
void StackInit(ST* ps);
//销毁
void StackDestory(ST* ps);
//入栈--进栈--压栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
//判断是否为空
bool StackEmpty(ST* ps);
//栈的大小
int StackSize(ST* ps);
//栈顶
STDataType StackTop(ST* ps);

2.2接口的实现

2.2.1初始化

由于栈开始为空，因此栈的空间和栈顶位置先赋为0。

//初始化
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
	
}

2.2.2销毁

将栈释放，并且将栈置空，栈的容量和栈顶位置赋0。

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

2.2.3入栈--进栈--压栈

在入栈时，相当于数组的尾插，将栈顶元素赋值为0，再让栈顶位置++。

但是在压栈前要先对栈空间进行判断，空间是否足够，如果不足够的话对栈进行动态扩容，这里之所以不把扩容写成一个函数的原因是，在栈这个数据结构中，只有入栈这一种操作需要判断空间是否足够，因此只需要在入栈内部写一个relloc即可。

void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//判断能否需要扩容
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		ps->a =(STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
		if (ps->a == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

2.2.4出栈

出栈直接让栈顶位置--ps->top即可.

//出栈
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	--ps->top;
}

2.2.5判断栈是否为空

判断栈是否为空，我们只需要判断栈顶位置是否等于0，如果栈顶位置等于0说明栈为空，如果不等于0说明栈不为空。

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

2.2.6栈的大小

由于top是存的是栈顶的下一个位置，因此根据下标来说，top位置所对应的下标即是栈的大小。

//栈的大小
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

2.2.7栈顶

栈顶元素即是(top-1)的下标位，因此只需ps->a[ps->top-1]即可

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

完整代码：

2022_03_24_栈和队列/2022_03_24_栈和队列 · 李兴宇/数据结构 - 码云 - 开源中国 (gitee.com)

（本篇完）