blocks|key|2976835|text|好吧，这真的很难，我能想出的唯一解决方案，记得我对Kobayashi+Maru测试的Kirks解决方案(不知何故被欺骗了)：想法是，我们使用堆栈(并用它来模拟一个列表)。我调用操作en/dequeue和push和pop，然后我们得到：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2976836|queue.new()+:+Stack1+=+Stack.new(<Stack>);++
++++++++++++++Stack2+=+Stack1;++

enqueue(element):+Stack3+=+Stack.new(<TypeOf(element)>);+
++++++++++++++++++Stack3.push(element);+
++++++++++++++++++Stack2.push(Stack3);
++++++++++++++++++Stack3+=+Stack.new(<Stack>);
++++++++++++++++++Stack2.push(Stack3);
++++++++++++++++++Stack2+=+Stack3;+++++++++++++++++++++++

dequeue():+Stack3+=+Stack1.pop();+
+++++++++++Stack1+=+Stack1.pop();
+++++++++++dequeue()+=+Stack1.pop()
+++++++++++Stack1+=+Stack3;

isEmtpy():+Stack1.isEmpty();|code-block|syntax|javascript|2976837|(StackX+=+StackY不是内容的副本，只是引用的副本。这只是简单地描述它。您也可以使用3个堆栈的数组，并通过index访问它们，在那里您只需更改index变量的值)。在堆栈操作术语中，一切都是O(1)。|2976838|是的，我知道这是有争议的，因为我们有3个以上的隐式堆栈，但它可能会给你们其他人带来好的想法。|2976839|编辑:解释示例：|2976840|+%7C+%7C+%7C+%7C3%7C+%7C+%7C+%7C
+%7C+%7C+%7C+%7C_%7C+%7C+%7C+%7C
+%7C+%7C+%7C_____%7C+%7C+%7C
+%7C+%7C+++++++++%7C+%7C
+%7C+%7C+++%7C2%7C+++%7C+%7C
+%7C+%7C+++%7C_%7C+++%7C+%7C
+%7C+%7C_________%7C+%7C
+%7C+++++++++++++%7C
+%7C+++++%7C1%7C+++++%7C
+%7C+++++%7C_%7C+++++%7C
+%7C_____________%7C|2976841|我试着在这里用一个小的ASCII艺术来展示Stack1。|2976842|每个元素都包装在一个元素堆栈中(所以我们只有类型安全的堆栈)。|2976843|你看，为了删除，我们首先弹出第一个元素(包含这里的元素1和2的堆栈)。然后弹出下一个元素，并在那里展开1。然后，我们说第一个弹出的堆栈现在是我们的新Stack1。说得更实用一点--这些列表是由2个元素组成的堆栈实现的，其中顶部的元素是cdr，第一个/下面的顶部元素是car。另外两个是帮助堆栈。|2976844|Esp棘手的是插入，因为你必须以某种方式深入到嵌套堆栈中来添加另一个元素。这就是Stack2出现的原因。Stack2总是最内层的堆栈。and就是将一个元素放入队列，然后再放入一个新的Stack2+(这就是为什么我们不允许在出队操作中接触Stack2的原因)。|2976845|entityMap^0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Y|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|Z|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|10|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|11|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|12|8|@]|9|@]|A|$]]|$1|M|3|N|5|D|7|13|8|@]|9|@]|A|$E|F]]|$1|O|3|P|5|6|7|14|8|@]|9|@]|A|$]]|$1|Q|3|R|5|6|7|15|8|@]|9|@]|A|$]]|$1|S|3|T|5|6|7|16|8|@]|9|@]|A|$]]|$1|U|3|V|5|6|7|17|8|@]|9|@]|A|$]]|$1|W|3|-4|5|6|7|18|8|@]|9|@]|A|$]]]|X|$]]

Ok, this is really hard, and the only solution I could come up with, remembers me of Kirks solution to the Kobayashi Maru test (somehow cheated):
The idea, is that we use stack of stacks (and use this to model a list).
I call the operations en/dequeue and push and pop, then we get:

<pre><code>queue.new() : Stack1 = Stack.new(&lt;Stack&gt;); 
 Stack2 = Stack1; 

enqueue(element): Stack3 = Stack.new(&lt;TypeOf(element)&gt;); 
 Stack3.push(element); 
 Stack2.push(Stack3);
 Stack3 = Stack.new(&lt;Stack&gt;);
 Stack2.push(Stack3);
 Stack2 = Stack3; 

dequeue(): Stack3 = Stack1.pop(); 
 Stack1 = Stack1.pop();
 dequeue() = Stack1.pop()
 Stack1 = Stack3;

isEmtpy(): Stack1.isEmpty();
</code></pre>

(StackX = StackY is no copying of the contents, just a copy of reference. Its just to describe it easy. You could also use an array of 3 stacks and access them via index, there you would just change the value of the index variable). Everything is in O(1) in stack-operation-terms.

And yes I know its argueable, because we have implicit more than 3 stacks, but maybe it give others of you good ideas.

EDIT: Explanation example:

<pre><code> | | | |3| | | |
 | | | |_| | | |
 | | |_____| | |
 | | | |
 | | |2| | |
 | | |_| | |
 | |_________| |
 | |
 | |1| |
 | |_| |
 |_____________|
