确定堆栈/队列大小的调用数
问题1
您有一个包含n个条目的抽象堆栈和一个空的抽象队列(用于帮助)。大约需要多少次呼叫才能确定n？堆栈之后需要保持不变。
问题2
同样的问题，但您从抽象队列开始，并有一个空的抽象堆栈。
我的推理
从堆栈->推到队列->，从队列->到栈->，从堆栈->推送到队列->，从队列->到堆栈。在某个地方，我们加入了一个计数器，这使它成为8*n调用(9*n，如果计数器调用数)。我看不出怎样才能将这些项目从堆栈中弹出，然后按正确的顺序返回。有更好的方法吗？
回答 1
Stack Overflow用户
发布于 2016-03-17 12:07:51
Q1。一个更好的解决办法可以是：
- 流行
- 排队
- 去队列
- 推
通过这样做，就可以得到4*n的运算。
例如，设为堆栈: 1，2，3(以1作为顶部)
设s为堆栈，q为队列。
q.enqueue(s.pop())，所以现在s= 2，3和q=1
q.enqueue(s.pop())，所以现在s=3，q= 1，2
q.enqueue(s.pop())，所以现在s= []和q= 1，2，3
s.push(q.dequeue())，所以现在s=1，q= 2，3
s.push(q.dequeue())，所以现在s= 2，1和q=3
s.push(q.dequeue())，所以现在s= 3，2，1和q= []
q.enqueue(s.pop())，所以现在s= 2，1和q=3
q.enqueue(s.pop())，所以现在s=1，q= 3，2
q.enqueue(s.pop())，所以现在s= []和q= 3，2，1
s.push(q.dequeue())，所以现在s=3，q= 2，1
s.push(q.dequeue())，所以现在s= 2，3和q=1
s.push(q.dequeue())，所以现在s= 1，2，3和q= []
我不认为这是最好的解决方案，但这是一个更好的解决方案(9*n对4*n，总是O(n))
Q2。我认为现在可以使用以前情况下相同的(不是最优的)算法。
主要思想是，当您从堆栈中获得一个项时，这将是队列的最后一个，因为这两个数据结构有不同的输入方式。
希望这对你有帮助：)
https://stackoverflow.com/questions/36059066
复制相似问题
腾讯云开发者
