数据结构：栈的概念及栈的实现

目录

1.栈的概念及结构

栈（后进先出，先进后出）：

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

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

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

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

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

在内存区域中也有一个区域叫做栈 ，它们一个是数据结构，一个是内存区域

2.栈的实现 

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小

// 下面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈
typedef int STDataType;
#define N 10
typedef struct Stack
{
	STDataType a[N];
	int top; // 栈顶
}ST;

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top; // 栈顶
	int capacity; // 容量
}ST;


void STInit(ST* pst);
void STDestroy(ST* pst);

// 栈顶插入删除
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);

bool STEmpty(ST* pst);
int STSize(ST* pst);

2.1  初始化栈

void STInit(ST* pst)
{
	//断言出现空指针
	assert(pst);
	pst->a = NULL;
	pst->capacity = 0;//栈容量
	// 如果top=0，表示top指向栈顶元素的下一个位置
	pst->top = 0;//栈顶

	// 如果top=-1，表示top指向栈顶元素
	//pst->top = -1;
}

在栈实现中top的初始值的选择是最关键的一点，top既可以初始化为0，也可以初始化为-1，如果top=0，表示top指向栈顶元素的下一个位置 ，如果top=-1，表示top指向栈顶元素，这里我们top取0，如果top取-1，下面的一些条件也要发生变化

2.2 入栈 

void STPush(ST* pst, STDataType x)
{
	//断言出现空指针
	assert(pst);
	//判断空间大小是否足够，如果不够，则扩容
	if (pst->capacity == pst->top)
	{
		//如果初始空间为0，则赋为4，如果不是则扩容为原来的2倍
		int newcapacity = pst->capacity == 0 ? 4:pst->capacity * 2;
		//将扩容的新空间存起来
		STDataType* tmp = realloc(pst->a, sizeof(newcapacity)*newcapacity);
		//判定新空间是否开辟成功
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		//将开辟的新空间和空间大小赋给a和capacity
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	//赋值
	pst->a[pst->top] = x;
	pst->top++;
}

注：数据结构中动态内存开辟非常重要，如果感觉不太熟悉的话可以看看我之前的文章（感谢支持！）C语言：动态内存管理-CSDN博客

2.3 出栈 

void STPop(ST* pst)
{
	断言出现空指针
	assert(pst);
	//这里top指向栈顶的下一个元素，top减一，看似没有删除元素，实则top已经指向要删除元素的下一个，要删除的元素变成了无效元素，从而达到删除的目的
	pst->top--;
}

这里top指向栈顶的下一个元素，top减一，看似没有删除元素，实则top已经指向要删除元素的下一个，要删除的元素变成了无效元素，从而达到删除的目的,这种思想以后我们在数据结构中会经常遇到 。

2.4 获取栈顶元素

STDataType STTop(ST* pst)
{
	//断言出现空指针
	assert(pst);
	return pst->a[pst->top - 1];
}

2.5 获取栈中有效元素个数 

int STSize(ST* pst)
{
	//断言出现空指针
	assert(pst);
	return pst->top;
}

 2.6  检测栈是否为空，如果为空返回非零结果，如果不为空返回0

bool STEmpty(ST* pst)
{
	//断言出现空指针
	assert(pst);
	return pst->top == 0;
}

2.7 销毁栈 

void STDestroy(ST* pst)
{
	//断言出现空指针
	assert(pst);
	free(pst->a);
	pst->capacity = pst->top = 0;
}

3. 完整代码

test.c

#include"Stack.h"

int main()
{
	ST s;
	STInit(&s);
	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);
	//printf("%d ", STTop(&s));
	//STPop(&s);
	//printf("%d ", STTop(&s));
	//STPop(&s);

	STPush(&s, 4);
	STPush(&s, 5);

	//    一     对     多
	// 入栈顺序  --  出栈顺序
	while (!STEmpty(&s))
	{
		printf("%d ", STTop(&s));
		STPop(&s);
	}
	printf("\n");

	return 0;
}

 Stack.h

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

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;


void STInit(ST* pst);
void STDestroy(ST* pst);

// 栈顶插入删除
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);

bool STEmpty(ST* pst);
int STSize(ST* pst);

Stack.c

#include "Stack.h"


void STInit(ST* pst)
{
	//断言出现空指针
	assert(pst);
	pst->a = NULL;
	pst->capacity = 0;//栈容量
	// 如果top=0，表示top指向栈顶元素的下一个位置
	pst->top = 0;//栈顶

	// 如果top=-1，表示top指向栈顶元素
	//pst->top = -1;
}
void STDestroy(ST* pst)
{
	//断言出现空指针
	assert(pst);
	free(pst->a);
	pst->capacity = pst->top = 0;
}

// 栈顶插入删除
void STPush(ST* pst, STDataType x)
{
	//断言出现空指针
	assert(pst);
	//判断空间大小是否足够，如果不够，则扩容
	if (pst->capacity == pst->top)
	{
		//如果初始空间为0，则赋为4，如果不是则扩容为原来的2倍
		int newcapacity = pst->capacity == 0 ? 4:pst->capacity * 2;
		//将扩容的新空间存起来
		STDataType* tmp = realloc(pst->a, sizeof(newcapacity)*newcapacity);
		//判定新空间是否开辟成功
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		//将开辟的新空间和空间大小赋给a和capacity
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	//赋值
	pst->a[pst->top] = x;
	pst->top++;
}
void STPop(ST* pst)
{
	//断言出现空指针
	assert(pst);
	//这里top指向栈顶的下一个元素，top减一，看似没有删除元素，实则top已经指向要删除元素的下一个，要删除的元素变成了无效元素，从而达到删除的目的
	pst->top--;
}
STDataType STTop(ST* pst)
{
	//断言出现空指针
	assert(pst);
	return pst->a[pst->top - 1];
}

bool STEmpty(ST* pst)
{
	//断言出现空指针
	assert(pst);
	return pst->top == 0;
}
int STSize(ST* pst)
{
	//断言出现空指针
	assert(pst);
	return pst->top;
}

感谢观看，希望能对你有所帮助 ！