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

栈及笔试题

目录

栈的实现

1、数组栈

2、链式栈

栈的创建

栈的打印

内存泄漏

栈溢出

练习

有效的括号


栈的实现

栈后入先出

1、数组栈

最佳实现,且访问数据的时候CPU告诉访存命中率比较高,因为地址连续存放,访问时CPU从cache里一次访问一片)

数组适合尾插尾删,所以栈底在数组头部

以下实现的就是数组栈

2、链式栈

双向链表,栈底可以是尾也可以是头

单链表,头插头删方便,所以栈顶在链表尾部

(单链表的头插头删方便在:

        头插:加减新节点只需要修改头指针指向新的节点,时间复杂度通常是O(1)

        尾插:需要遍历整个链表才能找到最后一个节点并将其之后的位置设置为新节点或者释放结点,时间复杂度是O(n)

栈的创建

栈的打印

以下是单链表的打印

此为栈的打印

栈访问一遍就已经空了

内存泄漏

后端开发,比如游戏上线了之后除了升级就不能退出,所以如果存在内存泄漏就会导致游戏越来越慢,因为可用内存资源越来越少

如果是在前端操作系统里出现了内存泄漏的情况,在进程结束掉之后就会主动释放空间,所以危害性不大

栈溢出

指的是给这个栈划分的内存区域爆了,比如写了一个死循环的递归

Stack.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int STDataType;typedef struct Stack {int* 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

#define  _CRT_SECURE_NO_WARNINGS
#include"Stack.h"
void STInit(ST* pst) {assert(pst);pst->a = NULL;pst->capacity = 0;pst->top = 0;
}
void STDestroy(ST* pst) {assert(pst);free(pst->a);pst->a = NULL;pst->capacity = 0;pst->top = 0;
}
void STPush(ST* pst, STDataType x) {assert(pst);if (pst->top == pst->capacity) {int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);if (tmp == NULL) {perror("relloc");return;}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top] = x;//在a[0]的时候放入第一个值pst->top++;
}
void STPop(ST* pst) {assert(pst);assert(pst->top > 0);//不为空pst->top--;
}STDataType STTop(ST* pst) {assert(pst);assert(pst->top > 0);//不为空return pst->a[pst->top - 1];
}
bool STEmpty(ST* pst) {assert(pst);return pst->top == 0;//等于0返回真,不等于0返回假
}
int STSize(ST* pst) {assert(pst);return pst->top;
}

Test.c

#define  _CRT_SECURE_NO_WARNINGS
#include"Stack.h"void Test() {ST s;STInit(&s);STPush(&s, 1);STPush(&s, 2);STPush(&s, 3);STPush(&s, 4);while (!STEmpty(&s)) {printf("%d ", STTop(&s));//打印栈顶位置的数据STPop(&s);//弹栈}printf("\n");
}int main() {Test();return 0;
}

练习

有效的括号

数量和顺序都要匹配

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef char 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);void STInit(ST* pst) {assert(pst);pst->a = NULL;pst->capacity = 0;pst->top = 0;
}
void STDestroy(ST* pst) {assert(pst);free(pst->a);pst->a = NULL;pst->capacity = 0;pst->top = 0;
}
void STPush(ST* pst, STDataType x) {assert(pst);if (pst->top == pst->capacity) {int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);if (tmp == NULL) {perror("relloc");return;}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top] = x;//在a[0]的时候放入第一个值pst->top++;
}
void STPop(ST* pst) {assert(pst);assert(pst->top > 0);//不为空pst->top--;
}STDataType STTop(ST* pst) {assert(pst);assert(pst->top > 0);//不为空return pst->a[pst->top - 1];
}
bool STEmpty(ST* pst) {assert(pst);return pst->top == 0;//等于0返回真,不等于0返回假
}
int STSize(ST* pst) {assert(pst);return pst->top;
}bool isValid(char* s) {ST st;STInit(&st);while(*s){if(*s == '{' || *s == '[' || *s == '('){//*s是左括号就入栈STPush(&st, *s);}else{//右比左多,会导致循环时栈为空,还要弹栈if(STEmpty(&st)){//防止内存泄漏STDestroy(&st);return false;}//*s是右括号就与栈顶匹配char top = STTop(&st);STPop(&st);//检查顺序匹配if((*s == '}' && top != '{')||(*s == ']' && top != '[')||(*s == ')' && top != '(')){STDestroy(&st);return false;}}++s;}//检查数量匹配//左多右少bool ret = STEmpty(&st);//等于0就返回真,不等于0就返回假STDestroy(&st);return ret;
}

相关文章:

栈及笔试题

目录 栈的实现 1、数组栈 2、链式栈 栈的创建 栈的打印 内存泄漏 栈溢出 练习 有效的括号 栈的实现 栈后入先出 1、数组栈 &#xff08;最佳实现&#xff0c;且访问数据的时候CPU告诉访存命中率比较高&#xff0c;因为地址连续存放&#xff0c;访问时CPU从cache里一…...

【工程测试技术】第3章 测试装置的基本特性,静态特性和动态特性,一阶二阶系统的特性,负载效应,抗干扰性

目录 3.1 概述 1测量装置的静态特性 2.标准和标准传递 3.测量装置的动态特性 4.测量装置的负载特性 5.测量装置的抗干扰性 1.线性度 2.灵敏度 3.回程误差 4.分辨力 5.零点漂移和灵敏度漂移 3.3.1 动态特性的数学描述 1.传递函数 2.频率响应函数 3.脉冲响应函数 …...

ireport 5.1 中文生辟字显示不出来,生成PDF报字体找不到

ireport生成pdf里文字不显示。本文以宋体中文字不显示为例。 问题&#xff1a;由浅入深一步一步分析 问题1、预览正常&#xff0c;但生成pdf中文不显示 报告模板编辑后&#xff0c;预览正常&#xff0c;但生成pdf中文不显示。以下是试验过程&#xff1a; 先编辑好一个报告单模…...

给Ubuntu虚拟机设置静态IP地址(固定IP)

查看 为Ubuntu虚拟机配置静态IP地址&#xff08;固定IP&#xff09;的方法经过亲自测试&#xff0c;已被证实有效。 这里你记得网关就可以了&#xff0c;等下要用 查看配置前的网络信息 ifconfig 查看网关 route -n 配置 配置网络文件 cd /etc/netplan/ ls 查看自己的文件的名…...

spring boot文件上传之x-file-storage

spring boot文件上传之x-file-storage 今天看到一个文件上传的开源组件x-file-storage&#xff0c;官方地址如下&#xff1a; https://x-file-storage.xuyanwu.cn/#/ 该组件官网是这样介绍的&#xff0c;如下&#xff1a; 一行代码将文件存储到本地、FTP、SFTP、WebDAV、阿…...

Object.values() 、 Object.keys()

拿到当前对象里面的value值 // 假设你有一个对象 const myObject {name: Kimi,age: 30,country: Moon };// 获取对象的所有值 const values Object.values(myObject);// 输出值数组 console.log(values); // ["Kimi", 30, "Moon"] 如果你需要在 Vue 组…...

脸爱云管理系统存在任意文件上传漏洞

漏洞描述 脸爱云一脸通智慧管理平台是一套功能强大、运行稳定、操作简单方便、用户界面美观的一脸通系统。该平台整合了人脸识别技术和智能化解决方案&#xff0c;可以实现识别和管理个体身份&#xff0c;为各种场景提供便捷的身份验证和管理功能。其存在任意文件上传漏洞&…...

elasticsearch_exporter启动报错 failed to fetch and decode node stats

最近把服务器迁移到了ubuntu系统&#xff0c;结果发现在centos还正常运行的elasticsearch_exporter&#xff0c;用systemd启动后一直报错 failed to fetch and decode node stats 在网上翻了大半年&#xff0c;竟然都无解&#xff01;这种报错&#xff0c;很明显就是你的ES密码…...

Git 使用方法

简介 Git常用命令 Git 全局设置 获取Git 仓库 方法二用的比较多 将仓库链接复制 在 git base here ----> git clone 仓库链接 工作区、暂存区、版本库 Git 工作区中文件中的状态 本地仓库的操作 远程仓库操作 git pull 将代码推送到远程仓库 1. git add 文件名 ---放…...

生产环境升级mysql流程及配置主从服务

之前写到过mysql升级8.4的文章, 因此不再介绍mysql的安装过程 避免服务器安装多个mysql引起冲突的安装方法_安装两个mysql会冲突吗-CSDN博客 生产环境升级mysql8.4.x流程 安装mysql 参考之前文章: 避免服务器安装多个mysql引起冲突的安装方法_安装两个mysql会冲突吗-CSDN博客…...

论软件体系结构的演化

摘要 2022年3月&#xff0c;我加入了公司的新智慧公交平台项目研发团队&#xff0c;并担任系统架构师角色&#xff0c;负责系统整体架构的设计与评审。该项目采用了物联网三层架构模型&#xff0c;其中设备接入层和网络交互层基于公司的中台战略&#xff0c;我们有效复…...

【go入门】常量

目录 定义枚举iota思考题 定义 go语言常量的定义和其他语言类似&#xff0c;常量中的数据类型只能是布尔型&#xff0c;数字型&#xff08;整型、浮点型、复数&#xff09;和字符串型 常量的定义方式和变量一样&#xff0c;只不过变量定义使用 var 关键字&#xff0c;而常量定…...

2.1 HuggingFists系统架构(二)

部署架构 上图为HuggingFists的部署架构。从架构图可知&#xff0c;HuggingFists主要分为服务器(Server)、计算节点(Node)以及数据库(Storage)三部分。这三部分可以分别部署在不同的机器上&#xff0c;以满足系统的性能需求。为部署方便&#xff0c;HuggingFists社区版将这三部…...

工具类:JWT

工具类&#xff1a;JWT 依赖JwtUtil.java 依赖 <!-- 创建、解析 和 验证JSON Web Tokens (JWT)--><dependency><groupId>io.jsonwebtoken</groupId><artifactId>jjwt</artifactId><version>0.9.1</version></dependenc…...

王道-计网

2 采用滑动窗口机制对两个相邻结点A(发送方)和B(接收方)的通信过程进行流量控制。假定帧的序号长度为3比特,发送窗口与接收窗口的大小均为7,当A发送了编号为0、1、2、3这4个帧后,而B接收了这4个帧,但仅应答了0、1两个帧,A继续发送4、5两个帧,且这两个帧已进入B的接收…...

【机器学习(十)】时间序列案例之月销量预测分析—Holt-Winters算法—Sentosa_DSML社区版

文章目录 一、Holt-Winters算法原理(一) 加法模型(二) 乘法模型(三) 阻尼趋势 二、Holt Winters算法优缺点优点缺点 三、Python代码和Sentosa_DSML社区版算法实现对比(一) 数据读入和统计分析(二) 数据预处理(三) 模型训练和模型评估(四) 模型可视化 四、总结 一、Holt-Winters…...

Webpack优化问题

目录 打包流程swcthread-loaderhash升级插件 打包流程 webpack 的打包流程大致可以分为以下几个步骤&#xff1a; 初始化&#xff1a;webpack 通过配置文件和 Shell 参数&#xff0c;初始化参数&#xff0c;确定入口文件、输出路径、加 载器、插件等信息。接下来读取配置文件…...

yjs10——pandas的基础操作

1.pandas读入文件——pd.read_cvs() data pd.read_csv("E:/机器学习/data/salary.csv") 注意&#xff1a;1.是pd.read_cvs&#xff0c;不要顺手写成np.read_cvs 2.路径的斜杠方向是/&#xff0c;不是\&#xff0c;如果直接从电脑粘贴路径&#xff0c;路径写法是\&am…...

Squaretest单元测试辅助工具使用

1、idea安装插件 Squaretest 然后关掉idea 2、安装字节码软件&#xff08;jclasslib&#xff09; 3、找到idea里面的Squaretest安装目录 找到包含TestStarter的jar包 4、打开 com.squaretest.c.f 打开后选择常量池 5、找到第16个修改 Long value值&#xff0c;修改的数字即为使…...

MFU简介

1、缩写 MFU - Mask Field Utilization&#xff08;光刻掩膜版有效利用比例&#xff09; GDPW - Gross Die Per Wafer&#xff0c;每张wafer上die的数量 2、什么是MASK 在光刻机中&#xff0c;光源&#xff08;紫外光、极紫外光&#xff09;透过mask曝光在晶圆上形成图…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...