Stack without duplicates

Question

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).

Answer 1

Here is the solution I found. I suppose here that the values entering the stack will be in $[\![0, n-1]\!]$. For that, I create an array $a$ of size $n$ that will implement a kind of doubly linked list: it is such that for $i \in [\![0, n-1]\!]$, $a[i] = (p_i, n_i)$ where:

• if $i$ is not in the stack, $(p_i, n_i) = (-2, -2)$;
• if $i$ is in the stack, $p_i$ (previous) is the value that is above $i$ in the stack ($-1$ if $i$ is the top of the stack) and $n_i$ (next) is the value that is below $i$ in the stack ($-1$ if $i$ is the bottom of the stack).

The stack is then a couple $(i_0, a)$, where $i_0$ is the top element of the stack ($-1$ if the stack is empty).

That way, the usual operations on stack can be done in $O(1)$ worst case:

• testing emptyness: just check if $i_0 = 1$ or not;
• pushing element $i$:
  • if $a[i] = (-2, -2)$, $a[i] \leftarrow (-1, i_0)$ then $i_0 \leftarrow i$
  • if $a[i] = (p_i, n_i)$ (duplicate case), then $a[p_i] \leftarrow (p_{p_i}, n_i)$, $a[n_i] \leftarrow (p_i, n_{n_i})$ (only if $p_i/n_i\neq -1$), $a[i] \leftarrow (-1, i_0)$ then $i_0 \leftarrow i$
• popping element: $i\leftarrow i_0$, $i_0 \leftarrow n_{i_0}$ $a[i] \leftarrow (-2, -2)$, return $i$.

In the case of the DFS, one can also add the case $a[i] = (-3, -3)$ to differentiate vertices that already exited the stack from the $a[j] = (-2, -2)$, vertices that have not already entered the stack. The array a can then replace the boolean array usually used.