The key reason that this can be implemented without locks is that push() only modifies the tail of the queue (even though it reads both) and pop() only modifies the head of the queue (even though it reads both).