One very simple approach is to gang a pair of sequential deques together, each protected by its own lock. To right-push an element onto the combined deque, acquire the right-hand deque’s lock and right-push the element. To left-push an element onto the combined deque, acquire the left-hand deque’s lock and left-push the element.
Popping is harder, but not by much. First, we will need a lock hierarchy. Because I am right-handed, this algorithm will acquire the right-hand deque’s lock before acquiring the left-hand deque’s lock, but you should of course feel free to reverse this hierarchy if you wish.
To right-pop an element from the combined deque, acquire the right-hand deque’s lock and right-pop an element. If there is no element to pop, acquire the left-hand deque’s lock and right-pop an element. Return the element popped, or a failure indication if both deques were empty, then release the lock(s).
Left-popping is harder, but only slightly harder. Acquire the left-hand deque’s lock and left-pop an element. If successful, release the lock and return the element.
If the left-hand deque was empty, release its lock and acquire the right-hand deque’s lock followed by the left-hand deque’s lock. Left-pop an element from the left-hand deque, and if the deque is still empty, left-pop an element from the right-hand deque. Release both locks, and return an element if there was one, otherwise return a failure indication.
A schematic view of this parallel deque is shown below:
There, that wasn't so hard, now was it?
People who enjoy complexity are of course free to think about ways to balance elements between the deques. For example, instead of left-popping only a single element from the right-hand deque, perhaps it would be better to move some or all of the remaining elements to the left-hand deque. All manner of heuristics could be proposed and analyzed!
Alternatively, can you implement a simple lock-based scheme that allows concurrent operations at each end of the parallel deque to proceed in parallel?