How to keep Immutable Stack References in Sync?

I'm creating this question based upon a small discussion I had in the comments to the answer to this question: design a method returning a value or changing some data but not both

@Kata pointed out that the pattern that the OP was interested in is called Command–query separation and argued that this is a good model to structure your code by.

From wikipedia:

Command–query separation (CQS) is a principle of imperative computer programming. It was devised by Bertrand Meyer as part of his pioneering work on the Eiffel programming language.

It states that every method should either be a command that performs an action, or a query that returns data to the caller, but not both. In other words, Asking a question should not change the answer.1 More formally, methods should return a value only if they are referentially transparent and hence possess no side effects.

I questioned the soundness of this design principle, as in general it would appear to make your code far more tedious. For instance: you could not perform a simple statement like next = Queue.Dequeue(); You would need two instructions: one to modify the data structure and one to read the result.

@Kata found an alternative approach that at first glance appears to satisfy the best of both worlds: taking a page from functional programming, we define our Stack as an immutable data-structure. Whenever we push(x) we create a new Stack node that holds the value x and maintains a pointer to the old head Stack instance. Whenever we pop() we just return the pointer to the next Stack instance. Thus we can adhere to the Command-Query Separation Principle.

However, one thing that is unclear in this case is how you would keep multiple references to the Stack in sync while still adhering to the Command-Query Separation Principle? I don't see an obvious solution to this. So as a point of curiosity I'm posing this problem to the community to see if we can't find a satisfactory solution :)