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

数据结构——第三章 栈与队列(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+1
top2为真。
进栈操作:必须区分是对哪一个栈进操作。

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、题目名称&#xff1a;奇偶排序 给定一个存放整数的数组&#xff0c;重新排列数组使得数组左边为奇数&#xff0c;右边为偶数。&#xff08;奇数和偶数的顺序根据输入的数字顺序排 列&#xff09; #include<bits/stdc.h> using namespace std; t…...

农产品销售系统的设计与实现

技术&#xff1a;Java、JSP等摘要&#xff1a;这篇文章主要描述的是农产品蔬菜在线销售系统的设计与实现。主要应用关于JSP网站开发技术&#xff0c;并联系到网站所处理的数据的结构特点和所学到的知识&#xff0c;应用的主要是Mysql数据库系统。系统实现了网站的基本功能&…...

C语言-基础了解-08-C判断

C判断 一、C判断 判断结构要求程序员指定一个或多个要评估或测试的条件&#xff0c;以及条件为真时要执行的语句&#xff08;必需的&#xff09;和条件为假时要执行的语句&#xff08;可选的&#xff09;。 C 语言把任何非零和非空的值假定为 true&#xff0c;把零或 null 假…...

用数组名作函数参数的详解,以及形参实参采用数组名,形参实参采用指针变量的几种情况解析

关于地址&#xff0c;指针&#xff0c;指针变量可以参考我的这篇文章&#xff1a; 地址&#xff0c;指针&#xff0c;指针变量是什么&#xff1f;他们的区别&#xff1f;符号&#xff08;*&#xff09;在不同位置的解释&#xff1f;_juechen333的博客-CSDN博客https://blog.csd…...

k8s中的PV和PVS

前言&#xff1a;容器磁盘上的文件的生命周期是短暂的&#xff0c;这就使得在容器中运行重要应用时会出现一些问题。首先&#xff0c;当容器崩溃时&#xff0c;kubelet 会重启它&#xff0c;但是容器中的文件将丢失——容器以干净的状态&#xff08;镜像最初的状态&#xff09;…...

【云原生】Gateway网关选型

网关一般分为流量网关和业务网关&#xff0c;流量网关负责接入所有的流量&#xff0c;并分发给不同的子系统&#xff0c;那在具体的业务接入之前&#xff0c;还有一层业务网关。流量网关提供全局性的、与后端业务应用无关的策略&#xff0c;例如 HTTPS证书卸载、Web防火墙、全局…...

QML Button详解

1.Button简介 Button表示用户可以按下或单击的按钮控件。按钮通常用于执行一个动作&#xff0c;或回答一个问题。典型的按钮有确定、应用、取消、关闭、是、否和帮助。 Button继承自AbstractButton&#xff0c;提供了以下几种信号。 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设置

问题 如果读者熟悉我&#xff0c;应该会发现我经常使用 VSCode 作为主力编辑器&#xff0c;但随着我安装的 VSCode 的插件逐渐增加&#xff0c;我发现对于部分较小的任务使用 VSCode 过于笨重&#xff0c;比如简单的 Markdown 文件编辑工作。 在经过一系列寻找后&#xff0c;…...

c语言经典例题-选择结构程序设计进阶

(创作不易&#xff0c;感谢有你&#xff0c;你的支持&#xff0c;就是我前行的最大动力&#xff0c;如果看完对你有帮助&#xff0c;请留下您的足迹&#xff09; 目录 快递费用计算&#xff1a; 题目&#xff1a; 代码思路&#xff1a; 代码表示&#xff1a; 计算一元二…...

NOI 2023春季测试 游记

怎么说&#xff0c;没遇到大波折即幸运。 Day 0 睡到下午三点&#xff0c;然后列了一堆复习计划&#xff0c;大概是左偏树等一些早就忘没的科技。 但是沉迷打块&#xff0c;最后基本什么计划也没完成。 白天睡多了&#xff0c;晚上睡不着&#xff0c;大概半梦半醒过了一整夜…...

【VC 7/8】vCenter Server 基于文件的备份和还原Ⅱ——使用 FTP 协议备份 VC(VAMI 英文)

目录2. 备份 vCenter Server2.1 使用 FTP 协议备份 VC&#xff08;1&#xff09;登录 vCenter Server 管理界面&#xff08;2&#xff09;进入Backup页面&#xff08;3&#xff09;配置 Backup Schedule&#xff08;4&#xff09;开始备份&#xff08;5&#xff09;备份成功&am…...

Python基础—文件操作(二)

Python基础—文件操作(二) CSV格式文件 逗号分隔值&#xff0c;以纯文本形式存储表格数据 由任意数目的记录组成&#xff0c;记录间以换行符分隔 每条记录由字段组成&#xff0c;字段间用逗号或制表符分隔 每条记录都有同样的字段序列 如有列名&#xff0c;位于文件第一行 每条…...

学校的班级个数【并查集基础应用,Java实现】

题目描述 现有一个学校&#xff0c;学校中有若干个班级&#xff0c;每个班级中有若干个学生&#xff0c;每个学生只会存在于一个班级中。如果学生A和学生B处于一个班级&#xff0c;学生B和学生C处于一个班级&#xff0c;那么我们称学生A和学生C也处于一个班级。 现已知学校中共…...

WSL2使用Nvidia-Docker实现CUDA版本自由切换

众所周知&#xff0c;深度学习的环境往往非常麻烦&#xff0c;经常不同的项目所依赖的 torch、tensorflow 包对 CUDA 的版本也有不同的要求&#xff0c;Linux 下进行 CUDA 的管理比较麻烦&#xff0c;是一个比较头疼的问题。 随着 WSL2 对物理机显卡的支持&#xff0c;Nvidia-…...

pygame9 扫雷游戏2

一、响应鼠标左键事件 pygame.MOUSEBUTTONDOWN 表示鼠标事件发生&#xff0c; pygame.mouse.get_pressed()[0] 确认是鼠标左键被按下 pygame.mouse.get_pos() 获取到鼠标按下时的坐标值。 因此&#xff0c;我们可以在事件逻辑中例用此三个函数判断鼠标事件及对应的坐标&#x…...

逻辑电路代数运算(上)

逻辑代数L是一个封闭的代数系统&#xff0c;由一个逻辑变量集K&#xff0c;常量0和1&#xff0c;以及与或非三种基本运算构成。 参与逻辑运算的变量叫逻辑变量&#xff0c;用字母A&#xff0c;B……表示。每个变量的取值非0 即1。 0、1不表示数的大小&#xff0c;而是代表两种不…...

Rabbit快速入门

入门案例 需求&#xff1a;使用简单模式完成消息传递 步骤&#xff1a; 创建工程&#xff08;生成者、消费者&#xff09; 分别添加依赖 编写生产者发送消息 编写消费者接收消息 3.1.2. 添加依赖 往heima-rabbitmq的pom.xml文件中添加如下依赖&#xff1a; <dependenc…...

【react+ts- forwardRef】

reactts- forwardRef1. 学习资料2. 普通input透传2.1 TS版本2.2 JS版本3. TS-Antd-Form组价透传引用传递&#xff08;Ref forwading&#xff09;是一种通过组件向子组件自动传递 引用ref 的技术。对于应用者的大多数组件来说没什么作用。但是对于有些重复使用的组件&#xff0c…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...