Разбор стека. Удаление повторов

Рейтинг: 2Ответов: 2Опубликовано: 16.04.2015

Подскажите пожалуйста, как имея стек (самописный) получить из него новый, без повторяющихся элементов? Можно использовать, естественно, вспомогательные стеки. На ум приходит только модификация ханойской башни и всё.

алгоритм коллекции
Источник: Stack Overflow на русском

Ответы

▲ 2Принят
  1. Заводите множество (самописное или нет, как хотите).
  2. Перекладываете данные в новый стек, занося их ещё и во множество. Если данное уже есть во множестве, в новый стек не кладёте.
  3. Разбираете новый стек, перекладывая данные в исходный стек, таким образом вы их снова разворачиваете.

В случае, когда дополнительными структурами данных (кроме одного дополнительного стека) пользоваться нельзя, подойдёт следующая идея. Назовём просмотром с удалением такую операцию:

  1. Элементы перекладываются из 1-го стека во второй
  2. Если по пути встречается удаляемый элемент (начиная с некоторого места), он не кладётся во второй стек
  3. Данные перекладываются назад

Тогда делаем так: проводим просмотр с удалением элементов после 1-го, равных этому самому первому. Затем то же для второго элемента и т. д., до конца стека. Это медленно, но ведёт к цели, т. к. после i-ого просмотра первые i элементов стека уникальны.

▲ 1

  1. Если одинаковые элементы в стеке лежат рядом, то задача решается элементарно

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