Как реализовать стек, который хранит только уникальные значения в Java - PullRequest
Новая
       77

Как реализовать стек, который хранит только уникальные значения в Java

0 голосов
/ 05 февраля 2020

Я пытаюсь реализовать уникальный стек. Если я попытаюсь расширить класс стека и использовать содержимое, он будет выглядеть как весь стек, а сложность по времени станет O (n). Поэтому я попытался расширить LinkedHashSet, который удалит дубликаты сам и поддерживает порядок. Я могу реализовать все методы, кроме pop.

Кто-нибудь может поделиться своими мыслями здесь? 

import java.util.Collection;
import java.util.LinkedHashSet;
import java.util.Stack;
import java.util.stream.Stream;

public class UniqueStack<E> extends LinkedHashSet<E>{

    private int size = 0;

    @Override
    public Stream<E> stream() {
        return super.stream();
    }

    public boolean push(E e) {
        if (!contains(e)) {
            ++size;
            return super.add(e);
        }
        return false;
    }

    public E pop() {       
       // struck here
    return;
    }
}

Ответы [ 2 ]

0 голосов
/ 06 февраля 2020

Я считаю, что было бы лучше использовать instance обычного стека для стековых операций, но используйте эффективность HashSet для отслеживания дубликатов. Дополнительные методы могут быть добавлены с использованием той же идеи. 

    UniqueStack<Integer> stack = new UniqueStack<>();

    stack.push(10);
    stack.push(20);
    stack.push(30);
    stack.push(40);
    stack.push(30); // ignored
    stack.push(50);

    System.out.println(stack);
    int v = stack.pop();
    System.out.println(v);
    System.out.println(stack);
    stack.push(1);
    stack.push(2);
    System.out.println(stack);
    v = stack.pop();
    System.out.println(v);
    System.out.println(stack);

Вывод этого

[10, 20, 30, 40, 50]
50
[10, 20, 30, 40]
[10, 20, 30, 40, 1, 2]
2
[10, 20, 30, 40, 1] 

class UniqueStack<E> extends LinkedHashSet<E> {

    Stack<E> stack = new Stack<>();
    private int size = 0;


    public Stream<E> stream() {
        return stack.stream();
    }

    public boolean push(E e) {
        if (!contains(e)) {
            ++size;
            stack.push(e);
            return add(e);
        }
        return false;
    }

    public E pop() {
        E val = null;
        if (!stack.isEmpty()) {
            --size;
            val = stack.pop();
            remove(val);
        }
        return val;
    }
}
0 голосов
/ 06 февраля 2020

Сделайте это следующим образом: 

public E pop() {
    E e = null;
    if (!isEmpty()) {
        Iterator<E> itr = iterator();
        while (itr.hasNext()) {
            e = itr.next();
        }
        remove(e);
    }
    return e;
}

Тест: 

public class Main {
    public static void main(String[] args) {
        UniqueStack<Integer> stack = new UniqueStack<Integer>();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println(stack.pop());
        System.out.println(stack.size());
    }
}

Выход: 

30
2

Не стесняйтесь комментировать в случае возникновения проблемы.

...