I think this is somewhat inconsistent since the empty node exists only before the first reclaim triggers. I think a more consistent approach might be leaving this empty node at the end.
xiaoguaz
@pavelkang Since the user will not retrieval the value of reclaim node, I think this implementation is good enough.
Besides, if we delete the nodes between reclaim and head here, and leave the void node (Is that you mean?), there will be race condition (e.g. double free) happens with two push command at the same time.
Araina
@pavelkang, I think you might misunderstand this picture, it does leave an empty node, which is always pointed by the head pointer. (Notice that 3 and 10 are popped from queue.)
cmusam
In unbounded queue implementation, reclaim is a pointer to the earliest element that is no longer in the queue, but has not yet been deleted.
ZhuansunXt
Question: is the complexity of push() operation now still O(1) (amortized to be O(1))?
lol
It is amortized O(1). If there are $n$ pushes and $m$ pops, and as $m \le n$, the number of deletes is the number of pops, so we are doing $n + m$ operations over $n$ push operations. Hence the amortized cost is $1 + m/n \le 2 = O(1)$.
I think this is somewhat inconsistent since the empty node exists only before the first reclaim triggers. I think a more consistent approach might be leaving this empty node at the end.
@pavelkang Since the user will not retrieval the value of reclaim node, I think this implementation is good enough.
Besides, if we delete the nodes between reclaim and head here, and leave the void node (Is that you mean?), there will be race condition (e.g. double free) happens with two push command at the same time.
@pavelkang, I think you might misunderstand this picture, it does leave an empty node, which is always pointed by the head pointer. (Notice that 3 and 10 are popped from queue.)
In unbounded queue implementation, reclaim is a pointer to the earliest element that is no longer in the queue, but has not yet been deleted.
Question: is the complexity of push() operation now still O(1) (amortized to be O(1))?
It is amortized O(1). If there are $n$ pushes and $m$ pops, and as $m \le n$, the number of deletes is the number of pops, so we are doing $n + m$ operations over $n$ push operations. Hence the amortized cost is $1 + m/n \le 2 = O(1)$.