</code></pre>

I tried here with a little ASCII-art to show Stack1. 

Every element is wrapped in a single element stack (so we have only typesafe stack of stacks).

You see to remove we first pop the first element (the stack containing here element 1 and 2). Then pop the next element and unwrap there the 1. Afterwards we say that the first poped stack is now our new Stack1. To speak a little more functional - these are lists implement by stacks of 2 elements where the top element ist cdr and the first/below top element is car. The other 2 are helping stacks. 

Esp tricky is the inserting, as you have somehow have to dive deep into the nested stacks to add another element. Thats why Stack2 is there. Stack2 is always the innermost stack. Adding is then just pushing an element in and then pushing ontop a new Stack2 (and thats why we are not allowed to touch Stack2 in our dequeue operation).

blocks|key|3190681|text|我将尝试一个证明来证明这是不可能的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3190682|3190683|假设有一个队列Q，它由3个堆栈A、B和C模拟。|3190684|断言|3190685|进一步，假设Q可以模拟O(1)中的操作{|3190686|，ASRT0+:=+}。这意味着对于每个队列/出队操作都存在特定的堆栈推送/弹出序列，假设队列操作是deterministic.|unordered-list-item|3190687|
的(+simulated.|3190688|Without+)而失去一般性|3190689|3190690|让在Q中排队的元素根据它们的队列顺序被编号为1，2，...，其中排入Q中的第一个元素被定义为1，第二个被定义为2，依此类推。|3190691|定义|3190692|当Q中有0个元素(以及A，B中的0个元素)时，|3190693|Q(0)+:=+Q的状态，并且在Q(0)|offset|length|style|CODE|3190694|Q(n)+:=上进行1次队列操作之后，C)|3190695|Q(1)+:=+Q(以及A，B和C)的状态在Q(0)|3190696|上进行n次队列操作之后，Q的状态(以及A，B和C|3190697|3190698|3190699|%7CQ(n)%7C+:=+Q(n)中的元素数量(因此，当Q的状态为Q(n)|3190700|%7CA(n)%7C+:=时，堆栈A的状态为A(n)|3190701|中的元素数量|3190702|以及对堆栈B和C的类似定义。|3190703|平凡的是，|3190704|%7CQ(n)%7C+=+%7CA(n)%7C+%2B+%7CB(n)%7C+%2B+%7CC(n)%7C

---|code-block|syntax|javascript|3190705|%7CQ(n)%7C显然在n上是无界的。|3190706|因此，%7CA(n)%7C、%7CB(n)%7C或%7CC(n)%7C中至少有一个在n上是无界的。|3190707|WLOG1，假设堆栈A是无界的，而堆栈B和C是有界的。|3190708|定义*+B_u+:=是B*+C_u+:=的上界，是C*+K+:=+B_u+%2B+C_u+%2B+1的上界|3190709|WLOG2，对于n这样的%7CA(n)%7C+>+K，从Q(n)中选择K个元素。假设对于所有的x+>=+0，这些元素中有1个在A(n+%2B+x)中，也就是说，无论完成多少个队列操作，该元素总是在堆栈A中。|3190710|3190711|X+:=+|3190712|的那个元素|3190713|然后我们就可以定义|3190714|3190715|Abv(n)+:=大于X|3190716|Blo(n)+:=的堆栈A(n)中的项数小于X的堆栈A(n)中的元素数|3190717|3190718|%7CA(n)%7C+=+Abv(n)+%2B+Blo(n)|3190719|ASRT1+:=从Q(n)出队X所需的pops数至少为Abv(n)|3190720|从(ASRT0)和(ASRT1)开始，ASRT2+:=+Abv(n)必须是有界的。|3190721|如果Abv(n)是无界的，则如果需要20个出队才能将X从Q(n)出队，则至少需要Abv(n)/20+pops。它是无界的。20可以是任何常量。|3190722|因此，|3190723|ASRT3+:=+Blo(n)+=+%7CA(n)%7C+-+Abv(n)|3190724|必须是无界的。|3190725|3190726|WLOG3，我们可以从A(n)的底部选择K个元素，其中一个元素位于A(n+%2B+x)中，用于所有x+>=+0|3190727|对于任何给定的n，X(n)+:=该元素|3190728|ASRT4+:=+Abv(n)+>=+%7CA(n)%7C+-+K|3190729|当一个元素在Q(n)中排队时...|3190730|WLOG4，假设B和C已经填充到它们的上界。假设已经达到了X(n)以上元素的上限。然后，一个新元素进入A。|3190731|WLOG5，假设作为结果，新元素必须在X(n)下面输入。|3190732|ASRT5+:=将元素放在X(n)+>=+Abv(X(n))以下所需的pops数量|3190733|在(ASRT4)中，Abv(n)在n上是无界的。|3190734|因此，将元素放在X(n)之下所需的pops数量是无限的。|3190735|3190736|这与ASRT1相矛盾，因此，不可能模拟具有3个堆栈的O(1)队列。|3190737|3190738|也就是说。|3190739|至少有一个堆栈必须是未绑定的。|3190740|对于驻留在该堆栈中的元素，其上方的元素数量必须是有界的，否则移除该元素的出队操作将是无界的。|3190741|然而，如果超过它的元素的数量是有界的，那么它将达到一个限制。在某些情况下，必须在其下方输入一个新元素。|3190742|因为我们总是可以从堆栈中最低的几个元素中选择旧元素，所以它上面可以有无限数量的元素(基于无界堆栈的无限大小)。|3190743|要在它下面输入一个新元素，因为它上面有无限数量的元素，所以需要无限数量的pops才能将新元素放在它下面。|3190744|这样就产生了矛盾。|3190745|3190746|有5个WLOG+(不失一般性)语句。在某种意义上，可以直观地理解它们是真的(但考虑到它们是5，这可能需要一些时间)。可以推导出没有丢失共性的形式证明，但非常冗长。它们被省略了。|3190747|我承认，这样的遗漏可能会使WLOG声明受到质疑。由于程序员对bug的偏执，如果您愿意的话，请务必验证WLOG语句。|3190748|第三个堆栈也是不相关的。重要的是有一组有界堆栈和一组无界堆栈。一个示例最少需要2个堆栈。当然，堆栈的数量必须是有限的。|3190749|最后，如果我是对的，没有证据，那么应该有一个更容易的归纳证明。可能基于每个队列之后发生的事情(在给定队列中所有元素的集合的情况下，跟踪它对出队的最坏情况的影响)。|3190750|entityMap^0|0|0|0|0|0|0|0|0|0|0|0|0|0|7|G|4|0|0|7|0|0|7|M|4|0|0|0|0|0|9|A|4|U|4|0|0|9|I|4|0|0|0|0|0|0|6|0|3|6|A|6|H|6|0|0|5|0|4|6|E|6|S|I|0|0|5|C|A|O|4|17|6|1N|8|0|0|0|4|0|0|0|0|0|9|0|0|9|C|4|Q|4|0|0|0|0|8|9|4|R|6|0|2|5|A|5|J|F|0|2|6|S|4|14|9|0|0|0|0|0|0|5|B|4|X|8|1B|6|0|9|7|0|0|6|4|0|0|5|T|4|0|0|5|J|4|0|0|8|D|H|0|1|7|A|6|0|8|4|0|0|2|5|Q|4|0|0|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|42|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|43|8|@]|9|@]|A|$]]|$1|C|3|D|5|6|7|44|8|@]|9|@]|A|$]]|$1|E|3|F|5|6|7|45|8|@]|9|@]|A|$]]|$1|G|3|H|5|6|7|46|8|@]|9|@]|A|$]]|$1|I|3|J|5|K|7|47|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|48|8|@]|9|@]|A|$]]|$1|N|3|O|5|K|7|49|8|@]|9|@]|A|$]]|$1|P|3|-4|5|6|7|4A|8|@]|9|@]|A|$]]|$1|Q|3|R|5|6|7|4B|8|@]|9|@]|A|$]]|$1|S|3|T|5|6|7|4C|8|@]|9|@]|A|$]]|$1|U|3|V|5|6|7|4D|8|@]|9|@]|A|$]]|$1|W|3|X|5|K|7|4E|8|@$Y|4F|Z|4G|10|11]|$Y|4H|Z|4I|10|11]]|9|@]|A|$]]|$1|12|3|13|5|K|7|4J|8|@$Y|4K|Z|4L|10|11]]|9|@]|A|$]]|$1|14|3|15|5|K|7|4M|8|@$Y|4N|Z|4O|10|11]|$Y|4P|Z|4Q|10|11]]|9|@]|A|$]]|$1|16|3|17|5|6|7|4R|8|@]|9|@]|A|$]]|$1|18|3|T|5|6|7|4S|8|@]|9|@]|A|$]]|$1|19|3|-4|5|6|7|4T|8|@]|9|@]|A|$]]|$1|1A|3|1B|5|K|7|4U|8|@$Y|4V|Z|4W|10|11]|$Y|4X|Z|4Y|10|11]|$Y|4Z|Z|50|10|11]]|9|@]|A|$]]|$1|1C|3|1D|5|K|7|51|8|@$Y|52|Z|53|10|11]|$Y|54|Z|55|10|11]]|9|@]|A|$]]|$1|1E|3|1F|5|6|7|56|8|@]|9|@]|A|$]]|$1|1G|3|1H|5|6|7|57|8|@]|9|@]|A|$]]|$1|1I|3|1J|5|6|7|58|8|@]|9|@]|A|$]]|$1|1K|3|1L|5|1M|7|59|8|@]|9|@]|A|$1N|1O]]|$1|1P|3|1Q|5|6|7|5A|8|@$Y|5B|Z|5C|10|11]]|9|@]|A|$]]|$1|1R|3|1S|5|6|7|5D|8|@$Y|5E|Z|5F|10|11]|$Y|5G|Z|5H|10|11]|$Y|5I|Z|5J|10|11]]|9|@]|A|$]]|$1|1T|3|1U|5|6|7|5K|8|@$Y|5L|Z|5M|10|11]]|9|@]|A|$]]|$1|1V|3|1W|5|6|7|5N|8|@$Y|5O|Z|5P|10|11]|$Y|5Q|Z|5R|10|11]|$Y|5S|Z|5T|10|11]]|9|@]|A|$]]|$1|1X|3|1Y|5|6|7|5U|8|@$Y|5V|Z|5W|10|11]|$Y|5X|Z|5Y|10|11]|$Y|5Z|Z|60|10|11]|$Y|61|Z|62|10|11]|$Y|63|Z|64|10|11]]|9|@]|A|$]]|$1|1Z|3|-4|5|6|7|65|8|@]|9|@]|A|$]]|$1|20|3|21|5|K|7|66|8|@$Y|67|Z|68|10|11]]|9|@]|A|$]]|$1|22|3|23|5|6|7|69|8|@]|9|@]|A|$]]|$1|24|3|25|5|6|7|6A|8|@]|9|@]|A|$]]|$1|26|3|-4|5|6|7|6B|8|@]|9|@]|A|$]]|$1|27|3|28|5|K|7|6C|8|@$Y|6D|Z|6E|10|11]]|9|@]|A|$]]|$1|29|3|2A|5|K|7|6F|8|@$Y|6G|Z|6H|10|11]|$Y|6I|Z|6J|10|11]|$Y|6K|Z|6L|10|11]]|9|@]|A|$]]|$1|2B|3|-4|5|6|7|6M|8|@]|9|@]|A|$]]|$1|2C|3|2D|5|6|7|6N|8|@]|9|@]|A|$]]|$1|2E|3|2F|5|6|7|6O|8|@$Y|6P|Z|6Q|10|11]|$Y|6R|Z|6S|10|11]|$Y|6T|Z|6U|10|11]]|9|@]|A|$]]|$1|2G|3|2H|5|6|7|6V|8|@$Y|6W|Z|6X|10|11]|$Y|6Y|Z|6Z|10|11]|$Y|70|Z|71|10|11]]|9|@]|A|$]]|$1|2I|3|2J|5|6|7|72|8|@$Y|73|Z|74|10|11]|$Y|75|Z|76|10|11]|$Y|77|Z|78|10|11]]|9|@]|A|$]]|$1|2K|3|2L|5|6|7|79|8|@]|9|@]|A|$]]|$1|2M|3|2N|5|1M|7|7A|8|@]|9|@]|A|$1N|1O]]|$1|2O|3|2P|5|6|7|7B|8|@]|9|@]|A|$]]|$1|2Q|3|-4|5|6|7|7C|8|@]|9|@]|A|$]]|$1|2R|3|2S|5|6|7|7D|8|@$Y|7E|Z|7F|10|11]|$Y|7G|Z|7H|10|11]|$Y|7I|Z|7J|10|11]|$Y|7K|Z|7L|10|11]]|9|@]|A|$]]|$1|2T|3|2U|5|6|7|7M|8|@$Y|7N|Z|7O|10|11]]|9|@]|A|$]]|$1|2V|3|2W|5|1M|7|7P|8|@]|9|@]|A|$1N|1O]]|$1|2X|3|2Y|5|6|7|7Q|8|@$Y|7R|Z|7S|10|11]]|9|@]|A|$]]|$1|2Z|3|30|5|6|7|7T|8|@$Y|7U|Z|7V|10|11]|$Y|7W|Z|7X|10|11]]|9|@]|A|$]]|$1|31|3|32|5|6|7|7Y|8|@$Y|7Z|Z|80|10|11]|$Y|81|Z|82|10|11]]|9|@]|A|$]]|$1|33|3|34|5|6|7|83|8|@$Y|84|Z|85|10|11]|$Y|86|Z|87|10|11]]|9|@]|A|$]]|$1|35|3|36|5|6|7|88|8|@$Y|89|Z|8A|10|11]|$Y|8B|Z|8C|10|11]]|9|@]|A|$]]|$1|37|3|38|5|6|7|8D|8|@$Y|8E|Z|8F|10|11]]|9|@]|A|$]]|$1|39|3|-4|5|6|7|8G|8|@]|9|@]|A|$]]|$1|3A|3|3B|5|6|7|8H|8|@$Y|8I|Z|8J|10|11]|$Y|8K|Z|8L|10|11]]|9|@]|A|$]]|$1|3C|3|-4|5|6|7|8M|8|@]|9|@]|A|$]]|$1|3D|3|3E|5|6|7|8N|8|@]|9|@]|A|$]]|$1|3F|3|3G|5|6|7|8O|8|@]|9|@]|A|$]]|$1|3H|3|3I|5|6|7|8P|8|@]|9|@]|A|$]]|$1|3J|3|3K|5|6|7|8Q|8|@]|9|@]|A|$]]|$1|3L|3|3M|5|6|7|8R|8|@]|9|@]|A|$]]|$1|3N|3|3O|5|6|7|8S|8|@]|9|@]|A|$]]|$1|3P|3|3Q|5|6|7|8T|8|@]|9|@]|A|$]]|$1|3R|3|-4|5|6|7|8U|8|@]|9|@]|A|$]]|$1|3S|3|3T|5|6|7|8V|8|@]|9|@]|A|$]]|$1|3U|3|3V|5|6|7|8W|8|@]|9|@]|A|$]]|$1|3W|3|3X|5|6|7|8X|8|@]|9|@]|A|$]]|$1|3Y|3|3Z|5|6|7|8Y|8|@]|9|@]|A|$]]|$1|40|3|-4|5|6|7|8Z|8|@]|9|@]|A|$]]]|41|$]]

