One stack, two queues

58 views
Skip to first unread message

Sadeq

unread,
Mar 26, 2006, 5:49:42 AM3/26/06
to
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?

PS: I found out a solution for this, but the amortized runtime of PUSH
is O(n).

Bryan Olson

unread,
Mar 26, 2006, 7:24:46 PM3/26/06
to
Sadeq wrote:
> 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?

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

Sadeq

unread,
Mar 27, 2006, 5:47:19 AM3/27/06
to
Yes. It's very easy to show how to implement a queue with two stacks
with amortized operation cost O(1).

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.

Googmeister

unread,
Mar 27, 2006, 7:20:41 AM3/27/06
to

Note: one queue suffices if you're not worried about running time.

Sadeq

unread,
Mar 27, 2006, 9:54:09 AM3/27/06
to
Yes, but that's the point: I just want to see if amortized runtime
could be O(1) ? So, it seems that the only thing I,m worried about is
runtime ;)

David Wagner

unread,
Mar 27, 2006, 4:17:36 PM3/27/06
to
Sadeq wrote:
>Is it possible to implement a stack using two queues, so that both PUSH
>and POP operations run in amortized time O(1) ?

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.

Reply all
Reply to author
Forward
0 new messages