CareerCup

Since we're using recursion - aren't we already using another stack ?
hence making this a two stack problem ;)

May be implemented using recursion.

yes, seems using the recursion and processing from the last element of the stack is the suitable approach for this scenario.Any other optimal technique ?

Assuming stack is represented using a linked list and the telephone numbers are stored as integer. Data would hold the next telephone number when the function returns. I am using recursion to do to the last element and saving it in the data and then pushing back all the rest.

void dequeue(Stack* s, int* data) {
  int r = pop(&s); //Remove from head, head will be modified to head->next, so passing &s
  if(s == NULL) { // We have reached the end of the list and r contains the first element entered in the stack
    *data = r;
    return;
  }
  else {
    dequeue(s, data);
    push(&s, r);
  }
}

This code should work but I think its very inefficient. The problem is that we are returning just one telephone number each call, so O(n) per retrieval. If the user wants to process all the telephone numbers present in the stack, we could have returned all the telephone numbers in a FIFO fashion but the restriction of no extra memory allocation is allowed keeps me from doing that.

{
top = index;
for(index = 0; index<=top; index++)
{
num = pop();
push(num+100); // update
printf("\t %d ", stack[index] );
}
}

public int ProcessStack(ref Stack<int> stck, int val)
{
if (val == 0)
return val;

int newVal = ProcessStack(ref stck, stck.Pop());
if (newVal != 0)
{
stck.Push(val);
return newVal;
}

return val;
}

Following is the code using recursion in Java, which does the job. I have used the built-in Stack (java.util) Data structure. But this should work with any other Stack implementation. Following is the code:

To test this you could write a main progam which initializes the stack & calls this method:

Main code snippet:
Stack<Integer> stack = new Stack<Integer>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);

System.out.println(pop(stack));

Recursive function:

private static Integer pop(Stack<Integer> stack) {
Integer temp = null, temp1 = null;

if(stack.size() == 1) {
temp = stack.pop();
} else {
temp1 = stack.pop();
temp = pop(stack);
stack.push(temp1);
}

return temp;
}

If your stack is linked list, just reverse the list. Pop and reverse again. You can reverse list using O(1) space