当前位置: 首页 > 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曝光在晶圆上形成图…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...