Home > Applied Algorithms, Queue, Recursion, Stack > Implement Queue with a single Stack

Implement Queue with a single Stack

This is a very common problem that most of you might have even figured out. But I know a few who wouldn’t know how to do it. What would you have done if you could have used 2 stacks? You would have been manipulating the two, popping and pushing elements between the two to just make them work like a queue. Basically, you would have been using double the required space.

With 1 stack, the only way (as you might have figured out) is to use recursion. Once this concept comes to mind, things become sweet and simple. For Enqueuing, you just need to PUSH an element onto the stack. So that is no hassle. For Dequeuing, what you need to do is recurse to the bottom of the stack by POP-ing elements (which is somewhat similar to how we used to tackle tree-related problems with recursion) and then print the last element. You again PUSH the rest of the elements on to the stack while coming bottom->up. 

Here is a pseudo code for both the functions :

void ENQUEUE ( element )

{

stacky_queue.PUSH (element) //stacky_queue is basically my stack

}

bool DEQUE ()

{

If ( NOT stacky_queue.EMPTY())

{

popped_element = stacky_queue.POP()

IF ( NOT DEQUE() )

{

PRINT popped_element

}

ELSE

{

stacky_queue.PUSH(popped_element)

}

return true

}

return false

}

Cool, eh? Hope you got it! If not read the paragraph in italics once more and you certainly will understand it then! 🙂

Advertisements
  1. Glen
    October 25, 2011 at 11:56 am

    that was pretty simple but what about its time complexity ???
    i mean that this is too much time consuming process .

    • October 25, 2011 at 12:08 pm

      For every ENQUE, it is O(1), for every DEQUE it is O(n). It is the best solution I could come up with. Do tell me if you figure out a better way to solve this. 🙂

  2. anon
    October 29, 2011 at 8:24 pm

    @blogger You are using stack provided by the system. so it is still two stacks.
    @Glen in these scenarios you may be interested in amortized complexity which is O(1) for both.

    • October 29, 2011 at 9:23 pm

      Very true buddy. Recursion does use system stack. But I am sure the interviewer wanted you to give this particular answer when he mentioned “using 1 stack”. 🙂

  3. anon
    October 29, 2011 at 8:24 pm

    @allaboutal You are using stack provided by the system. so it is still two stacks.
    @Glen in these scenarios you may be interested in amortized complexity which is O(1) for both push and pop.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: