CareerCup

Please post the questions correctly, i dont think it is possible

Questions:

1) Do you have access to the underlying data structure IE list etc?
2) Are you able to create and use new pointers?

I am not able to understnd your questions.The only thing that can be done is you can reverse the stack.Nothing else is to be used.

I assume that we have only push, pop, top, empty , full methods. Without creating a temporary storage for elements in stack one can't sort the stack. So I don't think in place stack sorting is feasible.

This is the trick here...there is a new functionlaity given for stack in which you can reverse the numbers for sorting.In sorting we just take 2 numbers are swap whereas here the list has to be revered and sorted

// The main logic is to push the lowest element to the bottom of the stack, now this is done by comparing the topmost 2 values, do this recursively !

Sort(stack) {
a = stack.pop()
b = stack.pop()
if( a == null) return;
if (b == null ) return;

if(a < b){
stack.push(a)
stack.push(b)
}

else{
stack.push(b)
sort(stack)

stack.push(a)
sort(stack)
}
}

// trace the algo to better understand

Idea is correct but I think problem asks you to give in place solution. This is not in place.

What are we trying to achieve here? If we sort the stack, its no more one...LIFO goes away
....or I am missing something?

Could anyone tell me the real world example where a stack need to be sorted? Someone asked me this during the interview.

#include<stdio.h>
#include<stddef.h>
#include<stdlib.h>
struct stack
{
int capacity;
int top;
int *array;

}*s=NULL;

void createstack(int size)
{
s=(struct stack*)malloc(sizeof(struct stack));
s->array=(int*)malloc(sizeof(int)*size);
s->top=-1;
s->capacity=size;
printf("\n ** array created succ!!\n");
}

int check(int data)
{
printf("\n inside check");
int temp;
if(s->top==-1)
{
s->array[++s->top]=data;
return ;
}
if(s->array[s->top] <data)
{
s->array[++s->top]=data;
return ;
}
if(s->array[s->top] >data)
{
temp=s->array[s->top--];
printf("temp -->> %d",temp);
check(data);
//push(temp);
s->array[++s->top]=temp;
}
}

int sort()
{
printf("\n inside sort");
int data;
if(s->top==-1)
return ;
else
{
data=s->array[s->top--];
printf("data -->> %d",data);
sort();
check(data);
}
}

void main()
{
int size , no , i;
printf("entre the size of array");
scanf("%d",&size);
createstack(size);
for(i=0;i<size;i++)
{
scanf("%d",&no);
s->array[++s->top]=no;
}
printf("\nvalue of top %d",s->top);
sort();
for(i=0;i<s->capacity;i++)
printf("\n%d",s->array[s->top--]);
}