数据结构栈的概念及栈的实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构栈的概念及栈的实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.栈的概念及结构

2.栈的实现

2.1 初始化栈

2.2 入栈

2.3 出栈

2.4 获取栈顶元素

2.5 获取栈中有效元素个数

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

2.7 销毁栈

3. 完整代码

test.c

Stack.h

Stack.c

1.栈的概念及结构

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

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

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

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

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

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

数据结构栈的概念及栈的实现,数据结构,数据结构,开发语言,c++,c语言,算法,linux,windows

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

数据结构栈的概念及栈的实现,数据结构,数据结构,开发语言,c++,c语言,算法,linux,windows

2.栈的实现

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

数据结构栈的概念及栈的实现,数据结构,数据结构,开发语言,c++,c语言,算法,linux,windows

// 下面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈
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;
}

感谢观看，希望能对你有所帮助！文章来源地址https://www.toymoban.com/news/detail-812914.html

到了这里，关于数据结构栈的概念及栈的实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！