One Stack, Two Queues

background Several 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 Question Is 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.