Love discussing work stealing queues. My first comment is that once you have a private queue you sort of lose the benefits of a work stealing queue and are in the domain of work sharing. That might be fine in practice but has different properties.

The weirdest work stealing queue I have read about is one that tries to model the x86 store queue to avoid a StoreLoad by making sure enough stores happen between the push and the take. Not very practical though.