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

#c #sorting #stack

#c #сортировка #стек

Вопрос:

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

1. Зачем вам сортировать стек? Природа стека заключается в сохранении порядка LIFO. После сортировки это на самом деле больше не стек.

2. Что вы уже пробовали? Какие ошибки вы получаете? Чего ты не понимаешь? Это домашнее задание?

3. @Steve, конечно, это все равно был бы стек. Почему у вас не могло быть отсортированного стека?

4. @aioobe — стеки сортируются в порядке естественного перемещения элементов. Что угодно еще, и это на самом деле не стек.

5. Я думаю, вы могли бы сказать, что стек уже отсортирован… критерием сортировки является порядок размещения элементов в стеке. :/

Ответ №1:

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

Ответ №2:

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

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

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

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

 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) amp;amp; top(stack) < x) {
        y = pop(stack);
        insert(x, stack);
        push(y, stack);
    } else {
        push(x, stack);
    }
}

Ответ №3:

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

Ответ №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 amp;amp; !isEmpty(s2)){
                    b=top(s2); s2=pop(s2);
                    s1=push(b,s1);
            }

            s2=push(a,s2);

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

}//end of outer while

return s2;

}