数据结构——第三章 栈与队列(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 的技术。对于应用者的大多数组件来说没什么作用。但是对于有些重复使用的组件,…...
Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
基于SpringBoot在线拍卖系统的设计和实现
摘 要 随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统,主要的模块包括管理员;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...
【LeetCode】算法详解#6 ---除自身以外数组的乘积
1.题目介绍 给定一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O…...
【深度学习新浪潮】什么是credit assignment problem?
Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...
《信号与系统》第 6 章 信号与系统的时域和频域特性
目录 6.0 引言 6.1 傅里叶变换的模和相位表示 6.2 线性时不变系统频率响应的模和相位表示 6.2.1 线性与非线性相位 6.2.2 群时延 6.2.3 对数模和相位图 6.3 理想频率选择性滤波器的时域特性 6.4 非理想滤波器的时域和频域特性讨论 6.5 一阶与二阶连续时间系统 6.5.1 …...
Qt的学习(一)
1.什么是Qt Qt特指用来进行桌面应用开发(电脑上写的程序)涉及到的一套技术Qt无法开发网页前端,也不能开发移动应用。 客户端开发的重要任务:编写和用户交互的界面。一般来说和用户交互的界面,有两种典型风格&…...
