Sorting a stack

I know how to sort an array but I haven't so开发者_Go百科rted a stack before. So please help. How can I sort a stack using the quicksort algorithm? Thank you.

---

What do you mean by "sorting a stack"? The whole idea of a stack is that it is in last-in, first-out (LIFO) order. Things that use stacks expect the most recent thing they put on the stack will be at the top of the stack with older things below it, ordered in reverse by when they were inserted because that's what stacks are. If you sort the stack you're going to break that.

---

I know how to sort an array but I haven't sort stack before.

The most efficient solution is probably to change the data structure to a list which allows random access and then sort the list. I.e., something like this:

1. Pop all elements of the stack into an array
2. Use the algorithm you do know and sort the array.
3. Push all elements back into the stack.

---

If you absolutely don't want to use a list, you'll perhaps find this solution interesting. (Stolen from here):

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);
    }
} 

---

What you can do is.. use recursion, recursively pop the elements in the stack and then find the best place to insert the current element. Let me know if you need the code, but then sorting a stack is totally unwarranted as mentioned in the earlier comments :) :)

---

I wrote this function to sort the stack using O(n) space. This works perfectly fine. I would appreciate any improvements in time. It's O(n*n) right now.

StackHead sortStack(StackHead s1){

StackHead s2=createStack();
Element a,b;

while(!isEmpty(s1)){

    a=top(s1);s1=pop(s1);
    if(isEmpty(s2) || top(s2) > a){
            s2=push(a,s2);
    } else {
            while(top(s2)<=a && !isEmpty(s2)){
                    b=top(s2); s2=pop(s2);
                    s1=push(b,s1);
            }

            s2=push(a,s2);

            while( (isEmpty(s2) || top(s1) < top(s2) ) && !isEmpty(s1)) {
                    b=top(s1); s1=pop(s1);
                    s2=push(b,s2);
            }
    }//end of else

}//end of outer while

return s2;

}