当前位置： 首页 > news >正文

【数据结构】C语言实现顺序栈 OJ题 —— 有效的括号

news 来源：原创 2024/5/17 1:11:26

文章目录

  • 0. 前言
  • 1. 栈的概念
  • 2. 栈的结构
  • 3. 栈的实现
    • 3.1 结构设计
    • 3.2 接口总览
    • 3.3 初始化
    • 3.4 销毁
    • 3.5 判断栈是否为空
    • 3.6 压栈
    • 3.7 出栈
    • 3.8 取栈顶元素
    • 3.9 计算栈的大小
  • 4. 完整代码
    • Stack.h
    • Stack.c
    • test.c
  • 5. OJ题 —— 有效的括号
  • 6. 结语

0. 前言

这篇博客为大家带来的是 栈的概念简述、栈的概念选择题、栈的结构选择、C语言实现栈以及栈的一道OJ题。内容相对比较简单。话不多说，我们这就开始。

1. 栈的概念

栈 是一个特殊的 线性表。

栈只允许在固定的一段进行插入和删除元素的操作。进行数据插入和删除操作的一端称为栈顶，不进行操作的一端称为栈底。

栈中的元素遵守 后进先出 (LIFO - Last In First Out) 的原则。也就是先进的后出，后进的先出，就像手枪的弹匣一样。后被装入的子弹，也就是弹匣顶端的子弹先被枪打出。

栈对于数据的管理主要有两种操作：

  1. 压栈：栈的插入操作叫做进栈 / 压栈 / 入栈，从栈顶进行压栈。
  2. 出栈：栈的删除操作叫做 出栈，从栈顶进行出栈。

栈的操作流程：

image-20221110225807135

栈的概念选择题：

  1. 一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出
    栈的顺序是（ ）。
    A. 12345ABCDE
    B. EDCBA54321
    C. ABCDE12345
    D. 54321EDCBA

答案：B

首先明确栈的原则：后进先出。

将以上元素依次入栈，那么最入栈的最晚出栈，那么1应该最后一个出栈，直接选出结果：EDCBA54321

  1. 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）
    A. 1,4,3,2
    B. 2,3,4,1
    C. 3,1,4,2
    D. 3,4,2,1

答案：C

做对这道题目，我们需要知道，栈不是所有数据入栈后才能出栈的，栈可以入栈部分元素，然后出栈，再入栈其他元素。

下面对每个选项进行分析：

A：1 先入栈，然后出栈，栈空；随后 2, 3, 4 依次入栈。然后将元素全部出栈，栈空。得到结果为：1, 4, 3, 2

B：1, 2 先入栈；然后出栈 2，栈中余1；再入栈 3，出栈 3，栈中余1；再入栈 4，出栈 4，栈中余1；最后出栈 1，栈空。得到结果为：2, 3, 4, 1

C：这种序列答案是绝对不可能的。通过 A、B两个选项和这道题的进栈序列我们也可以找出规律：某个元素的两个相邻元素必定有一个相邻元素与该元素差值为1。否则的话就不符合栈的结构。因为如果第一个元素为3的话，那么就是先入栈 1，2，3，然后出栈。那么无论怎么出栈，第二个元素都不可能为1。2, 4 都有可能，如果还不明白可以画图再想想。

D：1，2，3，先入栈；然后出栈3，栈中余2，1；再入栈 4，然后出栈 4，栈中余2，1；然后将栈中元素全部出栈。得到结果为：3, 4, 2, 1

2. 栈的结构

栈一般可以使用 数组或链表 实现。让我们分析一下使用这两种方法实现，栈的结构分别是什么样的。

在分析之前，我们要明确的一点是，栈只对 栈顶 的元素进行操作。

数组：

对于数组(顺序表)而言，最方便的就是尾插和尾删，所以我们将 顺序表的尾部 当做 栈顶。顺序表的头部 则当做 栈底，因为对于顺序表，头部的删除需要挪动大量数据。

image-20221110230725584

链表：

对于链表而言，尤其是 单链表，尾部的插入删除是很麻烦的。但是 单链表 的头插和头删就很方便，所以可以把 单链表的头部 作为栈顶，单链表的尾部 作为 栈底。

image-20221110231451539

如果对于双向链表而言，那么就是随便选了，毕竟双向链表无论哪头插入删除数据都很方便。

抉择：

那么对于 顺序栈 和 链式栈 ，那个更加好呢？那必定是 顺序栈，因为使用顺序栈的 尾插尾删非常方便， 且 cpu缓存利用率也更高。而且对于顺序栈实现起来相对简单，所以我们接下来就实现 顺序栈 。

3. 栈的实现

3.1 结构设计

我们既然是实现 顺序栈，那么它的结构肯定就和 顺序表 差不多：

typedef struct Stack
{
	STDatatype* a; // 指向动态开辟的数组
	int capacity; // 栈的容量
	int top; // 标识 栈顶的下一个位置的下标 或 栈顶的下标
}ST;

这里的 top 我们需要好好理解一下。当top的初始值不同时，top可以表示 栈顶的下一个位置的下标 或 栈顶下标。

  1. 当 top = 0，top 表示栈顶的下一个位置的下标：

image-20221111001915295

top 初始值为 0，那么第一次 压栈 就是在0下标插入元素。压栈后，top++。那么当 最后一次压栈后，元素被压在栈顶，那么top 最后的位置就是栈顶的下一个元素的下标处。此时，top就是栈中元素的个数。

  1. 当 top = -1，top 表示栈顶的下标：

image-20221111002108890

top 初始值为 -1，那么需要先 ++top，再压栈。否则会越界。当 最后一次压栈时，为先 ++top 再压栈，top 最后的位置就是栈顶的下标处。

这个需要理清楚，否则实现判空、计算大小等接口函数的时候会引起错误。

3.2 接口总览

由于 栈的结构 和 操作规则，栈的接口相对来说比较少，且比较简单：

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); // 计算栈的大小

3.3 初始化

我们实现的是顺序栈，那么就和顺序表一样，需要创建结构体变量，传结构体的地址，进行初始化。

在初始化的时候就给栈开上四个单位的空间，并且将起始容量设定为4。

注意了我们这里设定的 top = 0，那么表示 top 为栈顶的下一个位置的下标。

void StackInit(ST* ps)
{
	// 结构体一定不为空，所以需要断言
	assert(ps);

	ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = 0;
}

3.4 销毁

对于栈的销毁，那么我们就只需要释放动态开辟的空间，将指针置空。并将 capacity 和 top 两个变量置 0即可。

void StackDestroy(ST* ps)
{
	assert(ps);

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

3.5 判断栈是否为空

我们起初设定 top = 0，所以判断栈是否为空，那么只需要看 top 是否为0就可以了。如果为0，返回真 ；不为0，返回假。

bool StackEmpty(ST* ps)
{
	assert(ps);
	
    // 如果 ps->top == 0，返回真
    // 如果 ps->top !=0，返回假
	return ps->top == 0;
}

3.6 压栈

在压栈之前，需要保证空间足够，所以需要先检查容量，如果 不够，需要扩容，扩容成功后在考虑压栈的步骤。

我们设定 top 的初始值为 0。那么说明我们入栈的步骤为，先将元素放入，再让 top++。

image-20221111005737957

void StackPush(ST* ps, STDatatype x)
{
	assert(ps);

	// 检查容量
	if (ps->top == ps->capacity)
	{
		STDatatype* tmp = (STDatatype*)realloc(ps->a, sizeof(STDatatype) * ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
	// 插入元素
	// top 为栈顶的下一个元素
	// 先插入再 ++ 
	ps->a[ps->top++] = x;
}

3.7 出栈

如果栈中没有元素则不能出栈。所以我们需要调用 StackEmpty 判断是否为空，如果栈空(!StackEmpty(ps)为假)，则断言报错。

出栈的操作和顺序表的尾删操作步骤相似，直接将top--即可。

image-20221111010231100

void StackPop(ST* ps)
{
	assert(ps);

	// 如果栈空，则不能删除
	assert(!StackEmpty(ps));
	ps->top--;
}

3.8 取栈顶元素

由于我们 top 初值设定为 0，top为栈顶的下一个位置的下标，那么 top - 1 就是栈顶的下标，直接返回即可。

但是请注意：当栈为空时，无法取元素，所以需要判断一下。

STDatatype StackTop(ST* ps)
{
	assert(ps);

	assert(!StackEmpty(ps));

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

3.9 计算栈的大小

如果一开始top = 0，那么栈的大小就直接是最后 top 的值。也非常简单~

int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

4. 完整代码

Stack.h

#pragma once

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

typedef int STDatatype;

typedef struct Stack
{
	STDatatype* a;
	int capacity;
	int top;   // 初始为0，表示栈顶位置下一个位置下标
    		   // 初始为-1，表示栈顶位置的下标
}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);

Stack.c

这里我将 top = 0 和 top = -1 的方案都写了一遍，注释部分为 top = 0，未注释部分为 top = -1：

#define _CRT_SECURE_NO_WARNINGS 1 

#include "Stack.h"

// top 为栈顶的下一个元素

//void StackInit(ST* ps)
//{
//	// 结构体一定不为空
//	assert(ps);
//
//	ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);
//	if (ps->a == NULL)
//	{
//		perror("malloc fail");
//		exit(-1);
//	}
//	ps->capacity = 4;
//	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->top == ps->capacity)
//	{
//		STDatatype* tmp = (STDatatype*)realloc(ps->a, sizeof(STDatatype) * ps->capacity * 2);
//		if (tmp == NULL)
//		{
//			perror("realloc fail");
//			exit(-1);
//		}
//		ps->a = tmp;
//		ps->capacity *= 2;
//	}
//	// 插入元素
//	// top 为栈顶的下一个元素
//	// 先插入再 ++ 
//	ps->a[ps->top++] = x;
//}
//
//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;
//}

// top 为栈顶 初识值为 -1

void StackInit(ST* ps)
{
	// 结构体一定不为空
	assert(ps);

	ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = -1;
}

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

	// 检查容量
	// 此时 top 一开始为 -1，不能表示栈中元素的数目
	// top + 1 才是正确的

	if (ps->top + 1 == ps->capacity)
	{
		STDatatype* tmp = (STDatatype*)realloc(ps->a, sizeof(STDatatype) * ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
	// 插入元素
	// top 为栈顶元素
	// 先 ++ 再插入
	ps->a[++ps->top] = x;
}

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

bool StackEmpty(ST* ps)
{
	assert(ps);

	return ps->top == -1;
}

int StackSize(ST* ps)
{
	assert(ps);

	return ps->top + 1;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1 

#include "Stack.h"

void TestST1()
{
	ST st;
	StackInit(&st);

	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 5);

	StackPop(&st);
	StackPop(&st);
	StackPop(&st);
	StackPop(&st);


	printf("%d\n", StackTop(&st));

}

int main()
{
	TestST1();
}

5. OJ题 —— 有效的括号

由于我们刚刚学习了栈，而栈实现也比较简单，那么我们就趁热打铁做上一道OJ吧！

链接：20. 有效的括号

描述：

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

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例1：

输入：s = “()”
输出：true

示例2：

输入：s = “()[]{}”
输出：true

示例3：

输入：s = “(]”
输出：false

提示：

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

思路：

既然这道题目出现在这篇博客中，那么一定是用 栈 来解决，而且这道题目的解题思路是十分符合 栈 的。

首先，我们先要实现一个栈，并创建变量和初始化。

题目要求 左括号 需要以正确的顺序闭合，且左右括号成对，那么我们可以遍历字符串 s。

遍历过程中让 左括号入栈，一旦遇到 右括号 便 取栈顶元素 和右括号匹配，并 出栈元素。

一旦匹配失败，便返回 false。如果匹配成功，则让 s++ 往后走。

当字符串遍历结束时，判断栈是否为空，如果栈空，则说明为有效的括号；如果栈非空，则说明有左括号没有匹配，那么返回假。(这里只需要返回栈是否为空的值即可)

image-20221111023107879

但是也有一些 易错情况，比如字符串遍历结束，栈中仍有元素：

image-20221111021813951

只有右括号，无左括号，栈空，取元素时越界访问：

image-20221111022037352

注：只有右括号时为提前返回状况。提前返回需要注意栈的销毁，否则会内存泄漏 ！！！

image-20221111021406183

代码：

typedef int STDatatype;

typedef struct Stack
{
	STDatatype* a;
	int capacity;
	int top;   // 初始为0，表示栈顶位置下一个位置下标
}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 = (STDatatype*)malloc(sizeof(STDatatype) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	ps->capacity = 4;
	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->top == ps->capacity)
	{
		STDatatype* tmp = (STDatatype*)realloc(ps->a, sizeof(STDatatype) * ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
	// 插入元素
	// top 为栈顶的下一个元素
	// 先插入再 ++ 
	ps->a[ps->top++] = x;
}

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);
            StackPop(&st);
            if ((*s == ')' && top != '(')
                || (*s == ']' && top != '[')
                || (*s == '}' && top != '{'))
            {
                return false;
            }
            else
            {
                s++;
            }
        }
    }
    // 判断遍历结束后，栈是否为空
    bool ans = StackEmpty(&st);
    // 销毁栈
    StackDestroy(&st);
    return ans;
}

6. 结语

到这里，本篇博客就到此结束了。本篇文章对于顺序栈进行了实现，而这也是我们目前为止实现过最简单的一个数据结构。所以相对比较容易理解，建议大家也下去练习一下~

之后我会在更新数据结构的同时也更新一些 Linux 的博客，我们敬请期待~

如果觉得anduin写的还不错的话，还请一键三连！如有错误，还请指正！

我是anduin，一名C语言初学者，我们下期见！

相关文章：

  • Hive笔记
  • 趣味益智小游戏 三子棋+五子棋 优化版（可任意选择棋盘大小）
  • MySQL : 彻底搞懂一条SQL的执行过程
  • 【成为红帽工程师】第三天 web服务器
  • 【Node.js实战】一文带你开发博客项目（API 对接 MySQL）
  • 鸿蒙开发套件全面升级，助力鸿蒙生态蓬勃发展
  • HTML期末大作业——游戏介绍(HTML+CSS+JavaScript) web前端开发技术 web课程设计网页规划与设计 Web大学生网页成品
  • 读书笔记：《高频交易员》
  • HTML小游戏6 —— 《高达战争》横版射击游戏（附完整源码）
  • 【深度学习】第三章：卷积神经网络
  • 几款很好看的爱心表白代码（动态）
  • C语言百日刷题第六天
  • 表白爱心代码
  • linux无界面手敲命令笔记
  • OSPF高级配置——虚接口，NSSA
  • 【140天】尚学堂高淇Java300集视频精华笔记（86-87）
  • iOS仿今日头条、壁纸应用、筛选分类、三方微博、颜色填充等源码
  • js作用域和this的理解
  • Netty+SpringBoot+FastDFS+Html5实现聊天App(六)
  • Python进阶细节
  • 关于 Linux 进程的 UID、EUID、GID 和 EGID
  • 近期前端发展计划
  • 理解 C# 泛型接口中的协变与逆变（抗变）
  • 你真的知道 == 和 equals 的区别吗？
  • 前端相关框架总和
  • 使用API自动生成工具优化前端工作流
  • 微信公众号开发小记——5.python微信红包
  • 微信如何实现自动跳转到用其他浏览器打开指定页面下载APP
  • [Shell 脚本] 备份网站文件至OSS服务（纯shell脚本无sdk） ...
  • elasticsearch-head插件安装
  • 如何通过报表单元格右键控制报表跳转到不同链接地址 ...
  • !!【OpenCV学习】计算两幅图像的重叠区域
  • #中国IT界的第一本漂流日记 传递IT正能量# 【分享得“IT漂友”勋章】
  • （1）安装hadoop之虚拟机准备（配置IP与主机名）
  • （2.2w字）前端单元测试之Jest详解篇
  • （Note）C++中的继承方式
  • （附源码）计算机毕业设计SSM教师教学质量评价系统
  • （力扣）循环队列的实现与详解（C语言）
  • (六)库存超卖案例实战——使用mysql分布式锁解决“超卖”问题
  • （十）c52学习之旅-定时器实验
  • （四）汇编语言——简单程序
  • (原創) 如何動態建立二維陣列(多維陣列)? (.NET) (C#)
  • （转）http-server应用
  • (转)scrum常见工具列表
  • （转）人的集合论——移山之道
  • （转载）PyTorch代码规范最佳实践和样式指南
  • .NET Core 中插件式开发实现
  • .NET Core工程编译事件$(TargetDir)变量为空引发的思考
  • .NET MVC、 WebAPI、 WebService【ws】、NVVM、WCF、Remoting
  • .NET 药厂业务系统 CPU爆高分析
  • .NET/C# 使窗口永不获得焦点
  • .NET6使用MiniExcel根据数据源横向导出头部标题及数据
  • .NetCore项目nginx发布
  • @在php中起什么作用？
  • [\u4e00-\u9fa5] //匹配中文字符