共享栈和双端队列_双端队列和共享栈-程序员宅基地

技术标签: 链表    队列  数据结构  # 栈和队列  

共享栈和双端队列

一、共享栈

相比于普通的顺序栈,共享栈主要是为了提高内存的利用率和减少溢出的可能性而设计的。
为了增加内存空间的利用率和减少溢出的可能性,当两个栈共享一篇连续的内存空间时,应将两栈的栈底分别设在这片内存空间的两端,这样当两个栈的栈顶在栈空间的某一位置相遇时,才产生上溢。

二、双端队列

双端队列是一种插入和删除操作在两端均可进行的线性表,可以把双端队列看成栈底连在一起的两个栈。他们与两个栈共享存储空间的共享栈的不同指出是,两个栈的栈顶指针式向两端延伸的。由于双端队列允许在两端插入和删除元素,因此需要设立两个指针,分别指向双端队列中两端的元素。
允许在一端进行插入和删除(进队和出队),另一端只允许删除的双端队列称为输入受限的双端队列。
允许在一端进行插入和删除,另一端只允许插入的双端队列称为输出受限的双端队列

例1.设有一 个双端队列,元素进入该队列的顺序是1, 2, 3, 4.试分别求出满足下列条件的
输出序列。
(1)能由输入受限的双端队列得到,但不能由输出受限的双端队列得到的输出序列。
(2)能由输出受限的双端队列得到,但不能由输入受限的双端队列得到的输出序列。
(3)既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列。
在这里插入图片描述
解答
(1)先看输入受限的双端队列,假设end1端输入1,2,3,4,那么end2端的输出相当于队列的输出;1,2,3,4;而end1端的输出相当于栈的输出,n=4时,可以通过Catalan()仅通过end1端有14中输出序列,仅仅通过end1端不能得到的输出序列有4!-14=10种,它们是:

1,4,2,3 2,4,1,3
3,4,1,2 3,1,4,2
3,1,2,4 4,3,1,2
4,2,1,3 4,1,2,3
4,1,3,2 4,2,1,3

通过end1和end2端混合输出,可以输出着10种中的8种。其中,SL,XL分别代表end1端的进队和出队,XR代表end2端的出队
通过end1和end2端的混合输出序列图如下
在这里插入图片描述
可以得出有两种是不可能通过受限的双端队列输出的,即4,2,1,3和4,2,3,1
(2)假设end1端和end2端输入,还可以输出其中8种,假设SL代表end1端的输入,SR,XR代表end2端的输入和输出,则可能输出序列以及进队和出队序列如下图所示。
在这里插入图片描述
可得通过输出受限的双端队列不能输出的两种序列是:4,1,3,2和4,2,3,1
(3)取如上(1)和(2)的交集可得既不能由输入受限的双端队列得到 ,也不能由输出受限的双端队列得到的输出序列是4,2,3,1

综上得:
能由输入受限的双端队列得到,但不能由输出受限的双端队列得到的输出序列是4,1,3,2;能由输出受限的双端队列得到,但不能由输入受限的双端队列得到的输出序列是4,2,1,3;
既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列是4,2,3,
1。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_44279771/article/details/107759579

智能推荐

局域网内Ubuntu16和Ubuntu18离线安装ntp并部署ntp服务器及同步客户端时间_ubuntu ntp 离线安装-程序员宅基地

文章浏览阅读3.5k次,点赞3次,收藏11次。局域网内Ubuntu16和Ubuntu18离线安装ntp 并部署 ntp 服务器及同步客户端时间_ubuntu ntp 离线安装

EntityFramwork 相关概念_entity framwork-程序员宅基地

文章浏览阅读291次。ORM: Object Relational Mapping 关系对象映射Entity Framework:微软官方提供的ORM工具,将数据存储从域对象自动映射到关系型数据库的工具EF5由两部分组成,EF api和.net framework 4.0/4.5,而EF6是独立的EntityFramework.dll,不依赖.net Framework。使用NuGet即可安装EF。 E..._entity framwork

【运维有小邓】AD域文件权限管理_ad添加本地管理员权限-程序员宅基地

文章浏览阅读1k次。DManager Plus还内置了有关NTFS权限的报表。服务器中的共享、文件夹的权限、可访问文件夹的账户以及不可继承文件夹等方面的报表。这些报表让您可立即全面地了解访问控制信息,所以对管理员很有用。..._ad添加本地管理员权限

