java - 如何在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

我认为最好使用常规堆栈的实例进行堆栈操作，但使用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;
    }
}