Skip to main content
Theoretical Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

5
  • 2
    $\begingroup$ I guess that you can only use a limited amount of space other than the two queues (O(1) or O(log n)). Sounds impossible to me, because we do not have any way to reverse the order of a long input stream. But of course this is no proof unless it can be made into a rigorous claim…. $\endgroup$ Commented Oct 30, 2010 at 12:32
  • $\begingroup$ @Tsuyoshi: You're right about the limited space assumption. And yes, that was what I said to that (stubborn) TA, but he refused :( $\endgroup$ Commented Oct 30, 2010 at 13:22
  • 2
    $\begingroup$ @Tsuyoshi: I don't think you need to assume a bound on space in general, you only need to assume that you are not allowed to store the objects pushed and poped from the stack in any place other than the two queues (and probably a constant number of variables). $\endgroup$ Commented Oct 31, 2010 at 8:58
  • $\begingroup$ @SadeqDousti In my opinion, the only way this would be possible is if you used a linked-list implementation of a queue and used some pointers to always point to the top of the "stack" $\endgroup$ Commented Oct 16, 2013 at 0:23
  • 2
    $\begingroup$ It sounds like the TA might have actually have wanted to say "Implement a queue using two stacks" which is indeed possible precisely in "O(1) amortized time". $\endgroup$ Commented Nov 15, 2013 at 14:45