backgroundSeveral years ago, when I was an undergraduate, we were given a homework on amortized analysis. I was unable to solve one of the problems. I had asked it in comp.theory, but no satisfactory result came up. I remember the course TA insisted on something he couldn't prove, and said he forgot the proof, and ... [you know what].Today, I recalled the problem. I was still eager to know, so here it is...The QuestionIs it possible to implement a stack using two queues, so that both PUSH   and POP operations run in amortized time O(1)? If yes, could you tell   me how?Note: The situation is quite easy if we want to implement a queue with two stacks (with corresponding operations ENQUEUE & DEQUEUE). Please observe the difference.PS: The above problem is not the homework itself. The homework did not require any lower bounds; just an implementation and the running time analysis.
One Stack, Two Queues
ds.algorithms;ds.data structures;open problem;time complexity
I don't have an actual answer, but here's some evidence that the problem is open:It's not mentioned in Ming Li, Luc Longpr and Paul M. B. Vitnyi, The power of the queue, Structures 1986, which considers several other closely related simulationsIt's not mentioned in Martin Hhne, On the power of several queues, Theor. Comp. Sci. 1993, a follow-on paper.It's not mentioned in Holger Petersen, Stacks versus Deques, COCOON 2001.Burton Rosenberg, Fast nondeterministic recognition of context-free languages using two queues, Inform. Proc. Lett. 1998, gives an O(n log n) two-queue algorithm for recognizing any CFL using two queues. But a nondeterministic pushdown automaton can recognize CFLs in linear time. So if there were a simulation of a stack with two queues faster than O(log n) per operation, Rosenberg and his referees should have known about it.