已知输入序列为abcd经过输出受限的双向队列后能得到的输出序_

cpppppp

看了下大家的答案，没有看到有人从原理上证明答案。所以我来试着从原理上证明。

先说结论：

对于...a...b...c...d...的输入序列（...代表其他任意元素），经过输出受限的双向队列后，

有两种类型的序列是不存在的：

...d...b...c...a...

...d...a...c...b...

也就是不能出现c夹在a和b中间的情况。

证明过程：

因为a、b、c先于 d入队且d先于a、b、c出队，所以当d出队时a、b、c还在队中。

对于a、b、c而言： a，b先入队，此时a和b的排列顺序为ab或ba，所以当c入队时，只能排在在ab或ba的两端。

即不能出现c夹在a和b中间的情况，

也就是不能出现...d...b...c...a...和...d...a...c...b...这两种情况。

证明完成。

如果证明过程有错误，欢迎指出~ （=。= ）

发表于 2019-01-22 15:04:45 回复(4)

gbx1227

选择ＢＤ

输出受限意为可以在两端输入只能在一端输出。假设右端为输出端：

Ａ　要满足输出ｄａ，则先输入ａｂｃ再从右端输入ｄ，排列为ｃｂａｄ，右端输出为ｄａｂｃ，所以Ａ错；

Ｂ　先输入ａｂｃ使之排列为ｂａｃ，再从右端输出ｃａ，从右端输入ｄ，再依次输出ｄ和ｂ，所以序列为ｃａｄｂ；

后面类推。

发表于 2015-07-16 15:36:43 回复(11)

Scheaven

注意是出队受限的队列（单方向出队），入队可以两端入队，并且只限制进队的顺序，不限制是否全部进入才出队，

B:答案 cadb 过程： a进队列——b从入队口进队——c从出队口出队——a出队——d从出队口入队——d出队——b出队;

D: 答案bdac 过程： a进队列——b从出队口进队——b出队——c从入队口入队——d从出队口入队——d出队——a出队——c出队;

发表于 2016-08-17 17:43:39 回复(0)

InGodWeTrust

答案：B,D

输出受限的双端队列,即删除限制在一端进行,而插入仍允许在两端进行.先假设可在左右两端进队列，而只能在右端出队列，如图所示：

编辑于 2017-03-04 16:43:37 回复(2)

SIDNEY

题目中没说一次性输入和输出，所以可以在输入过程（两端都有可能）中也进行输出操作（限定一端)，交叉处理，得BD

发表于 2015-09-02 12:56:38 回复(4)

沂飔

输出受限意为可以在两端输入只能在一端输出。假设右端为输出端：

左[] [] [] [] 右

对于B答案，A从左边入，此时队列为左[A] [] [] [] 右，

接下来B从左边入，此时队列为左[B] [A] [] [] 右，

接下来C从右边入，此时队列为左 [B] [A] [C] [] 右，

然后C从右边出，A从右边出，此时队列为左 [B] [] [] [] 右，得到CA

接下来D从右边入，此时队列为左 [B] [D] [] [] 右，得到CA

然后D从右边出，此时队列为左 [B] [] [] [] 右，得到CAD

接下来B从右边出此时队列为左 [] [] [] [] 右，得到CADB

发表于 2017-07-20 09:50:47 回复(0)

侯卿

大号的右边比他小的序列里不能出现跳跃出队，例如ebcad中，e最大，右边的cad中a相邻的b不在它旁边，就是跳跃。即不可能出现。

发表于 2017-12-27 21:32:47 回复(0)

牛客4938kunn

本题需要注意两点：

未强调元素需要全部入队才能出队
自己拟定一个被限制的输出的端口（以下假设限制右侧输出），两端都可输入。

A：先输出的是d,则abc应该全部已经输入，则输出结果应该为dabc
B：先输出为c，则ab已经入队列，bac，弹出ca，再压栈d，则最后输出为cadb
C：同A有些相似，若第一个弹出为d，则全部已经入队列，第二个元素如果为b，则正确输出应该为dbac
D：b先弹出，则a已经入队列，先弹出b，在左侧压入c，右侧压入d，则输出为bdac

发表于 2021-07-24 20:20:48 回复(0)

bealikeflower

B选项假设a先进了，再b左进，c右进，再ca出，再d右进，再db出; D选项假设a进了，b右进，c左进，再b出，再d右进，再dac出

发表于 2017-06-10 19:00:52 回复(0)

huixieqingchun

输出受限的双向队列，表示队列可以两端进行输入，一端进行输出

发表于 2016-04-28 18:57:01 回复(0)

牛客200222370号

首先要明白双向队列是允许两边输入，一边输出

发表于 2022-04-18 17:46:48 回复(0)

lalalaxiaomoxian

不限制全部进队才出队

发表于 2020-11-15 14:03:33 回复(0)

理想L9

BD

输出受限的双端队列是指删除限制在一端进行，而插入允许在两端进行的队列。

输入序列为abcd，输出序列为cadb，其输入输出顺序为：先在输出端输入a，然后在非输出端输入b，这时队列中的序列为ba，再在输出端输入c，这时队列中的序列为bac；输出c，再输出a；再在输出端输入d，这时队列中的序列为bd；输出d，再输出b。最后得到输出序列为cadb。

输入序列为abcd，输出序列为bdac，其输入输出顺序为：现在输出端输入a，然后在输出端输入b，这是队列中的序列为ab，输出端输出b，再在非输出端输入c，这时队列中的序列为ca；再在输出端输入d，输出d，再输出a，输出c。最后输出序列为bdac。

发表于 2020-07-18 19:05:28 回复(0)

_澈

对于A、C，输出第一个是对d，说明序列已经全部入栈，那么a, b出队一定是相邻的。当第一个不是最后一个元素时，才可能使用剩下的元素从出队口入队再出队将a, b 间隔。

发表于 2017-07-30 10:01:20 回复(0)

DJL箫氏

想知道D是怎么可以的

发表于 2016-08-16 10:49:17 回复(1)

Cheney_cy

双向队列：头尾两端都可以进行插入和删除

题目的意思是头尾两端都可以进行插入但只有一端只能输出（不知道只能是哪一端输出，其实没有差别的），

我们用 d c b a b c d 这种格式进行理解，我用F表示进入的顺序,O表示删除的顺序（假如a是第一个进入的，则表示aF(1)；c是第二个进入的，则表示cF(2)；c是第一个出去的则表示cO(1)。）先解释B 选项为什么对？

先进的是a

B选项： (假设是右端能输出) bF(2)，aF(1)，cF(3)，cO(1)，aO(2)， dF(4)， dO(3)，bO(4) 如果是左端能输出，也是可以的无非是把左右插入删除顺序换换。

其余的选项也是以此类推，便知是否对错。

发表于 2016-03-17 22:42:27 回复(2)

牛客254375851号

不必等全部入队再出队，可以部分入队就出队，这样以d开头的都不对，因为d先出队就意味着已经入队完成了。

发表于 2024-09-13 20:19:40 回复(0)

niki413

这么模糊的题意我真的会谢，一点都不严谨，一次性输出都不考虑的吗

发表于 2023-10-20 13:32:51 回复(0)

暖光2333

就跟入栈出栈差不多，注意先后顺序就行，并不一定要abcd全入队再出队，可以边入队边出队

发表于 2023-03-29 17:30:36 回复(0)

加油打工

求助，什么时候可以一边入一边出，什么时候是一次性出呀？谢谢

发表于 2022-11-02 16:00:36 回复(0)

已知输入序列为abcd经过输出受限的双向队列后能得到的输出序

问题信息

热门推荐

相关试题