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;
}

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

相关推荐

狂神。Mybatis学习。

【JavaScript】JS实用案例分享：动态生成分页组件 | 通过按键实现移动控制

人工智能: 手把手教你运行机器学习代码（EGNet）

Oracle数据泵实现不同用户导入导出表级

在eclipse搭建maven项目

学习笔记2-RepVGG思想

网络空间冲突不断，沃通SSL证书、代码签名证书助力保障网络安全

抖音商品详情API接口-（item_get-获得抖音商品详情API接口）

JavaScript DOM简介和获取元素

【多线程】锁策略

C语言经典100题——求一个二维数组的鞍点

从零实现一个vue文件解析器

剑指 Offer 09. 用两个栈实现队列

每日一学丨Redis 突然变慢了如何排查并解决？

从零搭建嵌入式开发环境

xxl-job分布式任务调度框架使用实战

【腾讯蓝鲸】第七届 7·24 运维日节日祝福送上~ 快来许愿~

【Java刷题系列】01_循环找素数

甲骨文因超过90亿美元的NetSuite交易起诉Larry Ellison和CEO Safra Catz

C语言实现扫雷游戏详细流程

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

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

桂ICP备16001015号