1. 手写一个线程安全的队列（锁实现与 CAS 无锁实现），各有什么取舍？
问题
请手写一个线程安全的队列，分别给出基于锁（synchronized/ReentrantLock）的实现和基于 CAS 的无锁实现，并说明二者各自的取舍？
考察点
- 锁实现与 CAS 无锁实现的线程安全机制
- 阻塞与自旋的区别、吞吐量与公平性
- 不外借场景下的适用性判断
答案
锁实现（如 LinkedBlockingQueue）用一把锁或读写分离的锁保护头尾指针，入队出队操作原子；优点是简单、可控、天然支持阻塞等待，缺点是锁竞争会带来上下文切换开销。CAS 无锁实现（如 ConcurrentLinkedQueue）用 AtomicReference 配合循环 CAS 更新头尾指针，不阻塞线程，采用自旋重试；优点是高并发下吞吐更高、无死锁、无上下文切换，缺点是实现逻辑复杂、可能出现 ABA 问题（需用版本号或 AtomicStampedReference）、在竞争激烈时自旋浪费 CPU。取舍上：锁适合临界区有阻塞或队列空闲场景多的场景，CAS 适合高并发短临界区、无阻塞要求的场景。
解析
锁的本质是"让出 CPU 等待"，CAS 的本质是"原地重试"。锁开销固定但公平可控，CAS 在高并发下能把竞争分散到各线程的自旋上，从而获得更高吞吐。选择时若不要求阻塞式 take/put，优先考虑无锁；若要求元素等待且队列容量有限，则用锁（配合 Condition）更合适。
示例代码
// 基于锁的简单线程安全队列
public class LockQueue<T> {
private final ReentrantLock lock = new ReentrantLock();
private final Condition notEmpty = lock.newCondition();
private Node<T> head, tail;
public void put(T v) {
lock.lock();
try {
if (tail == null) head = tail = new Node<>(v);
else { tail.next = new Node<>(v); tail = tail.next; }
notEmpty.signal();
} finally { lock.unlock(); }
}
public T take() throws InterruptedException {
lock.lock();
try {
while (head == null) notEmpty.await();
T v = head.val; head = head.next;
if (head == null) tail = null;
return v;
} finally { lock.unlock(); }
}
static class Node<T> { T val; Node<T> next; Node(T v){ val=v; } }
}
// 基于 CAS 的无锁入队（简化）
public class LockFreeQueue<T> {
private final AtomicReference<Node<T>> head = new AtomicReference<>(new Node<>(null));
private final AtomicReference<Node<T>> tail = new AtomicReference<>(head.get());
public void put(T v) {
Node<T> n = new Node<>(v);
while (true) {
Node<T> t = tail.get(), tNext = t.next.get();
if (tNext != null) { tail.compareAndSet(t, tNext); continue; } // 推进 tail
if (t.next.compareAndSet(null, n)) { tail.compareAndSet(t, n); return; }
}
}
static class Node<T> { T val; AtomicReference<Node<T>> next = new AtomicReference<>(null); Node(T v){ val=v; } }
}