使用队列堆栈

Question

我正在浏览一些面试问题，并偶然发现了这个问题。它让我把头发撕开。

有谁知道如何使用队列实现堆栈？

Answer 1

push：将元素插入到队列的后面。

pop：从前面删除一个元素，立即将它插入到后面，重复N-1次，其中N是队列的大小，然后删除最后一个元素并返回它。

Answer 2

版本A：

推：

排队的队列1

流行：

而队列1的大小比1大，管出列从队列1项放入队列2 出队和回报队列1的最后一项，然后切换队列1和队列2的名称

版本B：

推：

排队的队列2 排队的队列2队列1的所有项目，然后再切换队列1的名称和队列2

流行：

deqeue从队列1

Answer 3

概念使用一个队列实现堆栈需要O（2n）或（机器独立）O（n）空间复杂度。但是，如果您正在为大型阵列工作，那么在您尝试仅使用一个阵列时，时间复杂度可能不是O（n^2）或O（n *（n + 1）/ 2）队列。