CareerCup

Are we allowed to instantiate one more stack ?
If yes, the problem is straightforward.

OrigStack = { 2, 6, 5, 1, 3}
NewStack = {NULL};

//Assume OrgiStack has atleast one element
NewStack.push(OrigStack.pop());

while(!OrigStack.isEmpty())
{
val = OrigStack.pop();
while(NewStack.top() < val) {
OrigStack.push(NewStack.top());
}
NewStack.push(val);
}

OrigStack = NewStack; //Done

Let me know suggestions. This the first trivial algo i can think about at the moment.

To do this recursively we need to do the following:

1) Remove the top item
2) Reverse the remaining stack
3) Put the top item we removed at the bottom of the stack

2) Is a recursive call. Also, since we have no way of directly putting an item at the bottom of a stack, we can implement 3) recursively as well. The following would work:

import java.util.Stack;


public class StackReverse
{
    public void reverse(Stack stack)
    {
        if (!stack.isEmpty())
        {
            Object top = stack.pop();
            reverse(stack);
            moveItemToBottom(stack, top);
        }
    }


    private void moveItemToBottom(Stack stack, Object bottomItem)
    {
        if (stack.isEmpty())
        {
            stack.push(bottomItem);
        }
        else
        {
            Object o = stack.pop();
            moveItemToBottom(stack, bottomItem);
            stack.push(o);
        }
    }
}

Oops, that was for the reverse a stack in place question. Posted it to the wrong thread.

@ posix4e . Your code looks correct apart from newStack.Top() in the inner while loop should be newStack.Pop(); . Please let me know if I am wrong.

void sort(stack)
{
type x;

if (!isEmpty(stack)) {
x = pop(stack);
sort(stack);
insert(x, stack);
}
}

void insert(x, stack)
{
type y;

if (!isEmpty(stack) && top(stack) < x) {
y = pop(stack);
insert(x, stack);
push(y, stack);
} else {
push(x, stack);
}
}

@Sucharit ... newstack.top() will just get the reference value of the top node.it wont pop/remove the top node. To remove the top node we use the pop().In this case to compare it with "val",we dont need to pop the top node.

This is tower of hanoi problem

using two stacks

void SortStack(stack<int>& stk)
{
	int elem;
	stack<int> secStk;

	if(stk.empty())
		return;

	secStk.push(stk.top());
	stk.pop();
	while(!stk.empty())
	{
		elem = stk.top();
		stk.pop();
		if(elem >= secStk.top())
		{
			secStk.push(elem);
		}
		else
		{
			int data;
			while(!secStk.empty() && secStk.top() > elem)
			{
				data = secStk.top();
				secStk.pop();
				stk.push(data);
			}
			secStk.push(elem);
		}
	}

	while(!secStk.empty())
	{
		stk.push(secStk.top());
		secStk.pop();
	}
}

try recursive insersion sort, u need not 2 use an other stack...

void sort(stack s) {
    if (!IsEmpty(s)) {
        int x = Pop(s);
        sort(s);
        insert(s, x);
    }
}

void insert(stack s, int x) {
    if (!IsEmpty(s)) {  
        int y = Top(s);
        if (x < y) {
            Pop(s);
            insert(s, x);
            Push(s, y);
        } else {
            Push(s, x);
        }
    }
}

chutiyapa ...