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*

6
  • $\begingroup$ I edited the first paragraphs so my answer is formulated as an actual answer to the question. $\endgroup$ Commented Oct 31, 2010 at 1:41
  • 6
    $\begingroup$ You are using an array (reverser) for reversing! I don't think you are allowed to do this. $\endgroup$ Commented Oct 31, 2010 at 8:51
  • $\begingroup$ True, I use extra space while executing the methods, but I thought that would be allowed: if you want to implement a queue using two stacks in the straightforward way, you have to reverse one of the stacks at one point, and as far as I know you need extra space to do that, so since this question is similar I figured using extra space during the execution of a method would be allowed, as long as you don't use additional space between method calls. $\endgroup$ Commented Oct 31, 2010 at 12:48
  • 6
    $\begingroup$ "if you want to implement a queue using two stacks in the straightforward way, you have to reverse one of the stacks at one point, and as far as I know you need extra space to do that" --- You don't. There's a way to get the amortized cost of Enqueue to be 3 and the amortized cost of Dequeue to be 1 (ie both O(1)) with one memory cell and two stacks. The hard part is really the proof, not the design of the algorithm. $\endgroup$ Commented Oct 31, 2010 at 13:30
  • $\begingroup$ After thinking about it some more, I realise I am indeed cheating and my previous comment is indeed wrong. I've found a way to rectify it: I thought up two algorithms with the same running times as the above two (though Push is now the operation taking long and Pop is now done in constant time) without using extra space at all. I'll post a new answer once I've written all of it down. $\endgroup$ Commented Oct 31, 2010 at 14:01