C语言用数组模拟实现栈（LIFO）

发布时间：2023-06-23 11:30

 \"\" 个人主页：欢迎大家光临——>沙漠下的胡杨

\"\"  各位大帅哥，大漂亮

\"\" 如果觉得文章对自己有帮助

\"\" 可以一键三连支持博主

\"\" 你的每一分关心都是我坚持的动力

\"\" \"\"

 ☄： 本期重点：数组栈的模拟实现

  希望大家每天都心情愉悦的学习工作。 

栈数据结构的特性：

数组模拟栈的实现：

头文件的实现：

源文件的实现：

栈的初始化：

栈的销毁：

入栈：

出栈：

读出栈顶元素：

判断栈是否为空：

栈中元素的个数：

栈的整体代码：

头文件：

源文件：

最后我们来看下一个栈的习题——>括号匹配问题

栈数据结构的特性：

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

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

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

 

我们看个图片来进一步理解下栈：

\"C语言用数组模拟实现栈（LIFO）_第1张图片\"

刚开始时栈顶和栈底一样，然后ABCD分别入栈，然后在把D出栈，这个过程是怎么实现的呢？我们接着往下看吧。 

数组模拟栈的实现：

头文件的实现：

首先我们要知道一个栈中都要有什么，必须有一个动态的数组吧，然后要有一个栈顶，还要有一个容量配合栈顶来完成一些逻辑。所以我们如下创建：

typedef int STDataType;

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

我们还要有一些常见的栈的接口，比如初始化，销毁，插入，删除，取栈顶，返回栈的元素个数，判断栈是否为空。如下：

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

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

void StackPush(ST* ps, STDataType x);//插入（入栈），栈的插入是尾插。

void StackPop(ST* ps);//删除（出栈），从尾部删除。

STDataType StackTop(ST* ps);//读出栈顶

bool StackEmpty(ST* ps);//判断栈是否为空

int StackSize(ST* ps);//栈中的元素个数

这些就是我们要实现的函数接口啦，下面我们进行实现。

源文件的实现：

栈的初始化：

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

我们在初始化时一般是把动态的数组置为NULL，把栈顶和容量置为0。

 

栈的销毁：

void StackDestroy(ST* ps)//销毁
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

栈销毁时，我们先free掉开辟的动态数组，在把内容置为NULL，接着把栈顶和容量置为0。

 

入栈：