I am going to attempt a proof to show that it can't be done.

<hr>

Suppose there is a queue Q that is simulated by 3 stacks, A, B and C.

<h3>Assertions</h3>

<ul>
<li>ASRT0 := Furthermore, assume that Q can simulate operations {queue,dequeue} in O(1). This means that there exists a specific sequence of stack push/pops for every queue/dequeue operation to be simulated.</li>
<li>Without loss of generality, assume the queue operations are deterministic.</li>
</ul>

Let the elements queued into Q be numbered 1, 2, ..., based on their order of queue, with the first element that is queued into Q being defined as 1, the second one as 2, and so on.

Define

<ul>
<li><code>Q(0) :=</code> The state of Q when there are 0 elements in Q (and thus 0 elements in A, B and C)</li>
<li><code>Q(1) :=</code> The state of Q (and A, B and C) after 1 queue operation on <code>Q(0)</code></li>
<li><code>Q(n) :=</code> The state of Q (and A, B and C) after n queue operations on <code>Q(0)</code></li>
</ul>

Define

<ul>
<li><code>|Q(n)| :=</code> the number of elements in <code>Q(n)</code> (therefore <code>|Q(n)| = n</code>)</li>
<li><code>A(n) :=</code> the state of the stack A when the state of Q is <code>Q(n)</code></li>
<li><code>|A(n)| :=</code> the number of elements in <code>A(n)</code></li>
</ul>

And similar definitions for stacks B and C.

Trivially,

<pre><code>|Q(n)| = |A(n)| + |B(n)| + |C(n)|

---
</code></pre>

<code>|Q(n)|</code> is obviously unbounded on n.

Therefore, at least one of <code>|A(n)|</code>, <code>|B(n)|</code> or <code>|C(n)|</code> is unbounded on n.

<code>WLOG1</code>, suppose stack A is unbounded and stacks B and C are bounded.

Define
* <code>B_u :=</code> an upper bound of B
* <code>C_u :=</code> an upper bound of C
* <code>K := B_u + C_u + 1</code>

<code>WLOG2</code>, for an n such that <code>|A(n)| &gt; K</code>, select K elements from <code>Q(n)</code>. Suppose that 1 of those elements is in <code>A(n + x)</code>, for all <code>x &gt;= 0</code>, i.e. the element is always in stack A no matter how many queue operations are done.

<ul>
<li><code>X :=</code> that element</li>
</ul>

Then we can define 

<ul>
<li><code>Abv(n) :=</code> the number of items in stack <code>A(n)</code> that is above X</li>
<li><code>Blo(n) :=</code> the number of elements in stack <code>A(n)</code> that is below X

|A(n)| = Abv(n) + Blo(n)</li>
</ul>

