Удалить дублирующий элемент из стека

Предположим, что у меня есть стек, а его элементы - [1,2,3,3,2,1,1,5,5,4,5]. Верхний указатель стека указывает на элемент 1. Теперь i хотите удалить все повторяющиеся элементы, поэтому мой последний стек будет [1,2,3,4,5]. Как я могу это сделать, есть ли какой-либо алгоритм для этой операции. Какое минимальное количество стеков требуется для этой операции.Удалить дублирующий элемент из стека

источник

2013-09-20 Rajat Shukla

Будучи пуристом, реальный стек, являющийся FILO, не позволит вам заглянуть в то, что находится в стеке, чтобы его удалить. Возможно, более простая реализация заключалась бы в том, чтобы сохранить список обработанных файлов, чтобы вы могли игнорировать элемент, когда вы его всплываете, если он уже обработан. Я делаю этот комментарий без каких-либо реальных знаний о том, чего вы пытаетесь достичь. – Bronumski

Есть ли причина, по которой вы не можете проверить наличие дубликатов при использовании стека? Каждый раз, когда вы выталкиваете значение, проверяйте список используемых значений. Если он существует в используемом списке, нажмите снова, пока вы не нажмете определенное значение. Добавьте отдельное значение в список. – tfitzger

Ну, у не указан какой-либо язык, поэтому я постараюсь дать некоторые шаги, чтобы сделать эту операцию на какой-то псевдо-языке:

Stack FunctionName(Stack paramStack) 
{ 
    Stack aux1 = param; 
    Stack aux2; 
    while (aux1.size() > 0) 
    { 
     StackElement eleAux = aux1.pop(); 
     if (NotExist(aux2,eleAux)) 
     { 
     aux2.push(eleAux); 
     } 
    } 
    while (aux2.size() > 0) 
    { 
     StackElement eleAux = aux2.pop(); 
     aux1.push(eleAux); 
    } 
    }

Supose Стек представляет собой структуру данных стека (извините за redundacy), а StackElement представляет собой элемент стека. Функции «NotExist» проверяют только, существует ли какой-либо элемент в некотором стеке.

Надеюсь, что это поможет. ^^

источник

2013-09-20 11:09:26 Cold

Просьба указать указанный выше псевдокод на языке C или Python. –

Вы можете преобразовать это на нужный язык. Если u использует C, я полагаю, что вы используете массив для представления scripts данных для стека. Я не знаю Фитона. – Cold

Ответ @ColdHack отправляет второй стек на каждый элемент из первого стека, который может быть дорогостоящим при больших размерах стека. Первое, что пришло мне в голову, это использовать хэш-карту и поп каждое значение из стека искать ее на карте - если она уже там ничего не делает, если не положить ее и установить ключ в хэш-карте на значение из стек и значение в хэш-карте для индекса в стеке, а затем, когда сделано, сортируйте хэш-карту по значениям и просто поместите ее в стек. Если идея не ясна, я могу попытаться опубликовать некоторый общий код.

источник

2013-09-20 11:25:25

Удалить дублирующий элемент из стека

ответ

Смежные вопросы