Сортировка стека в порядке возрастания?

Question

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

Есть два метода, о которых я могу подумать.

1. Чтобы вытолкнуть все содержимое стека и сохранить его в массиве, а затем отсортировать массив в
   O(nLog n) и затем поместите содержимое обратно в стек. Не лучший способ ....

2. Выполнить рекурсивную реализацию стека для его сортировки

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

Но второй метод, кажется, выполняет слишком много рекурсивных вызовов, и издержки будут проблемой, если стек окажется действительно большим.

Можно ли решить эту проблему гораздо лучшим образом для лучшей пространственно-временной сложности?

Существует так много рекурсивных вызовов (перекрывающихся подзадач), это претендент на dynamic programming тип проблем?

Как лучше всего это решить?

Answer 1

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

Например, псевдокод:

Linekd Stack stack = new List ();

while stack is not empty then

     element <- stack removes peek

     / / Recursiong
     push new elements on stack

end

Answer 2

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

Если операции со стеком стоят дорого, но у вас есть крайний срок, используйте сортировку вставкой, когда вы пишете, и вы можете нажать, как только ваш последний щелчок будет сделан.Но вы говорите, что это на C ++, поэтому я сомневаюсь, что мы рассматриваем такой сценарий.

Answer 3

Эта проблема не может иметь сложности меньше, чем O (n ^ 2).Для получения дополнительной информации см. здесь