<code>ASRT1 :=</code> The number of pops required to dequeue X from <code>Q(n)</code> is at least <code>Abv(n)</code>

From (<code>ASRT0</code>) and (<code>ASRT1</code>), <code>ASRT2 := Abv(n)</code> must be bounded.

If <code>Abv(n)</code> is unbounded, then if 20 dequeues are required to dequeue X from <code>Q(n)</code>, it will require at least <code>Abv(n)/20</code> pops. Which is unbounded. 20 can be any constant.

Therefore,

<pre><code>ASRT3 := Blo(n) = |A(n)| - Abv(n)
</code></pre>

must be unbounded.

<hr>

<code>WLOG3</code>, we can select the K elements from the bottom of <code>A(n)</code>, and one of them is in <code>A(n + x)</code> for all <code>x &gt;= 0</code>

<code>X(n) :=</code> that element, for any given n

<pre><code>ASRT4 := Abv(n) &gt;= |A(n)| - K
</code></pre>

Whenever an element is queued into <code>Q(n)</code>...

<code>WLOG4</code>, suppose B and C are already filled to their upper bounds. Suppose that the upper bound for elements above <code>X(n)</code> has been reached. Then, a new element enters A.

<code>WLOG5</code>, suppose that as a result, the new element must enter below <code>X(n)</code>.

<code>ASRT5 :=</code> The number of pops required to put an element below <code>X(n) &gt;= Abv(X(n))</code>

From <code>(ASRT4)</code>, <code>Abv(n)</code> is unbounded on n.

Therefore, the number of pops required to put an element below <code>X(n)</code> is unbounded.

<hr>

This contradicts <code>ASRT1</code>, therefore, it is not possible to simulate an <code>O(1)</code> queue with 3 stacks.

<hr>

I.e.

At least 1 stack must be unbounded.

For an element that stays in that stack, the number of elements above it must be bounded, or the dequeue operation to remove that element will be unbounded.

However, if the number of elements above it is bounded, then it will reach a limit. At some point, a new element must enter below it.

