удалить повторяющиеся поля _stack & array

Question

Я хочу написать программу для реализации стека на основе массива, который принимает целые числа, введенные пользователем. Затем программа идентифицирует любые вхождения данного значения от пользователя и удаляет повторяющиеся значения из стека (используя Язык программирования Java).

Мне просто нужна ваша помощь в написании (метод удаления значений) например вход: 6 2 3 4 3 8 выход: 6 2 4 8

Answer 1

переопределяет метод push и запускает его через стек, чтобы определить, существует ли уже значение.если это так, верните false в противном случае true (если вы хотите использовать логическое возвращаемое значение).

в принципе, это в духе ответа, опубликованного г-ном Шнайдером, но зачем уменьшать массив или изменять стек ввсе, если вы можете просто определить, является ли новый элемент дубликатом или нет?если это дубликат, не добавляйте его, и массив не нужно изменять.я что-то упустил?

Answer 2

Предполагая, что логика «без дубликатов» является частью самого стека, я бы сделал следующее:

1) Реализуйте вспомогательный метод:

private boolean remove(int item)

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

2) Теперь легко реализовать метод push:

public void push(int item) {
    if (!remove(item)) {
        arr[topPos++] = item;
    }
}

Обратите внимание, что мое решение предполагает, что в массиве всегда достаточно места. Правильная реализация должна позаботиться об изменении размера массива при необходимости.

Answer 3

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

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

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

Если вы хотите выполнить это вне стека, используя только традиционные методы стекового интерфейса (push () и pop ()), ваш алгоритм может выглядеть примерно так:

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

Существуют и другие способы сделать это, но я полагаю, что всем потребуется некоторая вспомогательная структура данных, которая не является стеком.

Answer 4

Рассмотрим Collection.contains (возможно, вместе с Arrays.asList , если вам так не повезло), HashMap или Set .

Это действительно зависит от того, что у вас есть, куда вы действительно идете, и какие глупые ограничения накладывает домашняя работа / учитель.Поскольку вы говорите «реализовать стек на основе массива», я предполагаю, что есть несколько глупых мандатов, и в этом случае я бы рассмотрел написание пользовательского arrayContains вспомогательного * метода и / или использование вторичной структуры данных (Hash / Set) для сохранениядорожка «увиденного».

Если вы выполняете проверку при вставке, это просто (метакод, это ваша домашняя работа: -):

function addItem (i) begin
   if not contains(stack, i) then
      push(stack, i)
   end if
end

* Вы можете использовать приведенный выше asList /содержит, если вы не возражаете против того, чтобы быть «не очень эффективным», но Java поставляется с очень небольшой хорошей поддержкой массивов и, следовательно, рекомендацией для помощника, который, в свою очередь, представляет собой просто цикл над массивом, возвращающий значение true, если значение найдено, falseиначе.(Или, возможно, верните найденный индекс или -1 ... ваш код: -)