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

数据结构(功能受限的表-栈队列)

功能受限的表结构

一、栈和队列介绍
  • 栈和队列是两种重要的线性结构,从数据结构角度,他们都是线性表,特殊点在于它们的操作被限制,也就是所谓的功能受限,统称功能受限的线性表

  • 从数据类型角度,它们也可以是看成处理、管理数据的一种规则

二、栈结构
  • 栈(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){}   
不带计数器的版本

相关文章:

数据结构(功能受限的表-栈队列)

功能受限的表结构 一、栈和队列介绍 栈和队列是两种重要的线性结构&#xff0c;从数据结构角度&#xff0c;他们都是线性表&#xff0c;特殊点在于它们的操作被限制&#xff0c;也就是所谓的功能受限&#xff0c;统称功能受限的线性表 从数据类型角度&#xff0c;它们也可以是…...

高数知识补充----矩阵、行列式、数学符号

矩阵计算 参考链接&#xff1a;矩阵如何运算&#xff1f;——线性代数_矩阵计算-CSDN博客 行列式计算 参考链接&#xff1a;实用的行列式计算方法 —— 线性代数&#xff08;det&#xff09;_det线性代数-CSDN博客 参考链接&#xff1a;行列式的计算方法(含四种&#xff0c;…...

《Techporters架构搭建》-Day01 第一个RESTful API接口

微服务架构搭建 搭建微服务架构分析一下项目的build.gradle添加Demo接口 搭建微服务架构 首先搭建系统管理模块&#xff0c;模块结构如下 tps-cloud └── tps-system -- 系统管理模块└── tps-system-api -- 系统管理模块公共api模块└── tps-system-biz -- 系统管理模…...

【C++ —— AVL树】

C —— AVL树 AVL树的概念AVL树节点的定义AVL树的插入向上调整旋转左单旋右单旋左右双旋右左双旋 AVL树的高度AVL树的验证总结&#xff1a;代码 AVL树的概念 二叉搜索树虽可以缩短查找的效率&#xff0c;但如果数据有序或接近有序二叉搜索树将退化为单支树&#xff0c;查找元素…...

跨平台webSocket模块设计技术解决方案

1. 概述 目标&#xff1a;设计并实现一个能够在多种操作系统上运行的WebSocket通讯模块&#xff0c;支持与前端浏览器和HTTPS服务端进行数据交换。技术栈&#xff1a;C11 &#xff0c;使用跨平台库如 Boost处理网络IO&#xff0c;使用 JSON 库如 nlohmann/json 解析消息。 2.…...

Drools规则引擎

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

vue学习day11-路由、路由模块的封装、声明式导航-路由的介绍、VueRouter、router-link、自定义高亮类名

32、路由 &#xff08;1&#xff09;路由的介绍 1&#xff09;生活中的路由&#xff1a;设备和ip的映射关系 2&#xff09;路由&#xff1a;一种映射关系 3&#xff09;Vue中的路由&#xff1a;路径与组件的映射关系 &#xff08;根据路由就能知道不同的路径&#xff0c;应…...

智慧校园学期基础数据管理

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

ISP代理和双ISP代理:区别和优势

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

【雷丰阳-谷粒商城 】【分布式高级篇-微服务架构篇】【22】【RabbitMQ】

持续学习&持续更新中… 守破离 【雷丰阳-谷粒商城 】【分布式高级篇-微服务架构篇】【22】【RabbitMQ】 Message Queue 消息队列异步处理应用解耦流量控制 消息中间件概念RabbitMQ概念MessagePublisherExchangeQueueBindingConnectionChannelConsumerVirtual HostBroker图…...

概率论原理精解【4】

文章目录 度量空间概述理论基础定义特点高级概念广泛应用 性质例子应用 柯西数列柯西数列的定义柯西数列的例子 参考文献 度量空间 概述 设 f : R n → R m , f ˙ ( x ) 在 { x : ∣ x − x 0 ∣ < r } 内连续&#xff0c;则当 ∣ t ∣ < r 时&#xff0c; f:R^n\righ…...

Linux云计算 |【第一阶段】ENGINEER-DAY3

主要内容&#xff1a; LVM逻辑卷管理、VDO、RAID磁盘阵列、进程管理 一、新建逻辑卷 1、什么是逻辑卷 逻辑卷&#xff08;Logical Volume&#xff09;是逻辑卷管理&#xff08;Logical Volume Management&#xff0c;LVM&#xff09;系统中的一个概念。LVM是一种用于磁盘管理…...

springboot 实体类加注解校验入参数据

导入的是springboot自身的依赖包 import org.springframework.validation.annotation.Validated; import org.springframework.web.bind.annotation.*; import javax.validation.Valid;...

关于 Qt输入法在arm特定的某些weston下出现调用崩溃 的解决方法

若该文为原创文章&#xff0c;转载请注明原文出处 本文章博客地址&#xff1a;https://hpzwl.blog.csdn.net/article/details/140423667 长沙红胖子Qt&#xff08;长沙创微智科&#xff09;博文大全&#xff1a;开发技术集合&#xff08;包含Qt实用技术、树莓派、三维、OpenCV…...

Android Studio关于Gradle及JDK问题解决

1.Android Studio 版本如&#xff1a;Android Studio Koala | 2024.1.1 2.Gradle 版本为&#xff1a;8.7 3.JDK 版本为&#xff1a;17 以上这三个必须匹配&#xff0c;具体可以看官网Android Studio 版本说明&#xff08;https://developer.android.google.cn/studio?hlzh-…...

Leetcode 205. 同构字符串

205. 同构字符串 Leetcode 205. 同构字符串 一、题目描述二、我的想法三、其他人的题解 一、题目描述 给定两个字符串 s 和 t &#xff0c;判断它们是否是同构的。 如果 s 中的字符可以按某种映射关系替换得到 t &#xff0c;那么这两个字符串是同构的。 每个出现的字符都应…...

多口适配器,给您的生活增添便利

随着科技的快速发展&#xff0c;我们的生活已离不开各种各样的电子设备&#xff0c;智能手机、平板电脑、智能手表、无线耳机……它们共同构建了我们丰富多彩的数字生活。然而&#xff0c;面对众多设备的充电需求&#xff0c;传统的单一充电口已难以满足现代人的使用习惯。在这…...

探索现代Web开发:WebKit的剪贴板API革新

探索现代Web开发&#xff1a;WebKit的剪贴板API革新 在当今的Web开发领域&#xff0c;用户体验的提升是开发者们不懈追求的目标。其中一个关键的交互点便是剪贴板操作&#xff0c;它允许用户在网页与本地系统之间复制和粘贴数据。WebKit&#xff0c;作为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转…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...