如何实现只在Java中存储唯一值的堆栈

Question

我正在尝试实现唯一的堆栈。如果我尝试扩展堆栈类并使用contains，它将看起来整个堆栈，时间复杂度将变为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;
    }
}

Answer 1

我相信最好将常规堆栈的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;
    }
}

Answer 2

执行以下操作：

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

如有问题，请随时发表评论。