Stacks & Queues

A stack is last-in first-out, a queue is first-in first-out, and a deque opens both ends. Each gives constant-time push and pop at its working end.

	C++	Python	Java
Stack	vector	list	ArrayDeque
Queue	queue	collections.deque	ArrayDeque
Deque	deque	collections.deque	ArrayDeque

A stack models nesting and undo, such as matching brackets, evaluating expressions, or canceling adjacent neighbors. A queue models pending work in arrival order, like rotations, round-robin elimination, and breadth-first traversal. Never pop from the front of a plain array or Python list, since shifting every remaining element costs $O(n)$.

Operation	Stack	Queue	Deque
Push / pop at the working end	$O(1)$	$O(1)$	$O(1)$
Peek	$O(1)$	$O(1)$	$O(1)$
Push / pop at the other end	not supported	not supported	$O(1)$

Use one whenever the order items come back out is the whole problem, where most recent first is a stack and oldest first is a queue.

The problems below start with bracket matching and adjacent-pair removal, move through expression evaluation, nested repeat expansion, and undo/redo, and end with queue rotation and round-robin elimination.