Since we can always choose the old element from among one of the lowest few elements of that stack, there can be an unbounded number of elements above it (based on the unbounded size of the unbounded stack).

To enter a new element below it, since there's an unbounded number of elements above it, an unbounded number of pops is required to put the new element below it.

And thus the contradiction.

<hr>

There are 5 WLOG (Without loss of generality) statements. In some sense, they can be intuitively understood to be true (but given that they are 5, it might take some time). The formal proof that no generality is lost can be derived, but is extremely lengthy. They're omitted.

I do admit that such omission might leave the WLOG statements in question. With a programmer's paranoia for bugs, please do verify the WLOG statements if you like to.

The third stack is also irrelevant. What matters is that there's a set of bounded stacks, and a set of unbounded stacks. The minimum needed for an example is 2 stacks. The number of stacks must be, of course, finite.

Lastly, if I am right that there's no proof, then there should be an easier inductive proof available. Probably based on what happens after every queue (keep track of how it affects the worst case of dequeue given the set of all elements in the queue).

blocks|key|2976905|text|摘要|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2976906|2976907|O(1)算法已知为6个堆栈|unordered-list-item|2976908|O(1)算法已知为3个堆栈，但使用惰性评估实际上对应于具有额外的内部数据结构，因此它不构成Sedgewick附近的问题已确认他们不知道原始问题|2976909|的所有约束内的3-堆栈解决方案|2976910|详细信息|2976911|这个链接背后有两个实现：http://www.eecs.usma.edu/webs/people/okasaki/jfp95/index.html|offset|length|2976912|其中一个是具有三个堆栈的O(1)，但它使用延迟执行，这实际上会创建额外的中间数据结构(闭包)。|2976913|其中另一个是O(1)，但使用了六个堆栈。然而，它在没有延迟执行的情况下工作。|2976914|更新:Okasaki的论文在这里：http://www.eecs.usma.edu/webs/people/okasaki/jfp95.ps，看起来他实际上只使用了2个栈来表示具有惰性评估的O(1)版本。问题是它实际上是基于懒惰的评估。问题是，它是否可以在不进行惰性评估的情况下转换为3-stack算法。|2976915|更新:另一个相关算法在Holger+Petersen的论文"Stacks+is“中描述，发表在第七届年度计算和组合会议上。你可以在Google+Books上找到这篇文章。查看第225-226页。但该算法并不是真正的实时模拟，它是对三个堆栈上的双端队列的线性时间模拟。|2976916|gusbro：“就像@Leonel几天前说的那样，我认为如果Sedgewick教授知道解决方案或有什么错误，与他核实一下是公平的。所以我确实给他写了信。我刚刚收到了一个回复(虽然不是来自他自己，而是来自普林斯顿的一个同事)，所以我想和所有的you.He分享，他基本上说他不知道使用三个堆栈的算法和施加的其他约束(比如不使用惰性评估)。他确实知道一种使用6个堆栈的算法，正如我们已经知道的那样，查看这里的答案。因此，我猜这个问题仍然悬而未决，无法找到算法(或者证明找不到算法)。|2976917|entityMap|0|LINK|mutability|MUTABLE|url|http://www.eecs.usma.edu/webs/people/okasaki/jfp95/index.html|1|http://www.eecs.usma.edu/webs/people/okasaki/jfp95.ps^0|0|0|0|0|0|0|C|1P|0|0|0|0|H|1H|1|0|0|0^^$0|@$1|2|3|4|5|6|7|19|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|1A|8|@]|9|@]|A|$]]|$1|C|3|D|5|E|7|1B|8|@]|9|@]|A|$]]|$1|F|3|G|5|E|7|1C|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|1D|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|1E|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|1F|8|@]|9|@$N|1G|O|1H|1|1I]]|A|$]]|$1|P|3|Q|5|6|7|1J|8|@]|9|@]|A|$]]|$1|R|3|S|5|6|7|1K|8|@]|9|@]|A|$]]|$1|T|3|U|5|6|7|1L|8|@]|9|@$N|1M|O|1N|1|1O]]|A|$]]|$1|V|3|W|5|6|7|1P|8|@]|9|@]|A|$]]|$1|X|3|Y|5|6|7|1Q|8|@]|9|@]|A|$]]|$1|Z|3|-4|5|6|7|1R|8|@]|9|@]|A|$]]]|10|$11|$5|12|13|14|A|$15|16]]|17|$5|12|13|14|A|$15|18]]]]

SUMMARY

<ul>
<li>O(1) algorithm is known for 6 stacks</li>
<li>O(1) algorithm is known for 3 stacks, but using lazy evaluation which in practice corresponds to having extra internal data structures, so it does not constitute a solution</li>
<li>People near Sedgewick have confirmed they are not aware of a 3-stack solution within all the constraints of the original question</li>
</ul>

DETAILS

There are two implementations behind this link: <a href="http://www.eecs.usma.edu/webs/people/okasaki/jfp95/index.html">http://www.eecs.usma.edu/webs/people/okasaki/jfp95/index.html</a>

One of them is O(1) with three stacks BUT it uses lazy execution, which in practice creates extra intermediate data structures (closures).

Another of them is O(1) but uses SIX stacks. However, it works without lazy execution.

