Archive

Posts Tagged ‘Stack’

Implement Queue with a single Stack

October 24, 2011 5 comments

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! 🙂

Reverse a stack without using any other data structures. (in-place)

This was a question that was asked to one of my friends in Microsoft’s IDC interview. No other data structures, eh? And I am pretty sure that  I would need all the values to reverse the stack. So there is only one way to this. Solve the problem using recursion!

But how? How do you utilize recursion to do this? Here is how you should proceed. Recurse down to the second last element in the stack and call a function with the stack as it is right now (with only 1 element) and the current element (the second last one). Now go on to pop an element. Then you should do one of the two things. If the size is not equal to zero, call this function again with the element you received from the function (2nd last). If the size is zero, just push the element you received from the call onto the stack.

So you are basically inserting each element in reverse order utilizing 2 functions. Here is a small pseudo-code:

void reverse(Stack s) //called at the start
{
int num = (int)s.Pop();
if (s.Count != 1)
reverse(s);
Push(s , num);
}
void Push(Stack s , int a)
{
int num = (int)s.Pop();
if (s.Count != 0)
Push(s , a);
else
s.Push(a);
s.Push(num);
}

You got it, right? If not, try running this for a basic input stack with values 1,2,3,4,5 (bottom -> top). You’ll certainly get it then. 🙂

%d bloggers like this: