Сортировка стека

Question

Я знаю, как сортировать массив, но я не сортировал стек раньше.Поэтому, пожалуйста, помогите.Как я могу отсортировать стек, используя алгоритм быстрой сортировки?Спасибо.

Answer 1

Что вы подразумеваете под "сортировкой стека"? Вся идея стека заключается в том, что он находится в порядке поступления (LIFO). Вещи, использующие стеки, ожидают, что самое последнее, что они положили в стек, будет наверху стека, а более старые вещи будут располагаться под ним в обратном порядке, когда они были вставлены, потому что это то, что стеки равны . Если вы сортируете стек, вы сломаете его.

Answer 2

Я знаю, как сортировать массив, но я не сортировал стек раньше.

Наиболее эффективным решением, вероятно, являетсяизмените структуру данных на список, который обеспечивает произвольный доступ, а затем отсортируйте список.То есть что-то вроде этого:

1. Поместить все элементы стека в массив
2. Использовать алгоритм, который вы do знаете, и отсортировать массив.
3. Вставьте все элементы обратно в стек.

---

Если вы абсолютно не хотите использовать список, вы, возможно, найдете это решение интересным.(Украдено у здесь ):

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

Answer 3

Что вы можете сделать, это ... использовать рекурсию, рекурсивно вытолкнуть элементы из стека и найти лучшее место для вставки текущего элементаДайте мне знать, если вам нужен код, но сортировка стека совершенно неоправданна, как упоминалось в предыдущих комментариях

Answer 4

Я написал эту функцию для сортировки стека, используя пространство O (n).Это прекрасно работает.Буду признателен за любые улучшения во времени.Это O (n * n) прямо сейчас.

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;

}