Что выбрать, Stack или Queue?

Queue – один из основных интерфейсов Java Collections Framework. В общем случае (но не обязательно) представляет FIFO-коллекцию – элементы можно добавлять в хвост, брать или удалять из головы. Его наследник, интерфейс Deque (double ended queue, двусторонняя очередь), позволяет манипулировать элементами на обеих сторонах.

Stack – LIFO коллекция. То есть добавлять и удалять элементы можно только с одного конца. Кроме того, стек наследуется от Vector, и тоже является пересинхронизированным и устаревшим. Его документация явно рекомендует предпочесть использовать Deque.