UPDATE: Okasaki's paper is here: <a href="http://www.eecs.usma.edu/webs/people/okasaki/jfp95.ps">http://www.eecs.usma.edu/webs/people/okasaki/jfp95.ps</a> and it seems that he actually uses only 2 stacks for the O(1) version that has lazy evaluation. The problem is that it's really based on lazy evaluation. The question is if it can be translated to a 3-stack algorithm without lazy evaluation.

UPDATE: Another related algorithm is described in paper "Stacks versus Deques" by Holger Petersen, published in 7th Annual Conference on Computing and Combinatorics. You can find the article from Google Books. Check pages 225-226. But the algorithm is not actually real-time simulation, it's linear-time simulation of a double-ended queue on three stacks.

gusbro: "As @Leonel said some days ago, I thought it would be fair to check with Prof. Sedgewick if he knew a solution or there was some mistake. So I did write to him. I just received a response (albeit not from himself but from a colleague at Princeton) so I like to share with all of you.He basically said that he knew of no algorithms using three stacks AND the other constraints imposed (like not using lazy evaluation). He did know of an algorithm using 6 stacks as we already know looking at the answers here. So I guess the question is still open to find an algorithm (or prove one cannot be found)."

blocks|key|275446|text|注意:这是对具有单链表的实时(常量时间最坏情况)队列的功能实现的注释。由于声誉的原因，我不能添加评论，但如果有人可以将其更改为antti.huima在答案中附加的评论，那就太好了。话又说回来，评论有点太长了。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|275447|@antti.huima:链表与堆栈不同。|275448|275449|s1+=+(1+2+3+4)+-包含4个节点的链表，每个节点指向右侧的一个节点，并保持值1、2、3和4|unordered-list-item|275450|s2+=+popped(s1)+-+s2+is+now+(2+3+4)|275451|275452|在这一点上，s2等同于弹出(S1)，它的行为类似于堆栈。但是，s1仍可供参考！|275453|275454|s3+=+popped(popped(s1))+-+s3+is+(3+4)|275455|275456|我们仍然可以窥视s1得到1，而在正确的堆栈实现中，元素1从s1中消失了！|275457|这是什么意思？|275458|275459|s1是对堆栈顶部的引用|275460|s2是对堆栈第二个元素的引用|275461|s3是对第三个元素的引用...|275462|275463|现在创建的附加链表每个都用作引用/指针！有限数量的堆栈无法做到这一点。|275464|根据我在论文/代码中看到的，算法都利用链表的这一属性来保留引用。|275465|编辑:我只是指的是2和3链表算法利用了链表的这个属性，因为我先读了它们(它们看起来更简单)。这并不意味着它们是或不适用的，只是为了解释链表不一定是相同的。等我有空的时候，我会读有6的那本书。@Welbog:谢谢您的更正。|275466|275467|懒惰也可以用类似的方式模拟指针功能。|275468|275469|使用链表解决了一个不同的问题。此策略可用于在Lisp中实现实时队列(或者至少是坚持从链表构建所有内容的Lisp)：请参阅“纯Lisp中的实时队列操作”(通过antti.huima的链接进行链接)。这也是一种设计具有O(1)操作时间和共享(不可变)结构的不可变列表的好方法。|275470|entityMap^0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|1G|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1H|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|1I|8|@]|9|@]|A|$]]|$1|E|3|F|5|G|7|1J|8|@]|9|@]|A|$]]|$1|H|3|I|5|G|7|1K|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|1L|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|1M|8|@]|9|@]|A|$]]|$1|M|3|-4|5|6|7|1N|8|@]|9|@]|A|$]]|$1|N|3|O|5|G|7|1O|8|@]|9|@]|A|$]]|$1|P|3|-4|5|6|7|1P|8|@]|9|@]|A|$]]|$1|Q|3|R|5|6|7|1Q|8|@]|9|@]|A|$]]|$1|S|3|T|5|6|7|1R|8|@]|9|@]|A|$]]|$1|U|3|-4|5|6|7|1S|8|@]|9|@]|A|$]]|$1|V|3|W|5|G|7|1T|8|@]|9|@]|A|$]]|$1|X|3|Y|5|G|7|1U|8|@]|9|@]|A|$]]|$1|Z|3|10|5|G|7|1V|8|@]|9|@]|A|$]]|$1|11|3|-4|5|6|7|1W|8|@]|9|@]|A|$]]|$1|12|3|13|5|6|7|1X|8|@]|9|@]|A|$]]|$1|14|3|15|5|6|7|1Y|8|@]|9|@]|A|$]]|$1|16|3|17|5|6|7|1Z|8|@]|9|@]|A|$]]|$1|18|3|-4|5|6|7|20|8|@]|9|@]|A|$]]|$1|19|3|1A|5|6|7|21|8|@]|9|@]|A|$]]|$1|1B|3|-4|5|6|7|22|8|@]|9|@]|A|$]]|$1|1C|3|1D|5|6|7|23|8|@]|9|@]|A|$]]|$1|1E|3|-4|5|6|7|24|8|@]|9|@]|A|$]]]|1F|$]]