void StackPush(ST* ps, STDataType x)//插入（入栈），栈的插入是尾插。
{
	assert(ps);

	if (ps->capacity == ps->top)
	{
		int NewCapaticy = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType)*NewCapaticy);
		if (tmp == NULL)
		{
			perror(\"realoc fail\\n\");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = NewCapaticy;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

这里在扩容时，我们可以直接把栈顶和容量做对比，如果相等那么就扩容，扩容一般是2倍或者1.5倍，如果不相等，直接尾插，最后栈顶自增一。

 

出栈：

void StackPop(ST* ps)//删除（出栈），从尾部删除。
{
	assert(ps);
	assert(!StackEmpty(ps));

	ps->top--;
}

入栈时，先判断栈是否为空，如果不为空，就让栈顶自减一，如果为空，就直接报错，为空时不能再出栈啦。

 

读出栈顶元素：

STDataType StackTop(ST* ps)//读出栈顶
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->a[ps->top-1];
}

先判断栈是否为空，不为空时再返回栈顶的元素，此时栈顶的元素个数从0开始的，下标访问要 -1进行访问。

 

判断栈是否为空：

bool StackEmpty(ST* ps)//判断栈是否为空
{
	assert(ps);

	return ps->top == 0;
}

还是直接用表达式判断，用表达式的结果，作为布尔值进行返回。

 

栈中元素的个数：

int StackSize(ST* ps)//栈中的元素个数
{
	assert(ps);

	return ps->top;
}

这里返回栈顶就可以啦。

栈的整体代码：

头文件：

#pragma once 
#define  _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 
#include 

typedef int STDataType;

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

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

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

void StackPush(ST* ps, STDataType x);//插入（入栈），栈的插入是尾插。

void StackPop(ST* ps);//删除（出栈），从尾部删除。

STDataType StackTop(ST* ps);//读出栈顶

bool StackEmpty(ST* ps);//判断栈是否为空

int StackSize(ST* ps);//栈中的元素个数

源文件：

#include \"Stack.h\"


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

void StackDestroy(ST* ps)//销毁
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

void StackPush(ST* ps, STDataType x)//插入（入栈），栈的插入是尾插。
{
	assert(ps);

	if (ps->capacity == ps->top)
	{
		int NewCapaticy = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType)*NewCapaticy);
		if (tmp == NULL)
		{
			perror(\"realoc fail\\n\");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = NewCapaticy;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

void StackPop(ST* ps)//删除（出栈），从尾部删除。
{
	assert(ps);
	assert(!StackEmpty(ps));

	ps->top--;
}

STDataType StackTop(ST* ps)//读出栈顶
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->a[ps->top-1];
}

bool StackEmpty(ST* ps)//判断栈是否为空
{
	assert(ps);

	return ps->top == 0;
}

int StackSize(ST* ps)//栈中的元素个数
{
	assert(ps);

	return ps->top;
}

最后我们来看下一个栈的习题——>括号匹配问题

题目如下：

给定一个只包括 \'(\'，\')\'，\'{\'，\'}\'，\'[\'，\']\' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

 

这个我们就可以使用栈区后进先出的性质来进行解决：

1. 我们先创建一个栈，然后遍历字符串。

2. 如果是元素为  \'(\' 或者 \'[\' 或者 \'{\' 这三个其中之一，我们就把该元素入栈。

3. 如果是 \')\' 或者是 \'}\' 或者是 \']\'  那我们判断栈顶是否是这三个其中一个对应的左括号，如果是那我们就把左括号出栈，继续便利，如果不是对应的左括号，那么我们就返回false。

4.如果最后栈不为空我们返回false，为空我们返回true。

5.如果返回，我们应该及时把栈销毁，防止内存泄漏，只需要返回，我们就销毁栈。

 

代码如下：

typedef int STDataType;

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

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

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

void StackPush(ST* ps, STDataType x);//插入（入栈），栈的插入是尾插。

void StackPop(ST* ps);//删除（出栈），从尾部删除。

STDataType StackTop(ST* ps);//读出栈顶

bool StackEmpty(ST* ps);//判断栈是否为空

int StackSize(ST* ps);//栈中的元素个数


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

}

void StackDestroy(ST* ps)//销毁
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

void StackPush(ST* ps, STDataType x)//插入（入栈），栈的插入是尾插。
{
	assert(ps);

	if (ps->capacity == ps->top)
	{
		int NewCapaticy = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType)*NewCapaticy);
		if (tmp == NULL)
		{
			perror(\"realoc fail\\n\");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = NewCapaticy;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

void StackPop(ST* ps)//删除（出栈），从尾部删除。
{
	assert(ps);
	assert(!StackEmpty(ps));

	ps->top--;
}

STDataType StackTop(ST* ps)//读出栈顶
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->a[ps->top-1];
}
bool StackEmpty(ST* ps)//判断栈是否为空
{
	assert(ps);

	return ps->top == 0;
}
int StackSize(ST* ps)//栈中的元素个数
{
	assert(ps);

	return ps->top;
}

bool isValid(char * s)
{
    ST st;
    StackInit(&st);//初始化栈

    while(*s)//遍历字符串
    {
        if(*s == \'{\' || *s == \'[\' || *s == \'(\')//左括号入栈
        {
            StackPush(&st,*s);
            s++;
        }
        else
        {
            if(StackEmpty(&st))//如果栈为空，直接返回
            {
                StackDestroy(&st);
                return false;
            }

            STDataType top = StackTop(&st);//取出栈顶元素做比较
            if((top == \'(\' && *s == \')\')
            || (top == \'{\' && *s == \'}\')
            || (top == \'[\' && *s == \']\'))
            {
               StackPop(&st);
               s++;
            }
            else
            {
                StackDestroy(&st);
                return false;
            }
        }
    }

    bool ret = StackEmpty(&st);//判断栈是否为空
    StackDestroy(&st);
    return ret;
}

今天到此结束啦，感谢大家观看。

相关推荐

用python-OpenCV做一个魔方墙找茬 （3D视眼训练）

九章云极DataCanvas公司深度参编《中国金融科技发展报告2021》蓝皮书

《死磕MySQL系列》为什么MySQL字符串不加引号索引失效？

Helm3安装带有ik分词的ElasticSearch

推荐模型复现（二）：精排模型DeepFM、DIN

python变量数据类型和运算符

ubuntu16.04系统下 ROS + Autoware1.12（包含calibration联合标定工具）安装过程

【HTML | CSS | JAVASCRIPT】一款响应式精美简历模板分享（万字长文 | 附源码）

ECMAScript 6.0

appuim java 脚本_APP自动化测试神器之Appium-QQ登录脚本实战（java版）

【stm32】STM32F407 如何使用代码进入USB-DFU模式？

《网络是怎么样连接的》读书笔记 - 认识网络基础概念（一）

k8s——pod进阶（资源限制与探针）

k8s笔记19--grafana配置node监控面板

即时通讯发展前景怎么样？现在状态是如何

call ,apply和bind方法 详解

Maven项目构建工具

SQL Server 2019 安装教程（详细免费，自定义安装）

springMVC跳转和传值

超详细的MySQL基本操作

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网，如有侵权请联系：561261067@qq.com

桂ICP备16001015号