make any assumptions about how the stack is implemented. The following
are the only
functions that should be used to write this program:
Push | Pop | Top | IsEmpty | IsFull
Method 1: Recursion
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);
}
}
Method:2 Iterative use one more stack
void sort_stack(Stack * src, Stack * dest)
{
while (!src->IsEmpty())
{
Int tmp = src->Pop();
while(!dest->IsEmpty() && dest->Top() > tmp)
{
src->Push(dest->Pop());
}
dest->Push(tmp);
}
Methode 3:
ascending(stack *s, int top){
IsEmpty(s){
push(top);
return;
}
i = pop(s);
if(i .<. top){
ascending(s, top);
push(i);
}
else{
ascending(s, i);
push(top);
}
}
No comments:
Post a Comment