CTF基础知识及web_ctf web-程序员宅基地

文章浏览阅读7.3k次,点赞13次,收藏175次。提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档文章目录CTF基础知识一、CTF简介二、CTF赛事介绍三、CTF竞赛模式1.解题模式(Jeopardy)2.攻防模式(Attack-Defense)3.混合模式(Mix)四、CTF竞赛内容国内外著名赛事1、国际知名CTF赛事2、国内知名CTF赛事五、如何学习CTF1、分析赛题2、常规操作3、入门知识推荐书籍CTF基础知识一、CTF简介CTF(Capture The Flag)夺旗比赛,在网络安全领域中指的是网络安全技术人员之间进行._ctf web

Udacity Self-Driving Car Simulator Introduction_udacity self driving car sim ros-程序员宅基地

文章浏览阅读725次。Introduction to Udacity Self-Driving Car SimulatorUdacity recently made its self-driving car simulator source code available on their GitHub which was originally built to teach their Self-Drivin..._udacity self driving car sim ros

python res函数_python函数-程序员宅基地

文章浏览阅读6k次。函数定义: 函数是指将一组语句的集合通过一个名字(函数名)封装起来,要想执行这个函数,只需调用其函数名即可函数特性:def my_sum(x,y): #定义函数名res = x+yreturn res #返回函数执行结果c = my_sum(4,5) #结果赋值给c变量print(c)减少重复代码使程序变的可扩展使程序变得易维护函数参数形参即变量名就是函数定义阶段的参数,实参即变量值就是函数调用阶..._python res

随便推点

Python解决AttributeError: module ‘matplotlib‘ has no attribute ‘get_data_path‘问题_module 'matplotlib' has no attribute 'get_data_pat-程序员宅基地

文章浏览阅读1.3w次,点赞7次,收藏3次。当import matplotlib.pyplot as plt时,报错显示AttributeError: module 'matplotlib' has no attribute 'get_data_path'检查了一下目前matplotlib的版本是3.4.3,出现包导入错误可能是系统或package升级的原因,多尝试一下降低package的版本就好。试了一下3.3.1 和3.3.4版本,最后3.3.4版本可以完美解决上述报错~..._module 'matplotlib' has no attribute 'get_data_path

Supermap/Cesium 开发心得----动态散点图(波纹点/涟漪点)-程序员宅基地

文章浏览阅读1.6k次。在二维开发中,openlayers4 入门开发系列结合 echarts4 实现散点图,下图是GIS之家的效果图,那么在三维中,则可借助Entity来变相构造下图的效果。思路:构造实体ellipse,造一个用作实心中心区域的表征位置,再造两个圆,控制他们的半径动态变化,然后轮回播放,这其中涉及的是Cesium.CallbackProperty Cesium.Image..._cesium加载涟漪图

onlyoffice 回调传参数_onlyOffice 开发相关 总结-程序员宅基地

文章浏览阅读977次。onlyOffice 服务端 客户端 相关开发整理功能:所有客户端都可用云端部署服务查看 预览 doc ppt excel编辑权限控制开发技术准备用户服务器端 提供保存接口用户浏览器端 提供生成文件 key 标示(刷新后重新生成)安装server 端docker pull onlyoffice/documentserverdoc:ports:- 8686:80/tcptty: trueimage..._onlyoffice callbackurl

java 两个时间相减_java两个时间相减得到分钟-程序员宅基地

文章浏览阅读5.6k次,点赞3次,收藏4次。废话不多说: DateFormatdf=newSimpleDateFormat("yyyy-MM-ddHH:mm:ss"); try { Dated1=df.parse("2018-03-2613:31:40"); Dated2=df.parse("2018-01-0211:30:24");..._java两个时间相减得到分钟

PHP性能优化工具–xhprof安装-程序员宅基地

文章浏览阅读130次。PHP性能优化工具–xhprof安装,这里我先贴出大致的步骤:1.获取xhprof2.编译前预处理3.编译安装4.配置php.ini5.查看运行结果那么下面我们开始安装xhprof工具吧:1.获取xhprof可以输入网址直接下载,或者wget1234#wget http://p..._php 安装xprof

RK3399-android7.1-mipi转lvds_struct video_timing video_1920x1080_60hz-程序员宅基地

文章浏览阅读847次。RK3399-android7.1-mipi转lvds_struct video_timing video_1920x1080_60hz