Stacks and Queues

Stacks

Linear data structure, LIFO (Last In, First Out). Insert and remove happen only at the top.
Operations: push, pop, top / peek, isEmpty, size. All are $O(1)$ when backed by a dynamic array.
Uses: temporary storage during recursion and the function call stack, undo / redo in editors, reversing a string, parenthesis matching, postfix / infix conversion.
Recognition signals: matching or nesting (brackets), “most recent unresolved item”, evaluating expressions, converting recursion to iteration, next greater / smaller element.

Linear data structure, FIFO (First In, First Out). Items are added at the rear and removed from the front.
Operations: enqueue, dequeue, front, rear, isEmpty, size.
Uses: breadth-first search, operating system job / disk / CPU scheduling, level-order traversal, simulations of “waiting in line”.
A queue backed by a plain array makes dequeue $O(n)$ ; use a linked list, circular buffer, or a deque for $O(1)$ .

Insert and delete are allowed at both ends: insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull.
Input-restricted deque: insertion at one end only, deletion at both.
Output-restricted deque: deletion at one end only, insertion at both.
Used for sliding window maximum / minimum (monotonic deque of indices).

Each element has a priority, and elements are served in priority order rather than insertion order.
Uses: Dijkstra and Prim’s algorithms, Huffman coding, finding the Kth largest / smallest element (top K with heapq), scheduling.

Implementation	peek	insert	delete
Linked list	$O(1)$	$O(n)$	$O(1)$
Binary heap	$O(1)$	$O(\log n)$	$O(\log n)$
Binary search tree	$O(1)$	$O(\log n)$	$O(\log n)$

Stack	Queue
Data is added and removed from the top	Data is added at the rear and removed from the front
LIFO principle	FIFO principle
Insertion is `push`	Insertion is `enqueue`
Deletion is `pop`	Deletion is `dequeue`
One pointer for both add and remove: `top()`	Two pointers: `front()` and `rear()`
Used for recursion-style problems (nesting, backtracking)	Used for sequential processing (BFS, scheduling)

Maintain a stack whose elements stay in a specific order (increasing or decreasing). Before pushing a new element, pop everything that would break the order.
Each element is pushed and popped at most once, so the whole pass is $O(n)$ .
Use it to find the next greater or smaller element (or previous), daily temperatures-style “days until warmer”, and largest rectangle in a histogram.
Store indices rather than values when you need distances or positions.

Problem	Pattern / Template
Baseball Game	Stacks
Valid Parentheses	Stacks
Min Stack	Stacks
Number of Students Unable to Eat Lunch	Queues
Implement Stack Using Queues	Queues