共享栈和双端队列_作业写不完的卑微小cookie的博客-程序员宅基地_共享栈和双端队列

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

共享栈和双端队列

一、共享栈

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

二、双端队列

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

例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

智能推荐

Tagged Pointer遐想_xingshao1990的博客-程序员宅基地

Tagged Pointer遐想一、NSString__NSCFConstantStringNSTaggedPointerString__NSCFStringcopymutableCopy中文或者特殊字符(非ASCII字符)autoreleaseNSMutableStringstring二、NSNumber三、 线程安全Todo:摘要Tagged Pointer(64bit系统对 NSStrin...

js进阶Web APIs05---offset、client、scroll属性_兰兰的小窝的博客-程序员宅基地

offsetPS:获得元素距离带有定位父元素的位置元素的宽和高含:padding + border + width 返回的数值不带单位注意区分:(1)offsetParent与parentNode①offsetParent:返回带有定位的父亲 否则返回的是body②parentNode:返回父亲 是最近一级的父亲 亲爸爸 不管父亲有没有定位(2)offset与styleA. offsetoffset 可以得到任意样式表中的样式值offset 系列获得的数值是没有单位的offs

基于金融业顾客生命周期的商业分析_JMP数据分析的博客-程序员宅基地

随着近些年商业银行之间的竞争逐渐加大,客户,作为银行利润的最终来源就愈发重要。银行若要提高自身盈利能力,对客户价值的挖掘与深入洞察必不可少。客户分级就是常用的方法之一。客户分级,即:基于客户需求的异质性和银行资源的有限性、对客户群体根据不同维度进行细分的过程。其主要有两类模式:依据商业价值与账户活跃周期。随着移动互联网技术和金融科技的发展,银行的功能也发生了转变,原有的客户分级方法可能存在一定的局限性。基于客户全生命周期的精准客户分级与科学分析势在必行。那么,当下的银行业:客户分级应该如何来改进

ubuntu 13.04 mysql_Ubuntu13.04 下MySQL5.6安装过程_瓦克五的博客-程序员宅基地

1.mysql下载:按照自己系统选择 http://www.mysql.com/downloads/installer/2.mysql依赖包安装 (libaio1.so) 若已安装可以省略:sudo apt-get install libaio1sudo apt-get install cmake libncurses5-dev bison g++ (可不选,有问题时再执行)3.组及用户创建:...

python pip命令报错 invlid systax_pip执行命令过程报错-SyntaxError: invalid syntax_weixin_39841825的博客-程序员宅基地

pip执行命令过程中出现错误,异常代码如下:Traceback (most recent call last):File "/usr/bin/pip", line 7, in from pip._internal.main import mainFile "/usr/lib/python2.6/site-packages/pip/_internal/main.py", line 13, in fr...

中国情侣必去的国内十大浪漫圣地_ximenchuixuezijin的博客-程序员宅基地

1、丽江——追寻一米阳光的传说         清冷的玉龙雪山顶上,终年云雾缭绕,即使是在最晴朗的天气,阳光也很难穿透云层,传说每年秋分是日月交合同辉同映的日子,只有在特别偶然的时刻,才能看到有一米长的阳光照在山顶,而被这道阳光照耀到的人就能拥有一世不变的爱情。也许,这一瞬间

随便推点

关于动态加载dll问题_weixin_34114823的博客-程序员宅基地

关于动态加载dll问题 Delphi / Windows SDK/APIhttp://www.delphi2007.net/DelphiAPI/html/delphi_20061106114545295.html现在有一个dll文件,需动态加载,看了很多资料,但是还是不太清楚     1.动态加载时,是不是须在oncreate事件中LoadLibrary进行判断     2.dll在何时...

进程管理_中国味鲁花香的博客-程序员宅基地

进程管理 进程管理知识要点认识进程进程和程序的关系进程相关操作查看系统性能进程是什么程序 保存在硬盘、光盘等介质中的可执行代码和数据 是静态保存的代码进程 在CPU及内存中运行的动态执行的程序代码 进程是程序运行的实例 同一个程序可能对应多个进程子进程和父进程 INIT进程是系统中第一个进程,PID永远是1[ro...

java 矩阵乘向量_矩阵乘法运算-JAVA实现_核桃英语的博客-程序员宅基地

用JAVA写了个矩阵乘法运算.没什么好解释的.直接贴代码吧.public class Matrix {int row;int col;private int[][] array;private Matrix(){//构造函数私有化,使用setArray方法进行初始化}public int[][] getArray() {return array;}public void setArray(int[...

docker版本包 乌班图_Ubuntu安装Docker社区版_馥菲的博客-程序员宅基地

Docker社区版叫Docker -ce如果安装有老的docker先删除老的版本sudo apt-getremove docker docker-engine docker.io先更新包信息sudo apt-getupdate安装libltdl7sudo apt-getinstall libltdl7下载最新版本的安装包(其他版本可以在docker下载地址找到)wget https://downl...

C++ 拷贝构造函数中Private权限问题_startAt24的博客-程序员宅基地

自己以前的理解中Private是限制了类中数据的访问权限,在外部无法访问。今天阅读拷贝构造函数的时候看到了这样的例子:class MyString {private: char* m_pData; size_t m_iLen; void _init_data(const char* s) { m_pData = new char[m_iLen + 1]; memcpy(m_pDat...

EBS的性能调优_csdn13681123263的博客-程序员宅基地

metalink Tuning performance on eBusiness suite (Doc ID 744143.1) 这篇文档描述了如何调查电子商务套件的整体性能下降。特别是,我们强调...

推荐文章

热门文章

相关标签