PS: I found out a solution for this, but the amortized runtime of PUSH
is O(n).
If this is homework, we don't do that here. Just be sure you
read the problem correctly. A popular exercise is implementing a
queue using two stacks [and only O(1) storage outside the stacks]
with operations in O(1) amortized time.
--
--Bryan
But the problem is, if it's possible to implement a stack with two
queues with amortized operation cost O(1).
I believe that it's impossible. But I want to know other's opinion.
PS: Regarding the homework issue: that's in fact NOT a homework. The
homework is, just to show an implementation, and the amortized cost is
not important in my homework. I solved this easily. This question is
just my little curiosity about if there's a better implementation.
Note: one queue suffices if you're not worried about running time.
I can't see how. You might be able to do it with O(lg n) queues and
amortized time O(lg n) per operation, if you're lucky, but I can't begin
to imagine how one would beat that.
Here is an easier special case: suppose we have n PUSHes followed by n
POPs (which corresponds to reversing an input word of length n). Then
we can store the first n/2 symbols into one queue, the next n/4 symbols
into the 2nd queue, the next n/8 into the 3rd queue, and so on. When you
get to the last symbol, it will be in a queue of length one, and you just
output it. Then you recursively apply the same procedure to reverse each
queue, starting with smaller queues and working towards larger ones. You
end up using 2 lg n queues and O(lg n) queue-operations per stack-op.
Perhaps this idea can be generalized to support any sequence of stack
operations. It seems like it might be possible, but I haven't tried
to work out the details, as the result doesn't seem very interesting
or useful.