数据结构——第三章 栈与队列(5)
共用栈和双队列
- 1.共用栈
- 2.双端队列
- 栈与队列的本章小节
1.共用栈
在实际应用中,有时一个应用程序需要多个栈,但这些栈的数据元素类型相同。假设每个栈都采用顺序栈,由于每个栈的使用情况不尽相同,势必会造成存储空间的浪费。若让多个栈共用一个足够大的连续存储空间,则可利用的动态特性使它们的存储空间互补。这时的操作必须同时记住多个栈的栈顶。
为使操作更加方便,可采用多个单链表,将它们的栈顶存放到一个指针数组中。
顺序栈的共享最常见的两栈的共享。假设两个栈共享一维数组s[MAXNUM],其中一个栈的栈顶用topl指示,另一个栈的栈顶用top2指示。
共享栈的数据类型描述如下:
typedef int SElemType;
typedef struct ShareStack
{SElemType data[MAXNUM];int top1, top2;int stackSize;
}ShareStack;
栈空:栈1空,top1==-1为真;栈2空,top2MAXNUM为真。
栈满:top1+1top2为真。
进栈操作:必须区分是对哪一个栈进操作。
int EnShareStack(ShareStack* S, SElemType x, int stacknum)
{if (S->top1 + 1 == S->top2)return 0;if (stacknum == 1)S->data[++S->top1] = x;else if (stacknum == 2)S->data[++S->top2] = x;else return 0;return 1;
}
出栈操作:必须区分是对哪一个栈进行操作。
int DeShareStack(ShareStack* S, SElemType* x, int stacknum)
{if (stacknum == 1){if (S->top1 == -1)return 0;else *x = S->data[S->top1--];}else if (stacknum == 2){if (S->top1 == S->stackSize)return 0;else *x = S->data[S->top2++];}else return 0;return 1;
2.双端队列
如果限定插入和删除操作均可以在线性表的两端进行,则称位双端队列。
这样的结构常用于计算机的CPU的调度,所谓“CPU调度”是指在多人使用一个CPU的情况下,由于CPU在同一时间只能执行一项任务,所以将每个人的工作任务事先存放在队列中,待CPU闲置时,再从队列中取出一项待执行的工作进行处理。双端队列的两端均可输出和输入,使CPU处理不同任务的请求更具灵活性。
双端队列与共用栈是不相同的。共用栈的每个栈都各自有一个栈顶都各自有一个栈顶指针,两个栈顶指针是向中间扩展;而两端队列可以看成是两个栈底连在一起的栈,在两个端点都分别设有队头和队尾两个指针,也可以对双端队列做出如下限制。
(1)只允许在一端进行插入,两端进行删除。
(2)只允许在一端进行删除,两端进行插入。
栈与队列的本章小节
栈和队列同属于线性表,但它们与第2章的线性表数不同。一般线性的插入和删除操作,只要位置合理,都可以进行操作。栈的插入与删除操作只能在一端进行;队列的插入与删除操作分别在两端进行。因此常常称栈与队列是插入与删除受限的线性表。
栈的常用存储空间结构有顺序栈和链栈。顺序栈除了要考虑一片连续的存储空间用于存放栈中元素之外,还必须考虑指示栈顶的位置和总容量,所以常用的顺序栈和顺序表一样有两种不同的定义方法。由于进栈和出栈操作只能在栈顶进行,因此链表通常不是带头结点的单向链表。
队列的常用存储结构有循环队列和队列。循环队列一定要哦保证一片连续存储空间的循环使用,因此循环队列的类型考虑给定的数据成员能否正确表达队头、队尾的位置以及队空、队满的条件和队列元素个数的计算。本章给出了循环队列的两种描述方法,特别需要注意的是;在第一种循环队列的定义中,队头指针指向队头,队尾指针指向队尾的下一个元素;在第2种循环队列的定义中,只有队尾指针,队头指针并不在类型中,而是计算出来的。
链队列的重点在于队头指针和队尾指针的确定。本章给出了两种链队列的类型定义:一种是单链表实现,将队头指针和队尾指针组成一个结构体类型,让队头指针指向头结点,队尾指针指向队尾;另一种是循环链表实现,只用一个队尾指针指向尾结点,让尾结点的指针域指向头结点。
相关文章:
数据结构——第三章 栈与队列(5)
共用栈和双队列1.共用栈2.双端队列栈与队列的本章小节1.共用栈 在实际应用中,有时一个应用程序需要多个栈,但这些栈的数据元素类型相同。假设每个栈都采用顺序栈,由于每个栈的使用情况不尽相同,势必会造成存储空间的浪费。若让多…...
CSDN竞赛第33期题解
CSDN竞赛第33期题解 1、题目名称:奇偶排序 给定一个存放整数的数组,重新排列数组使得数组左边为奇数,右边为偶数。(奇数和偶数的顺序根据输入的数字顺序排 列) #include<bits/stdc.h> using namespace std; t…...
农产品销售系统的设计与实现
技术:Java、JSP等摘要:这篇文章主要描述的是农产品蔬菜在线销售系统的设计与实现。主要应用关于JSP网站开发技术,并联系到网站所处理的数据的结构特点和所学到的知识,应用的主要是Mysql数据库系统。系统实现了网站的基本功能&…...
C语言-基础了解-08-C判断
C判断 一、C判断 判断结构要求程序员指定一个或多个要评估或测试的条件,以及条件为真时要执行的语句(必需的)和条件为假时要执行的语句(可选的)。 C 语言把任何非零和非空的值假定为 true,把零或 null 假…...
用数组名作函数参数的详解,以及形参实参采用数组名,形参实参采用指针变量的几种情况解析
关于地址,指针,指针变量可以参考我的这篇文章: 地址,指针,指针变量是什么?他们的区别?符号(*)在不同位置的解释?_juechen333的博客-CSDN博客https://blog.csd…...
k8s中的PV和PVS
前言:容器磁盘上的文件的生命周期是短暂的,这就使得在容器中运行重要应用时会出现一些问题。首先,当容器崩溃时,kubelet 会重启它,但是容器中的文件将丢失——容器以干净的状态(镜像最初的状态)…...
【云原生】Gateway网关选型
网关一般分为流量网关和业务网关,流量网关负责接入所有的流量,并分发给不同的子系统,那在具体的业务接入之前,还有一层业务网关。流量网关提供全局性的、与后端业务应用无关的策略,例如 HTTPS证书卸载、Web防火墙、全局…...
QML Button详解
1.Button简介 Button表示用户可以按下或单击的按钮控件。按钮通常用于执行一个动作,或回答一个问题。典型的按钮有确定、应用、取消、关闭、是、否和帮助。 Button继承自AbstractButton,提供了以下几种信号。 void canceled() //当按…...
【编程实践】什么是好/坏代码?非程序员的示例
What is good/bad code? An illustrated example for non-programmers 什么是好/坏代码?非程序员的示例 目录 What is good/bad code? An illustrated example for non-programmers什么是好/坏代码?非程序员的示例 So what is ‘Bad Code’, as a layperson?那么,作为…...
一个简单的Sublime设置
问题 如果读者熟悉我,应该会发现我经常使用 VSCode 作为主力编辑器,但随着我安装的 VSCode 的插件逐渐增加,我发现对于部分较小的任务使用 VSCode 过于笨重,比如简单的 Markdown 文件编辑工作。 在经过一系列寻找后,…...
c语言经典例题-选择结构程序设计进阶
(创作不易,感谢有你,你的支持,就是我前行的最大动力,如果看完对你有帮助,请留下您的足迹) 目录 快递费用计算: 题目: 代码思路: 代码表示: 计算一元二…...
NOI 2023春季测试 游记
怎么说,没遇到大波折即幸运。 Day 0 睡到下午三点,然后列了一堆复习计划,大概是左偏树等一些早就忘没的科技。 但是沉迷打块,最后基本什么计划也没完成。 白天睡多了,晚上睡不着,大概半梦半醒过了一整夜…...
【VC 7/8】vCenter Server 基于文件的备份和还原Ⅱ——使用 FTP 协议备份 VC(VAMI 英文)
目录2. 备份 vCenter Server2.1 使用 FTP 协议备份 VC(1)登录 vCenter Server 管理界面(2)进入Backup页面(3)配置 Backup Schedule(4)开始备份(5)备份成功&am…...
Python基础—文件操作(二)
Python基础—文件操作(二) CSV格式文件 逗号分隔值,以纯文本形式存储表格数据 由任意数目的记录组成,记录间以换行符分隔 每条记录由字段组成,字段间用逗号或制表符分隔 每条记录都有同样的字段序列 如有列名,位于文件第一行 每条…...
学校的班级个数【并查集基础应用,Java实现】
题目描述 现有一个学校,学校中有若干个班级,每个班级中有若干个学生,每个学生只会存在于一个班级中。如果学生A和学生B处于一个班级,学生B和学生C处于一个班级,那么我们称学生A和学生C也处于一个班级。 现已知学校中共…...
WSL2使用Nvidia-Docker实现CUDA版本自由切换
众所周知,深度学习的环境往往非常麻烦,经常不同的项目所依赖的 torch、tensorflow 包对 CUDA 的版本也有不同的要求,Linux 下进行 CUDA 的管理比较麻烦,是一个比较头疼的问题。 随着 WSL2 对物理机显卡的支持,Nvidia-…...
pygame9 扫雷游戏2
一、响应鼠标左键事件 pygame.MOUSEBUTTONDOWN 表示鼠标事件发生, pygame.mouse.get_pressed()[0] 确认是鼠标左键被按下 pygame.mouse.get_pos() 获取到鼠标按下时的坐标值。 因此,我们可以在事件逻辑中例用此三个函数判断鼠标事件及对应的坐标&#x…...
逻辑电路代数运算(上)
逻辑代数L是一个封闭的代数系统,由一个逻辑变量集K,常量0和1,以及与或非三种基本运算构成。 参与逻辑运算的变量叫逻辑变量,用字母A,B……表示。每个变量的取值非0 即1。 0、1不表示数的大小,而是代表两种不…...
Rabbit快速入门
入门案例 需求:使用简单模式完成消息传递 步骤: 创建工程(生成者、消费者) 分别添加依赖 编写生产者发送消息 编写消费者接收消息 3.1.2. 添加依赖 往heima-rabbitmq的pom.xml文件中添加如下依赖: <dependenc…...
【react+ts- forwardRef】
reactts- forwardRef1. 学习资料2. 普通input透传2.1 TS版本2.2 JS版本3. TS-Antd-Form组价透传引用传递(Ref forwading)是一种通过组件向子组件自动传递 引用ref 的技术。对于应用者的大多数组件来说没什么作用。但是对于有些重复使用的组件,…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
解读《网络安全法》最新修订,把握网络安全新趋势
《网络安全法》自2017年施行以来,在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂,网络攻击、数据泄露等事件频发,现行法律已难以完全适应新的风险挑战。 2025年3月28日,国家网信办会同相关部门起草了《网络安全…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
一些实用的chrome扩展0x01
简介 浏览器扩展程序有助于自动化任务、查找隐藏的漏洞、隐藏自身痕迹。以下列出了一些必备扩展程序,无论是测试应用程序、搜寻漏洞还是收集情报,它们都能提升工作流程。 FoxyProxy 代理管理工具,此扩展简化了使用代理(如 Burp…...
ThreadLocal 源码
ThreadLocal 源码 此类提供线程局部变量。这些变量不同于它们的普通对应物,因为每个访问一个线程局部变量的线程(通过其 get 或 set 方法)都有自己独立初始化的变量副本。ThreadLocal 实例通常是类中的私有静态字段,这些类希望将…...
LangChain【6】之输出解析器:结构化LLM响应的关键工具
文章目录 一 LangChain输出解析器概述1.1 什么是输出解析器?1.2 主要功能与工作原理1.3 常用解析器类型 二 主要输出解析器类型2.1 Pydantic/Json输出解析器2.2 结构化输出解析器2.3 列表解析器2.4 日期解析器2.5 Json输出解析器2.6 xml输出解析器 三 高级使用技巧3…...
如何做好一份技术文档?从规划到实践的完整指南
如何做好一份技术文档?从规划到实践的完整指南 🌟 嗨,我是IRpickstars! 🌌 总有一行代码,能点亮万千星辰。 🔍 在技术的宇宙中,我愿做永不停歇的探索者。 ✨ 用代码丈量世界&…...
RushDB开源程序 是现代应用程序和 AI 的即时数据库。建立在 Neo4j 之上
一、软件介绍 文末提供程序和源码下载 RushDB 改变了您处理图形数据的方式 — 不需要 Schema,不需要复杂的查询,只需推送数据即可。 二、Key Features ✨ 主要特点 Instant Setup: Be productive in seconds, not days 即时设置 :在几秒钟…...
