Compare ArrayDeque, Stack, and the various queue choices. What should you actually use for a stack or queue today?

Use ArrayDeque for both stacks and queues: it's array-backed, faster than LinkedList, and unlike the legacy Stack class (which extends Vector and is synchronized and slow) it isn't burdened by Vector's design.

Prefer the Deque methods (push/pop/offer/poll) which return/insert without throwing on empty, over add/remove which throw. For producer-consumer concurrency reach for BlockingQueue implementations (ArrayBlockingQueue, LinkedBlockingQueue), and for priority ordering use PriorityQueue, remembering it isn't thread-safe and iteration order isn't sorted.