【数据结构】--栈

👌个人主页: 起名字真南
🤣个人专栏:【数据结构初阶】【C语言】

请添加图片描述

1 栈

1.1 栈的概念和结构

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

压栈：栈的插入操作叫做压栈/ 进栈。
出栈：栈的删除操作叫做出栈。
不管是压栈还是出栈都在栈顶

在这里插入图片描述

1.2 栈的实现

栈的实现一般可以用数组或者链表进行实现，但相对而言使用数组的结构实现更优越些，因为数组在尾插数据比较方便。

1.2.1 头文件

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int StackDataType;

typedef struct Stack
{
	StackDataType* arr;  
	int top;  //记录栈顶的数据
	int capacity; //记录空间的大小

}Stack;

//初始化
void StackInit(Stack* ST);

//销毁
void StackDestroy(Stack* ST);

//打印数据
void StackPrint(Stack ST);

//插入数据
void StackPush(Stack* ST, StackDataType data);

//删除数据
void StackPop(Stack* ST, StackDataType data);

//取栈顶数据
StackDataType StackTop(Stack* ST);

//判空
bool StackEmpty(Stack* ST);

//获取数据个数
int STSize(Stack* pst);

1.2.2 初始化

我们可以看到栈的初始化和顺序表的初始化基本一致。所以这次我们在初始化的时候给定capacity = 4，因为初始有空间所以在给数组初始化的时候要开辟空间，使用malloc，然后定义top来记录栈顶的数据。


void StackInit(Stack* ST)
{
	assert(ST);
	ST->arr = (StackDataType*)malloc(4 * sizeof(StackDataType));
	ST->capacity = 4;
	ST->top = 0;
}

1.2.3 销毁

因为数组是一串连续的空间所以直接释放首元素地址即可。

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

1.2.4 打印所有元素

因为通过top来记录栈顶元素的原理是top作为访问栈顶元素的指针（地址）所以我们也可以根基top的大小来记录元素的数量。因为这里传的参数是结构体所以结构体的调用使用 ”.“ 。

void StackPrint(Stack ST)
{
	assert(ST.arr);
	for (int i = 0; i < ST.top; i++)
	{
		printf("%d ", ST.arr[i]);
	}
	printf("\n");
}

1.2.5 入栈

入栈我们首先要判断空间的大小是否满了，因为top也记录着元素的数量所以直接比较即可由于在初始化的时候我们分配的空间，所以如果相等的化只有一种情况就是满了，所以我们需要对他进行扩容。

void StackPush(Stack* ST, StackDataType data)
{
	assert(ST);
	if (ST->top == ST->capacity)
	{
		StackDataType* tmp = realloc(ST->arr, 2 * sizeof(ST->arr));
		if (tmp == NULL)
		{
			perror("realloc:");
		}
		ST->arr = tmp;
		ST->capacity = 2 * (ST->capacity);
	}
	ST->arr[ST->top++] = data;
	ST->capacity++;
}

1.2.6 出栈

出栈和顺序表的尾删同理。

void StackPop(Stack* ST, StackDataType data)
{
	assert(ST);
	ST->top--;
}

1.2.7 获取栈顶数据

需要注意的是在构造函数的时候，函数的返回值类型，还有top-1记录的是栈顶的数据而top记录的是元素的个数，因为是从0开始所以相差了1.

StackDataType StackTop(Stack* ST)
{
	assert(ST);
	return ST->arr[ST->top - 1];
}

1.2.8 判空

判空的时候我们需要用到bool类型所以需要包含对应的头文件，如果ST->top == 0 成立则返回 True 否则返回False。

#include<stdbool.h>
bool StackEmpty(Stack* ST)
{
	assert(ST->arr);
	return ST->top == 0;
}

1.2.9 获取元素个数

这个也只是需要注意返回值类型为int

int STSize(Stack* pst)
{
	assert(pst);

	return pst->top;
}

目录

1 栈