栈的实现---超详细

栈的实现

在这里插入图片描述

文章目录

栈的实现
- 一、栈的模型
- 二、栈的代码实现以及测试用例
- - ①栈的初始化
  - ②入栈
  - ③出栈
  - ④弹出栈顶
  - ⑤判断栈空间是否为空
  - ⑥计算栈空间长度
  - ⑦销毁栈
  - ⑧测试用例

一、栈的模型

首先栈有两个概念
1.数据结构里的栈。2.语言/操作系统中的栈(内存空间)，可能会在递归程序里发生栈溢出。
入栈和出栈只能发生在栈顶，栈底不进行任何操作，且栈顶随着入栈和出栈变化。栈顶指向最后的数据。
在这里插入图片描述

二、栈的代码实现以及测试用例

①栈的初始化

void STIni(ST* pst)
{
	assert(pst);//数组栈和顺序表比较像，注意顺序表和数组栈
	//是一块连续的内存空间，所以必须要这样实现
	pst->a = NULL;
	pst->capacity = 0;
	//top指向栈顶元素
	pst->top = -1;
	//top指向栈顶元素的下一个
	//pst->top = 0;
}

②入栈

void STPush(ST* pst, STDataType x)
{
	assert(pst);
	if (pst->capacity == pst->top + 1)
	{
		int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("malloc");
			exit(-1);
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	pst->a[pst->top + 1] = x;
	pst->top += 1;
}

③出栈

void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > -1);
	/*free(pst->a[pst->top]);
	pst->a[pst->top] = NULL;*///不能随便free，数组栈连续，我还可以下次继续插回来。
	pst->top -= 1;
}

④弹出栈顶

STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > -1);
	return pst->a[pst->top];
}

⑤判断栈空间是否为空

bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == -1;
}

⑥计算栈空间长度

int STSize(ST* pst)
{
	assert(pst);
	return (pst->top + 1);
}

⑦销毁栈

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

⑧测试用例

#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"
void test1()
{
	ST s;
	STIni(&s);
	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);
	STPush(&s, 4);
	STPush(&s, 5);
	while (!STEmpty(&s))
	{
		printf("%d ", STTop(&s));
		STPop(&s);
	}
	printf("\n");
}

int main()
{
	test1();
	return 0;
}