автор1. compareAndSet - это и есть блокировка, просто она wait free. Вслед за этим все заворачивается в цикл, который как раз и реализует это ожидание. Поэтому алгоритм не "без блокировок" и не "без ожиданий".

Строго говоря, это lock-free называется, см. http://www.1024cores.net/home/in-russian/lock--wait--obstruction--atomic-free-algorithms

автор2. Это даже не стек. Ибо в силу отсутствия сериализации вполне допускается ситуация, когда поток будет пытаться вставить элемент, но у него это достаточно долго не будет получаться, при том, что другие потоки будут вставлять и вынимать объекты из "стека".
Это starvation, есть такое, но из этого не следует, что это перестает быть стеком, следуя такой логике Collections.synchronized(deque) это тоже не стек, да и ConcurrentLinkedDeque тоже не стек.

авторГонять в цикле генератор новый Entry, при том, что достаточно менять одну ссылку это перебор.
+

авторПри пустом стеке может забрать новый элемент. Что, правда, может и не плохо.
+, надо добавить else return null;

Да, кстати, а как наличие GC отменяет ABA? Вполне теоретически возможна ситуация, когда Entry собирается GC и new Entry возвращает объект по тому же адресу.

авторНу если Entry не пересоздавать в цикле ожидания, то проблемы быть не должно.:)
Ибо GC он не достанется, так как удерживается переменной в стеке потока, а то, что добавлено в "стек" удерживается "стеком".
Да, точно, я тупанул

questioner, ну, что, придумал как написать size()?))