58 views

Skip to first unread message

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?

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).

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?

> 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

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).

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.

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

to

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

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 ;)

could be O(1) ? So, it seems that the only thing I,m worried about is

runtime ;)

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) ?

>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

Search

Clear search

Close search

Google apps

Main menu