I was thinking about the implementation of a DFS on graphs, and particularly about space complexity. The DFS algorithm can be implemented with a stack data structure. When a vertex $v$ is met during the exploration of the adjacency list of a vertex $w$, if $v$ has not already been processed, then $v$ is added to the stack. A vertex is marked a processed when it exits the stack (contrary to BFS, where a vertex is marked as seen when it enters the queue).
That way, the stack may contains duplicates during the execution of the DFS. Since each vertex is processed at most once, the size of the stack for a graph $(V, E)$ is $O(|V| + |E|)$.
Since I wondered if it was possible to get $O(|V|)$ space memory for the DFS, I tried to find a data structure of stack without duplicates. I found a solution for the DFS (given as an answer to this question), but the structure I found has restrictions: it works in space $\Theta(n)$ in the case I know in advance that the values entering the stack will be in $[\![0, n-1]\!]$.
My question is: is there a more efficient way to implement a stack without duplicates (in a stack without duplicate, if I push an element already in the stack, then this element is put at the top of the stack, and the duplicate is deleted), in the general case where I don't know in advance the values entering the stack? The time complexity for operation of pushing/popping should be in $O(1)$ worst case, amortized or average case (in this order of preference). Also, is there a way to use $\Theta(n)$ space memory, $n$ being the current size of the stack (and not the maximal size).