Private deques can still be very effective for work-stealing, both in theory and practice! This paper comes to mind: https://hal.inria.fr/hal-00863028/document