Stacks and Queues

Stacks and queues are restricted linear collections that differ only in where elements are added and removed.

Stack (LIFO)

Last In, First Out: the most recently pushed element is popped first.

• push(x): add to top, $O(1)$.
• pop(): remove from top, $O(1)$.
• peek(): inspect top without removing, $O(1)$.

Queue (FIFO)

First In, First Out: the oldest enqueued element is dequeued first.

• enqueue(x): add to back, $O(1)$.
• dequeue(): remove from front, $O(1)$.
• front(): inspect front, $O(1)$.

Deques

A double-ended queue supports insertion and removal at both ends in $O(1)$.

• Generalizes both stack and queue.
• Usually backed by a doubly linked list or a circular dynamic array.

Array vs Linked Implementations

Aspect	Array-backed	Linked-list-backed
Push/pop	$O(1)$ amortized	$O(1)$ worst case
Memory	contiguous, less overhead	pointer per node
Resizing	occasional $O(n)$ copy	none needed

Queue via array

Use a circular buffer (wrap indices with modulo) so both ends operate in $O(1)$ without shifting.

Applications

• Call stack: function calls push frames, returns pop them; recursion depth bounded by stack size.
• Expression evaluation and matching brackets use a stack.
• Breadth-first search in Graphs uses a queue to visit nodes level by level.
• Undo/redo and backtracking use stacks.