Алгоритм сортировки стека на месте
Какие алгоритмы сортировки были бы хороши для сортировки стека для экономии пространства? Мне нужно отсортировать стопку "на месте". Кроме того, мое понимание алгоритмов "на месте" заключалось в том, что они не используют никаких дополнительных структур данных - это правильно?
Я знаю, что это похоже на этот вопрос, но мне интересно, будет ли это иначе для стеков? Я знаю, что стеки могут быть просто типом связного списка, но разве тот факт, что вы можете получить доступ только к вершине, изменится, как вы это сделаете?
2 ответа
Вам придется пропустить квалификатор "на месте", если вы хотите отсортировать стек, используя только операции стека (вам потребуется другой стек). Алгоритм на месте - это алгоритм, который преобразует входные данные без использования других структур данных. Однако для промежуточных / временных переменных допускается небольшой объем дополнительного пространства для хранения.
Если вы пропустите квалификатор "на месте", вы можете найти ответ здесь: Как отсортировать стек, используя только операции стека? (сортирует стек, используя дополнительный вспомогательный стек)
Если вы сохраняете квалификатор, то сортировка стека возможна только на уровне реализации, а не с использованием операций стека.
Есть альтернативное определение для сортировки на месте, которое просто означает, что отсортированные данные заканчиваются в том же контейнере (в данном случае в стеке), в котором изначально были сохранены несортированные данные.
Возвращаясь к первоначальному вопросу, единственный способ получить доступ и / или изменить последний элемент стека - это вытолкнуть все остальные элементы, для чего требуется O(n-1) место в другом месте, самым простым из которых является массив.
Если стек реализован как связанный список, можно использовать сортировку по типу связанного списка, но это будет сортировка, ориентированная на список, с использованием операций, отличных от стандартных операций стека peek, pop и push.