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: brackets, expressions, cancelling neighbors. A queue models pending work in arrival order: rotations, eliminations, breadth-first traversal. Never pop from the front of a plain array or Python list; that shifts every element and 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 things come back out is the whole problem: most recent first is a stack, oldest first is a queue.

The problems below start with bracket matching and stack simulation, move to expression evaluation and undo/redo, and end with queue rotation.