If both queues are immutable, enqueuing/dequeuing is just creating a new queue with/without the element in it.

So thread A and thread B can share the same queue, but will create two different queues (one for each thread) when enqueuing to it.

Now if you want to share a queue between two threads, you have to simply synchronize between the threads and share each of their current versions of the queue.