Can You Improve the Time Complexity of Building a Queue with Stacks?

[Shackman]

Hello, I'm tasked with building a queue from as many stacks as I'd like, trying to get the fastest implementation possible. The best I can think of is using two stacks and as you enqueue items you push them on the first stack stack, but every time you want to dequeue if there are n items enqueue'd you have to pop each one individually and push them onto the second stack for n-1 times, then pop the first item enqueue'd and return it. Then any dequeue is easy..simply popping off the second stack because the order is reversed. If you want to enqueue again though, you'd have to do the reverse and pop each item off the second and push it back onto the first another n-1 times. So it looks like worst case it is O(n^2). Can anyone think of something better or help me improve this?

 

[rcgldr]

Would it be cheating to use a queue of stack pointers and use one stack per object?