IMHO Я уже кусок из книги прочитал.

В данном коде, не может быть ситуации "Поток 2 добавляет A обратно на стек".
Так как в данном коде НЕТ никакой возможности извлечь Node из стека и потом тот же Node положить обратно. Т.к. Node каждый раз создается разным

Но в данном коде есть "два финта ушами"

1.
Обращение к объекту, хотя мы не уверены, что этот объект нам принадлежит

Вида "newHead = oldHead.next" /// а oldHead == top

Для Java это безопасно, для C не очень ))) Т.к. в этот момент top доступен нескольких потокам и никто не может гарантировать, что другой поток в этот момент не освободит данный блок памяти. Как минимум для C это грязный код.

IMHO В качестве "маловероятной жести" : например другой поток на C в этот момент извлек top из стека, освободил данный блок памяти, вернул его операционной системе, операционная система освободила всю страницу операционной памяти и заодно пометила ее как ни используемой и запрещенной для доступа. И первый поток, попытавшись обратиться к ней, получит ошибку GPF / доступ запрещен ))) Вероятность такого конечно крайне низка, тем приятнее такие ошибки отлаживать IMHO.

Т.е. на Java так делать можно, на C, в общем случае, это не корректно.

Вывод из этой проблемы, при попытке использования данного алгоритма на языках без автоматического управления памятью, достаточно сложно придумать код для корректного удаления памяти.

А вот здесь внимание! Легкое передергивание! Да, на Java мы можем так делать и можем "не думать" об удалении объектов. Как написано в книжке "letting the garbage collector manage link nodes for you"

Но хорошо ли это?

И ответ на данный вопрос НЕТ. Даже в Java, лучше все же за собой мусор убирать. А особенно в долго живущих объектах приложения. И в других коллекциях его убирают.

2.
Собственно исходный постулат, если "вершина не менялась, то коллекция не менялся"

Постулат полностью правдив. Так как любой Node находящаяся в коллекцию по определению уникальна (она создается) и нет никакой возможно "извлечь ее и положить обратно"

===
Т.ч. данной придуманной проблемы в данном коде нет.

Зато есть другая проблема! Объект Node не очищается. Если коллекция долго живущая, это может порождать связанный мусор!

Т.е. достаточно одному объекты Node попасть в OldGen область память, как все остальные Node, с которыми работает коллекция, оказывается не возможно очистить через Minor Garbage Collector и пофиг, насколько они короткоживущие. Их от удаления защищает мусор лежащий в OldGen'е !

А вот об этой особенности алгоритма, я в книжке не прочел. Да и в JavaDoc об этом вроде ни одним словом. (((

Offtopic: Как на сайт опубликовать картинку с локального диска ?

За что купил, за то и продаю.

http://psy-lob-saw.blogspot.ru/2016/03/gc-nepotism-and-linked-queues.html

Но на графике от JConsole я вижу не то, что хотел бы. Сильно не уверен, что виной коллекция (((

Код от psy-lob-saw однозначно содержит данный эффект. Через JConsole это видно не однозначно, но если добавить банальный подсчет кол-во выделенной памяти и кол-во освобожденной (добавив метод finalize() ), то хорошо видно, minor GC объекты Node чистить отказывается.

На графиках от JConsole можно увидеть все, что хочешь ((( Это как чернильную кляксу рассматривать или на кофейной гуще гадать (((

Плюс видны утечки памяти, которые вообще с коллекциями не связаны. Возможно проистекают от работы JConsole. На моем компе где-то под 10 Mb в oldGen забивается.

На реализации ConcurrentLinkedQueue от JDK 1.8.65 лично я эффект не наблюдаю. Или просто его не заметил. Или в JDK 1.8 исправили.

В общем, х.з.

questioner...
Но если будет такой сценарий:
ABC-> DABC->ABC

Подозреваю "будет фиолетово". Т.е. работать алгоритму стека это не помещает (а для связанного списка, подозреваю, и такая ситуация не возможна).

questioner...
Точнее как Си может создать объект с таким же адресом
delete ptr;
ptr = new SomeType();

При некоторой доли везения (или невезения) адрес в ptr останется тот же самый, а объект будет другим.

IMHO

questionerНа чем основаны подозрения?

Лениво такую ситуацию на листочке рассматривать.

questionerА в джаве всё то же самое, только без delete, всё ещё не понимаю в чем разница
Нет. Без delete такого не получится.
Нет delete - нет и проблемы (что в C, что в Java).