CareerCup

Sorting can be performed with one more stack. The idea is to pull an item from the original stack and push it on the other stack. If pushing this item would violate the sort order of the new stack, we need to remove enough items from it so that it’s possible to push the new item. Since the items we removed are on the original stack, we’re back where we started. The algorithm is O(N^2) and appears below.

public static Stack<Integer> sort(Stack<Integer> s) {
Stack<Integer> r = new Stack<Integer>();
while(!s.isEmpty()) {
int tmp = s.pop();
while(!r.isEmpty() && r.peek() > tmp) {
s.push(r.pop());
}
r.push(tmp);
}
return r;
}

What is the run time and memory requirement?
If there are no requirements, you can just put in an array. Sort it using your favorite N Log N algorithm and push it back on the stack.

Except that you don't know how many items are in the stack so you can't create an array.

I recommend heap sort and push it back to the stack

You'll need two stacks for this. The sorting method used is bubble sort. Pop from stack1 and push in stack2. compare top of stack1 & top of stack2. then push accordingly.

#include<iostream>
using namespace std;

struct node
{
int data;
node *next;

node()
{
next=NULL;
}

node(int x)
{
data=x;
next=NULL;
}
// ~node()
// {
// delete next[];
// }

};

struct stack
{
node *head;

stack()
{
head=NULL;
}

void push(int x)
{
node *n=new node(x);

if(head==NULL)
{
head=n;
}
else
{

n->next=head;
head=n;

}

}

int pop()
{
node *temp=head;
if(head->next!=NULL)
head=head->next;
else
head=NULL;
return temp->data;
}

bool IsEmpty()
{
if(head==NULL)
return true;
else
return false;
}
int top()
{
if(head!=NULL)
{
return head->data;
}

}
void print()
{
node *temp=head;

while(temp!=NULL)
{
cout<<temp->data<<" ";
temp=temp->next;
}
cout<<endl;
}


};

void sort_stack(stack &s)
{
stack A,B;

while(!s.IsEmpty())
{
int tmp=s.pop();

if(A.IsEmpty())
{
A.push(tmp);
continue;
}

if(A.top()<tmp)
{
int mark=0;
while(!A.IsEmpty() && A.top() <tmp)
{
mark=1;
B.push(A.pop());
}
if(mark==1)
{
mark=0;
A.push(tmp);
}

while(!B.IsEmpty())
{
A.push(B.pop());
}
}
else
{
A.push(tmp);
}


}

while(!A.IsEmpty())
{
s.push(A.pop());
}



}

void main()
{
stack s;

s.push(15);
s.push(9);
s.push(2);
s.push(7);
s.push(3);
s.push(11);

s.print();

sort_stack(s);

s.print();

}

Just think about Hanoi Tower. Essentially the same problem.

/*
Logic: use two stacks, orig_stack and new_stack    
    // pop from orig_stack
    // current = popped element from orig_stack
    // check if new_stack top element must be smaller than current
    // if not pop element from new_stack, push into orig_stack
    // pop element into orig_stack till current not get greater then top value of new stack
    // now put current into new_stack , and again follow steps above

*/
#include<stdio.h>
#include<stdlib.h>

#define MAX 5

typedef struct stack_arr
{
    int arr[MAX];
    int top;
}stack;

stack s;
stack u_s;

void push(stack *s,int val)
{

    if(s->top == MAX-1)
        printf("Stack is full\n");
    else
    {
        s->top = s->top+1;
        s->arr[s->top] = val;
    }
}

int pop(stack *s)
{

    int num;
    if(s->top == -1)
        printf("Stack is empty\n");
    else
    {
        num = s->arr[s->top];
        printf("Popped element : %d\n",num);
        s->top = s->top -1;
    }
    return num;
}
void sort_stack(stack *s, stack *new_s)
{
    int curr,temp,flag =0;
    // pop from orignal stack
    // current = popped element from orig stack
    // check if new_stack top element must be smaller than current
    // if not pop element from new_stack, push into orig_stack
    // pop element into orig stack till current not get greate then top value of new stack
    // now put current into new_stack , and again follow steps above

    while(new_s->top != MAX-1)
    {
        curr = pop(s);

        if(new_s->top == -1)
            push(new_s,curr);
        else if(curr > new_s->arr[new_s->top])
            push(new_s,curr);
        else
        {
            while(curr < new_s->arr[new_s->top] && new_s->top != -1)
            {
                temp = pop(new_s);
                push(s,temp);
                flag=1;
            }
            if(flag == 1)
            {
                push(new_s,curr);
                flag = 0;
            }
        }
    }

}
void display(stack *s)
{
    int i;
    if(s->top == -1)
        printf("Stack is empty\n");
    for(i=0;i<=s->top;i++)
    {
        printf("%d ",s->arr[i]);
    }
    printf("\n");
}

int main()
{
int temp;

s.top = -1;
u_s.top=-1;

push(&s,8);
push(&s,2);
push(&s,1);
push(&s,5);
push(&s,4);

display(&s);
sort_stack(&s,&u_s);
display(&u_s);

return 0;
}

plxrciyoa ybksxlvu gyterinbp blothsv gmpr vfaeljiz uqgd