## Amazon Interview Question

Software Engineer / Developers**Country:**-

Similar implementation in C++

CustomStack CustomStack::RecursiveReverse(CustomStack inputStack)

{

CustomStack tmpStack(_size);

int value;

//Base condition

//Vector of size 1 is by itself reversed

if(inputStack._Stack.size() == 1)

return inputStack;

//Pop the last item from the stack

value = inputStack.Pop();

//Recursive function call

tmpStack._Stack = RecursiveReverse(inputStack)._Stack;

//Insert the popped into the first position

tmpStack.RecursiveInsert(value);

return tmpStack;

}

int CustomStack::RecursiveInsert(int value)

{

if(this->_Stack.size() == 0)

{

this->Push(value);

}

else

{

int tmp = this->Pop();

this->RecursiveInsert(value);

this->Push(tmp);

}

return 0;

}

Reversing the stack is similar to reversing the singly linked list..

```
void ReverseStack(struct stack *oldtop,struct stack **newtop)
{
if(oldtop->next==NULL)
*newtop=oldtop;
else {
ReverseStack(oldtop->next,newtop);
oldtop->link->link=oldtop;
oldtop->link=NULL;
}
}
```

void ReverseStackRecursive(stack<int>* s)

{

if(!s || s->size() == 1) return;

for(int i = 0; i < s->size() ; i ++)

{

int head = s->top();

s->pop();

ReverseStackRecursiveAux(s, head, i); //insert the current head at position i from the bottom

}

}

void ReverseStackRecursiveAux(stack<int>* s, int value, int index)

{

if(s->size() == index)

{

s->push(value);

return;

}

int current = s->top();

s->pop();

ReverseStackRecursiveAux(s, value, index);

s->push(current);

}

Complexity will be O(n*n). We have to reverse element by element. Kindly suggest if you know a way to do this with lesser complexity.

```
public static void main(String[] args){
for(int i=1;i<stackSize;i++){
Object obj = reversestack(stack,i,0);
stack.push(obj);
}
}
public Object reverseStack(Stack stack, int toBeReversed, int current){
Object obj = stack.pop();
if(current == toBeReversed){
return obj;
}else{
Object obj2 = reverseStack(stack, toBeReversed, current+1);
stack.push(obj);
return obj2;
}
}
```

<pre lang="" line="1" title="CodeMonkey62146" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));

String s;

while (!(s=r.readLine()).startsWith("42")) System.out.println(s);

}

}

class ReverseStack {

// a simple recursive method that pops from the bottom of the stack

// and push that number

public void reverse(Stack<Integer> stack) {

if (stack.isEmpty())

return;

int bottom = popFromBottom(stack);

reverse(stack);

stack.push(bottom);

}

// recursive method that gets the number in the bottom of the stack

private Integer popFromBottom(Stack<Integer> stack) {

Integer oldValue = stack.pop();

// if the stack is empty after a pop operation, we know that

// we just got the number in the bottom of the stack and we can

// return this value

if (stack.isEmpty()) {

return oldValue;

}

// if this is not the number in the bottom of the stack, then keep going

Integer value = popFromBottom(stack);

// we need to put everything back into the stack except the number int he bottom

stack.push(oldValue);

return value;

}

}</pre><pre title="CodeMonkey62146" input="yes">

</pre>

static void Reverse(struct node** headRef) {

struct node* result = NULL;

struct node* current = *headRef;

struct node* next;

while (current != NULL) {

next = current->next; // tricky: note the next node

current->next = result; // move the node onto the result

result = current;

current = next;

}

*headRef = result;

}

public static void revertStack(Stack<Integer> s)

- Anonymous October 24, 2011{

if (s.isEmpty()) {

return;

} else {

Integer a = s.pop();

revertStack(s);

appendStack(s, a);

}

}

public static void appendStack(Stack<Integer> s, Integer a)

{

if (s.isEmpty()) {

s.push(a);

return;

} else {

Integer o = s.pop();

appendStack(s, a);

s.push(o);

}

}