Чем очередь (FIFO) отличается от стека (LIFO)?

Очередь — первым пришёл, первым ушёл: обработка задач по порядку, обход графа в ширину. Стек — последним пришёл, первым ушёл: отмена действий, обход в глубину, разбор скобок.

В современной Java обе структуры реализует ArrayDeque — двусторонняя очередь на кольцевом массиве. Она добавляет и снимает элементы с обоих концов за O(1):

• как очередь: offer / poll / peek;
• как стек: push / pop / peek.

Старый класс Stack использовать не рекомендуют: он синхронизирован без необходимости (медленнее) и наследует Vector, поэтому наружу «протекают» операции по индексу, которые ломают идею стека. LinkedList тоже реализует Deque, но обычно медленнее ArrayDeque.

Отдельно: PriorityQueue — не FIFO, она отдаёт наименьший элемент по сравнению (двоичная куча, O(log n)). Для многопоточной работы есть блокирующие очереди: ArrayBlockingQueue, LinkedBlockingQueue.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2);
stack.pop();                 // 2

Queue<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.offer(2);
queue.poll();                // 1