Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Building a queue with stacks

  1. Sep 13, 2008 #1
    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?
  2. jcsd
  3. Sep 14, 2008 #2


    User Avatar
    Homework Helper

    Would it be cheating to use a queue of stack pointers and use one stack per object?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook