Как отсортировать стек, используя только операции со стеком?

Question

Я нашел этот вопрос в Интернете.

Учитывая стек S, напишите программу на C для сортировки стека (в порядке возрастания).Нам не разрешается делать какие-либо предположения о том, как реализован стек.Используются только следующие функции:

Push
Pop
Top
IsEmpty
IsFull

Я думаю, мы можем построить кучу и отсортировать ее.Какое оптимальное решение для этого?

Answer 1

/* the basic idea is we go on
 *  popping one element (o) from the original stack (s) and we
 *  compare it with the new stack (temp)
 * if o (the popped element from original stack)
 *  is < the peek element from new stack temp
 * then we push the new stack element to original stack
 *  and recursively keep calling till temp is not empty
 *  and then push the element at the right place.
 * else we push the element to the new stack temp
 *  (o >= new temp stack.
 *
 * Entire logic is recursive.
 */

public void sortstk( Stack s )
{
    Stack<Integer> temp = new Stack<Integer>();

    while( !s.isEmpty() )
    {
        int s1 = (int) s.pop();

        while( !temp.isEmpty() && (temp.peek() > s1) )
        {
            s.push( temp.pop() );
        }
        temp.push( s1 );
    }

    // Print the entire sorted stack from temp stack
    for( int i = 0; i < temp.size(); i++ )
    {
        System.out.println( temp.elementAt( i ) );
    }
}

Answer 2

Вот решение в Javascript, основанное на ответе @ OrenD

var org = [4,67,2,9,5,11,3];
var helper = [];

while(org.length > 0){
    var temp = org.pop();
    while((helper.length > 0) && (helper[helper.length-1] < temp)){
        org.push(helper.pop());
    }
    helper.push(temp);
}

while(helper.length > 0){
    org.push(helper.pop());
}

Answer 3

Обратите внимание, что Неправильный ответ Майкла Дж. Барбера (см. Выше), который забывает отправить элемент обратно в стек, когда он пустПравильная версия выглядит следующим образом:

void sort(stack s) {
    if (!IsEmpty(s)) {
        int x = Pop(s);
        sort(s);
        insert(s, x);
    }
}

void insert(stack s, int x) {
    if (!IsEmpty(s)) {  
        int y = Top(s);
        if (x < y) {
            Pop(s);
            insert(s, x);
            Push(s, y);
        } else {
            Push(s, x);
        }
    } else {
        Push(s, x); // !!! must step, otherwise, the stack will eventually be empty after sorting !!!
    }
}

Answer 4

Если нет ограничений на использование других структур данных, я бы сказал, минимальная куча. всякий раз, когда извлекается элемент из стека, помещается в кучу. По окончании выталкивания берется элемент из верхней части кучи (минимум остальных) и помещается в стек. Повторять такой процесс, пока куча не опустеет.

Для создания кучи среднее время равно O (nlogn); для удаления элементов из кучи и возврата элементов в порядке возрастания среднее время также составляет O (nlogn).

Как это выглядит?

Answer 5

Если у вас нет никакой дополнительной информации о содержимом стека, то вы в значительной степени застряли, просто извлекая все данные, сортируя их и возвращая их обратно. Хепсорт здесь был бы хорош, как бы быстрая сортировка или интросорт. .