Note: This is meant to be a comment to the functional implementation of real-time ( constant time worst case ) queues with singly-linked-lists. I can't add comments due to reputation, but it'll be nice if someone could change this to a comment appended to the answer by antti.huima. Then again, it is somewhat long for a comment.

@antti.huima:
Linked lists are not the same as a stack.

<ul>
<li>s1 = (1 2 3 4) --- a linked list with 4 nodes, each pointing to the one on the right, and holding values 1, 2, 3 and 4</li>
<li>s2 = popped(s1) --- s2 is now (2 3 4)</li>
</ul>

At this point, s2 is equivalent to popped(s1), which behaves like a stack. However, s1 is still available for reference!

<ul>
<li>s3 = popped(popped(s1)) --- s3 is (3 4)</li>
</ul>

We can still peek into s1 to get 1, whereas in a proper stack implementation, element 1 is gone from s1!

What does this mean?

<ul>
<li>s1 is the reference to the top of the stack</li>
<li>s2 is the reference to the second element of the stack</li>
<li>s3 is the reference to the third ...</li>
</ul>

The additional linked-lists created now each serves as a reference/pointer! A finite number of stacks can't do that.

From what I see in the papers/code, the algorithms all make use of this property of linked-lists to retain references.

Edit: I'm referring only to the 2 and 3 linked-list algorithms make use of this property of linked-lists, as I read them first (they looked simpler). This is not meant to show that they are or are not applicable, just to explain that linked-lists aren't necessarily identical. I'll read the one with 6 when I'm free. @Welbog: Thanks for the correction.

<hr>

Laziness can also simulate pointer-functionality in similar ways.

<hr>

Using linked-list solves a different problem. This strategy can be used to implement real-time queues in Lisp (Or at least Lisps that insist on building everything from linked-lists): Refer to "Real Time Queue Operations in Pure Lisp" (linked to through antti.huima's links). It's also a nice way to design immutable lists with O(1) operation time and shared (immutable) structures.

blocks|key|271902|text|你可以用两个堆栈在分期固定的时间内完成：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|271903|-------------+--------------
++++++++++++%7C+%7C
-------------+--------------|code-block|syntax|javascript|271904|Adding为O(1)，removing为O(1)，如果要获取的堆栈不为空，则为O(n)，否则为O(n)(将另一个堆栈一分为二)。|offset|length|style|CODE|271905|诀窍是看到O(n)操作将仅在每个O(n)时间内执行(如果您将其拆分，例如对半)。因此，操作的平均时间是O(1)%2BO(n)/O(n)+=+O(1)。|271906|虽然这看起来像是一个问题，但如果您使用的是一种带有基于数组的堆栈的命令式语言(最快)，那么无论如何您将只有分期不变的时间。|271907|entityMap^0|0|0|7|4|L|4|14|4|1C|4|0|5|4|G|4|1F|L|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|U|8|@$I|V|J|W|K|L]|$I|X|J|Y|K|L]|$I|Z|J|10|K|L]|$I|11|J|12|K|L]]|9|@]|A|$]]|$1|M|3|N|5|6|7|13|8|@$I|14|J|15|K|L]|$I|16|J|17|K|L]|$I|18|J|19|K|L]]|9|@]|A|$]]|$1|O|3|P|5|6|7|1A|8|@]|9|@]|A|$]]|$1|Q|3|-4|5|6|7|1B|8|@]|9|@]|A|$]]]|R|$]]

You can do it in amortized constant time with two stacks:

<pre><code>------------- --------------
 | |
------------- --------------
</code></pre>

Adding is <code>O(1)</code> and removing is <code>O(1)</code> if the side you want to take from is not empty and <code>O(n)</code> otherwise (split the other stack in two).

The trick is to see that the <code>O(n)</code> operation will only be done every <code>O(n)</code> time (if you split, e.g. in halves). Hence, the average time for an operation is <code>O(1)+O(n)/O(n) = O(1)</code>.

While this may seam like a problem, if you are using an imperative language with an array based stack (fastest), you are going to have only amortized constant time anyway.

I came across this question in an algorithms book (<a href="https://rads.stackoverflow.com/amzn/click/com/032157351X" rel="noreferrer" rel="nofollow noreferrer">Algorithms, 4th Edition</a> by Robert Sedgewick and Kevin Wayne). 

<blockquote>
 Queue with three stacks. Implement a queue with three stacks so that each queue operation takes a constant (worst-case) number of stack operations. Warning : high degree of difficulty.
</blockquote>

I know how to make a queue with 2 stacks but I can't find the solution with 3 stacks. Any idea ? 

(oh and, this is not homework :) )

How to implement a queue with three stacks?

数据结构

我在一本算法书( Robert Sedgewick和Kevin Wayne的)中遇到了这个问题。具有三个堆栈的队列。实现一个具有三个堆栈的队列，以便每个队列操作都需要恒定(最坏情况下)数量的堆栈操作。警告:难度很高。我知道如何使用2个堆栈来创建一个队列，但是我找不到使用3个堆栈的解决方案。有什么想法吗？(哦，这不是家庭...

问如何实现一个有三个栈的队列？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何实现一个有三个栈的队列？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何实现一个有三个栈的队列？
EN