数据结构(功能受限的表-栈队列)
功能受限的表结构
一、栈和队列介绍
-
栈和队列是两种重要的线性结构,从数据结构角度,他们都是线性表,特殊点在于它们的操作被限制,也就是所谓的功能受限,统称功能受限的线性表
-
从数据类型角度,它们也可以是看成处理、管理数据的一种规则
二、栈结构
-
栈(stack)是限定在表尾进行数据的插入、删除等操作的线性表(只允许操作一个端口的数据)
-
表尾称为栈顶,表头称为栈底 ,当没有元素的空表称为空栈,当元素的数量到达栈的容量时称为满栈 ,添加数据到栈顶中的动作称为入栈、压栈,把数据从栈顶中拿出的动作称为出栈、弹栈,正因为这个数据的添加、删除的规则,所以栈中元素满足先进后出,简称FILO表、LIFO
-
栈结构可以具备的功能
-
创建
-
销毁
-
是否满栈
-
是否空栈
-
入栈
-
出栈
-
查看栈顶元素
-
查看元素数量
注意:只有顺序栈才有需要判断栈是否满
-
1、栈结构的顺序实现
// 设计顺序栈结构 typedef struct ArrayStack {TYPE* ptr; // 存储栈元素的内存首地址size_t cap; // 栈的容量size_t top; // 栈顶的位置 }ArrayStack;
2、栈结构常考笔试题
-
对一个栈的入栈、出栈序列进行正确性判断
-
入栈顺序: 1 2 3 4 5
-
出栈顺序:1 2 3 4 5 正确 1 2 4 3 5 正确 2 1 5 3 4错误 5 4 3 2 1
-
-
编程题:实现一个函数,判断序列B是否是序列A的出栈顺序
// 判断出栈顺序是否正确 bool is_pop(int* a,int* b,size_t len) {// 创建一个栈ArrayStack* stack = create_array_stack(len);// 按照a顺序入栈for(int i=0,j=0; i<len; i++){ push_array_stack(stack,a[i]);// 按照b的顺序出栈,一直出到无法出栈为止int val = 0;// 栈非空,且栈顶值等于b中要出栈的值 则出栈while(top_array_stack(stack,&val) && val == b[j]){ pop_array_stack(stack);j++;}}// 判断栈是否空,如果空,则是正确顺序bool flag = false;if(empty_array_stack(stack))flag = true;// 销毁栈destroy_array_stack(stack);return flag; }
-
如何让两个长度相同的顺序栈,实现空间利用率最大化?
-
两个栈顶的增长方向设置成相对的
-
3、栈结构的链式实现
#define TYPE int typedef struct ListNode {TYPE data;struct ListNode* next; }ListNode; ListNode* create_list_node(TYPE data) {ListNode* node = malloc(sizeof(ListNode));node->data = data;node->next = NULL;return node; } // 链式栈结构 typedef struct ListStack {ListNode* top; // 栈顶指针 指向栈顶节点size_t size; // 节点数量 }ListStack; // 创建栈 ListStack* create_list_stack(void) {ListStack* stack = malloc(sizeof(ListStack));// 因为栈不允许随意操作插入、删除操作,因此不需要头节点stack->top = NULL;stack->size = 0;return stack; } // 栈空 bool empty_list_stack(ListStack* stack) {} // 入栈 void push_list_stack(ListStack* stack,TYPE data) {} // 出栈 bool pop_list_stack(ListStack* stack) {} // 栈顶 TYPE top_list_stack(ListStack* stack) {} // 节点数 size_t size_list_stack(ListStack* stack) {} // 销毁 void destroy_list_stack(ListStack* stack) {}
4、栈的应用
-
内存管理,例如栈内存,之所以叫栈内存因为它遵循栈的先进后出原则,函数调用、函数参数的传参、定义,先把数据入栈,等结束时,逆序出栈,函数的调用、结束跳转也是遵循栈结构原则
-
特殊的算法:算术表达式的转换(中缀表达式转后缀表达) 、进制转换、迷宫算法
三、队列结构
1、队列介绍
-
与栈结构相似的是,也只允许在端口处进行添加、删除操作,但是有两个端口,一个负责添加数据,称为入队 ,该端口称为队尾,另一个端口只负责删除数据,称为出队,该端口称为队头,属于一种先进先出结构,称为FIFO
2、队列所具备的功能
-
创建队列
-
销毁队列
-
判断队空
-
判断队满 (只有顺序存储时才有)
-
入队
-
出队
-
查看队头元素
-
查看队尾元素
-
队列元素数量
3、队列的链式实现
#define TYPE int typedef struct ListNode {TYPE data;struct ListNode* next; }ListNode; ListNode* create_list_node(TYPE data) {ListNode* node = malloc(sizeof(ListNode));node->data = data;node->next = NULL;return node; } // 设计链式队列结构 typedef struct ListQueue {ListNode* front; // 队头ListNode* rear; // 队尾size_t size; // 节点数量 }ListQueue; // 创建 ListQueue* create_list_queue(void) {ListQueue* queue = malloc(sizeof(ListQueue));queue->front = NULL;queue->rear = NULL;queue->size = 0;return queue; } // 队空 bool empty_list_queue(ListQueue* queue) {return 0 == queue->size; } // 入队 void push_list_queue(ListQueue* queue,TYPE data) {ListNode* node = create_list_node(data);if(empty_list_queue(queue)){queue->front = node;}else{ queue->rear->next = node;queue->rear = node;}queue->size++; } // 出队 bool pop_list_queue(ListQueue* queue) {if(empty_list_queue(queue)) return false;ListNode* node = queue->front;queue->front = node->next;free(node);queue->size--;if(0 == queue->size) queue->rear = NULL;return true; } // 队头 TYPE front_list_queue(ListQueue* queue) {return queue->front->data; } // 队尾 TYPE rear_list_queue(ListQueue* queue) {return queue->rear->data; } // 数量 size_t size_list_queue(ListQueue* queue) {return queue->size; } // 销毁 void destroy_list_queue(ListQueue* queue) {while(pop_list_queue(queue));free(queue); }
4、队列的顺序实现
-
顺序队列的队尾下标rear会随着入队而增大rear+1,队头下标front会随着出队增大front+1,因为是顺序结构,就有随着入队和出队的进行,可能超出有效的下标范围,如果不进行处理,那么队列无法重复使用。
-
为了避免这种情况,当队尾、队头下标达到存储空间的末尾时,要想办法让它们回到内存的开头位置,相当于把内存想象成一个环形,从而可以循环使用队列,这样的队列称为循环队列
-
因此当队尾、队头下标增加时,都要对队列的容量求余
-
rear = (rear+1)%cap
-
front = (front+1)%cap
-
带计数器版本的循环队列
-
很直接地解决了元素数量的问题
-
可以直接解决队空、队满的判断矛盾问题
-
但是在队列结构中会多增加一个数据项,并且每次入队、出队操作都要对其进行修改
typedef struct ArrayQueue {TYPE* ptr; // 存储元素的内存首地址size_t cap; // 容量size_t cnt; // 元素个数 计数器int front; // 队头下标int rear; // 队尾下标 }ArrayQueue; // 创建 ArrayQueue* create_array_queue(size_t cap) {ArrayQueue* queue = malloc(sizeof(ArrayQueue));queue->ptr = malloc(sizeof(TYPE)*cap);queue->cap = cap;queue->cnt = 0;queue->front = 0;qeueu->rear = -1; // rear指向队尾元素return queue; } // 销毁 void destroy_array_queue(ArrayQueue* queue){} // 队满 bool full_array_queue(ArrayQueue* queue){} // 队空 bool empty_array_queue(ArrayQueue* queue){} // 入队 bool push_array_queue(ArrayQueue* queue,TYPE data){} // 出队 bool pop_array_queue(ArrayQueue* queue){} // 队头 TYPE front_array_queue(ArrayQueue* queue){} // 队尾 TYPE rear_array_queue(ArrayQueue* queue){} // 数量 size_t size_array_queue(ArrayQueue* queue){}
不带计数器的版本
相关文章:
数据结构(功能受限的表-栈队列)
功能受限的表结构 一、栈和队列介绍 栈和队列是两种重要的线性结构,从数据结构角度,他们都是线性表,特殊点在于它们的操作被限制,也就是所谓的功能受限,统称功能受限的线性表 从数据类型角度,它们也可以是…...

高数知识补充----矩阵、行列式、数学符号
矩阵计算 参考链接:矩阵如何运算?——线性代数_矩阵计算-CSDN博客 行列式计算 参考链接:实用的行列式计算方法 —— 线性代数(det)_det线性代数-CSDN博客 参考链接:行列式的计算方法(含四种,…...

《Techporters架构搭建》-Day01 第一个RESTful API接口
微服务架构搭建 搭建微服务架构分析一下项目的build.gradle添加Demo接口 搭建微服务架构 首先搭建系统管理模块,模块结构如下 tps-cloud └── tps-system -- 系统管理模块└── tps-system-api -- 系统管理模块公共api模块└── tps-system-biz -- 系统管理模…...

【C++ —— AVL树】
C —— AVL树 AVL树的概念AVL树节点的定义AVL树的插入向上调整旋转左单旋右单旋左右双旋右左双旋 AVL树的高度AVL树的验证总结:代码 AVL树的概念 二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素…...
跨平台webSocket模块设计技术解决方案
1. 概述 目标:设计并实现一个能够在多种操作系统上运行的WebSocket通讯模块,支持与前端浏览器和HTTPS服务端进行数据交换。技术栈:C11 ,使用跨平台库如 Boost处理网络IO,使用 JSON 库如 nlohmann/json 解析消息。 2.…...

Drools规则引擎
一、Drools规则引擎 Drools官网: https://www.drools.org/Drools中文网: http://www.drools.org.cn/bilibili学习视频(黑马博学谷2020年最新Java项目Drools业务规则管理系统(BRMS)): https://www.bilibili.com/video/BV1Pa4y1a7u…...

vue学习day11-路由、路由模块的封装、声明式导航-路由的介绍、VueRouter、router-link、自定义高亮类名
32、路由 (1)路由的介绍 1)生活中的路由:设备和ip的映射关系 2)路由:一种映射关系 3)Vue中的路由:路径与组件的映射关系 (根据路由就能知道不同的路径,应…...

智慧校园学期基础数据管理
在智慧校园基础数据管理之一的学期管理功能管理中,学期的有序管理具有重要意义。它不仅是教学活动有序开展的指挥棒,更是连接学校管理者、教师与学生之间沟通的桥梁,承载着规划、跟踪与管理学期内各项事务的重要使命。 学期管理功能的首要任务…...

ISP代理和双ISP代理:区别和优势
随着互联网技术的不断发展和普及,网络代理服务成为众多用户保护隐私、提高网络性能、增强安全性的重要工具。其中,ISP代理和双ISP代理是两种常见的网络代理服务形式。本文将详细探讨ISP代理和双ISP代理的区别和优势,以便用户更好地了解并选择…...

【雷丰阳-谷粒商城 】【分布式高级篇-微服务架构篇】【22】【RabbitMQ】
持续学习&持续更新中… 守破离 【雷丰阳-谷粒商城 】【分布式高级篇-微服务架构篇】【22】【RabbitMQ】 Message Queue 消息队列异步处理应用解耦流量控制 消息中间件概念RabbitMQ概念MessagePublisherExchangeQueueBindingConnectionChannelConsumerVirtual HostBroker图…...
概率论原理精解【4】
文章目录 度量空间概述理论基础定义特点高级概念广泛应用 性质例子应用 柯西数列柯西数列的定义柯西数列的例子 参考文献 度量空间 概述 设 f : R n → R m , f ˙ ( x ) 在 { x : ∣ x − x 0 ∣ < r } 内连续,则当 ∣ t ∣ < r 时, f:R^n\righ…...

Linux云计算 |【第一阶段】ENGINEER-DAY3
主要内容: LVM逻辑卷管理、VDO、RAID磁盘阵列、进程管理 一、新建逻辑卷 1、什么是逻辑卷 逻辑卷(Logical Volume)是逻辑卷管理(Logical Volume Management,LVM)系统中的一个概念。LVM是一种用于磁盘管理…...

springboot 实体类加注解校验入参数据
导入的是springboot自身的依赖包 import org.springframework.validation.annotation.Validated; import org.springframework.web.bind.annotation.*; import javax.validation.Valid;...

关于 Qt输入法在arm特定的某些weston下出现调用崩溃 的解决方法
若该文为原创文章,转载请注明原文出处 本文章博客地址:https://hpzwl.blog.csdn.net/article/details/140423667 长沙红胖子Qt(长沙创微智科)博文大全:开发技术集合(包含Qt实用技术、树莓派、三维、OpenCV…...
Android Studio关于Gradle及JDK问题解决
1.Android Studio 版本如:Android Studio Koala | 2024.1.1 2.Gradle 版本为:8.7 3.JDK 版本为:17 以上这三个必须匹配,具体可以看官网Android Studio 版本说明(https://developer.android.google.cn/studio?hlzh-…...
Leetcode 205. 同构字符串
205. 同构字符串 Leetcode 205. 同构字符串 一、题目描述二、我的想法三、其他人的题解 一、题目描述 给定两个字符串 s 和 t ,判断它们是否是同构的。 如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的。 每个出现的字符都应…...

多口适配器,给您的生活增添便利
随着科技的快速发展,我们的生活已离不开各种各样的电子设备,智能手机、平板电脑、智能手表、无线耳机……它们共同构建了我们丰富多彩的数字生活。然而,面对众多设备的充电需求,传统的单一充电口已难以满足现代人的使用习惯。在这…...
探索现代Web开发:WebKit的剪贴板API革新
探索现代Web开发:WebKit的剪贴板API革新 在当今的Web开发领域,用户体验的提升是开发者们不懈追求的目标。其中一个关键的交互点便是剪贴板操作,它允许用户在网页与本地系统之间复制和粘贴数据。WebKit,作为Safari、QQ浏览器等众多…...

【电路笔记】-放大器的频率响应
放大器的频率响应 文章目录 放大器的频率响应1、概述2、定义3、电容器的影响4、低频响应5、高频响应6、总结1、概述 对于任何电子电路来说,放大器的行为都会受到其输入端子上信号频率的影响。 该特性称为频率响应。 频率响应是放大器最重要的特性之一。 在放大器设计的频率范…...

Artix7系列FPGA实现SDI视频编解码,基于GTP高速接口,提供3套工程源码和技术支持
目录 1、前言工程概述免责声明 2、相关方案推荐本博已有的 SDI 编解码方案本方案在Xilinx--Kintex系列FPGA上的应用本方案在Xilinx--Zynq系列FPGA上的应用 3、详细设计方案设计原理框图SDI 输入设备Gv8601a 均衡器GTP 高速接口-->解串与串化SMPTE SD/HD/3G SDI IP核BT1120转…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...

华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...

使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...

基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...

零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...