Stacks & Queues

Linked-node push is O(1) worst case: allocate a node and link it to the head. Array-backed push is O(1) amortized: usually one slot write, but a full buffer forces copying every element into a larger block.

Only when the outbound stack is empty. Pushing the inbound stack's contents onto a non-empty outbound stack puts newer arrivals above older ones and destroys first-in-first-out order. Standard implementations drain the inbound stack completely in that one transfer.

A queue hands nodes back in the order they were discovered, so every person at one depth is expanded before anyone a depth lower. A stack returns the most recent discovery first, which dives down a single reporting chain instead.

Removing the element at index 0 slides every remaining element one slot toward the front, so a single dequeue costs O(n). Draining a backlog of n items that way costs about n^2/2 moves in total.

A ring buffer moves an index instead of data: dequeue reads the slot at head, then advances head by one, wrapping to zero past the last slot. Nothing is copied. A shift-down queue relocates every remaining element.

A counter records how many delimiters are open, not which ones. With several delimiter types you must know the type of the most recently opened one to reject overlapping pairs, and last-opened-first-closed is exactly what a stack gives you.

Push and pop touch only the top position, so each does a fixed amount of work however many elements are stored. A stack exposes no access below the top, so finding a value means uncovering elements one at a time: O(n).

Each element is pushed at most twice and popped at most twice across its entire lifetime, so any sequence of m operations does O(m) work in total. The one expensive transfer pays for all the cheap removals that follow it.

Two equal minima produce only one auxiliary entry, so removing the first occurrence discards the record while an equally small value is still stored. The structure then reports a minimum that is too large. Record on less-than-or-equal, or store counts.

The snapshot freezes how many nodes belong to the current level before any of their children are added. Without it the loop bound keeps growing as children are inserted, and the level boundary is lost.

A circular-array queue never moves stored elements. Dequeue advances the front index by one modulo the array's capacity, and enqueue writes at the wrapped back position, so both are O(1) and freed front slots get reused.

With two indices and all N slots usable, head == tail means empty after zero writes and full after N writes — indistinguishable. Fix it with a count field, one permanently unused slot, or non-wrapping counters.

They are different things. A stack data structure is a LIFO discipline over memory you allocate on demand, so its ceiling is available memory. A thread's call stack is one fixed contiguous region reserved when the thread starts.

Undo reads the newest entry, but a cap must discard the oldest — and those live at opposite ends. A stack only reaches one end, so trimming the oldest costs O(n); a deque appends at the back and evicts from the front, both constant time.

Because an odd-length input leaves a lone middle element with no partner. Looping while more than one element remains stops before that element, so the front pop never empties the deque and leaves the back pop with nothing to remove.

Every linked element carries a next-pointer plus allocator bookkeeping, so a small payload often costs two to three times its own size. Array backing instead pays in unused reserved slots and needs one enormous contiguous block.

Growing at full and shrinking at half leaves no gap between the triggers, so a stack at the boundary oscillates: push grows and copies, pop shrinks and copies back. Every operation becomes O(n). Shrink at one-quarter instead.

Dequeuing the last element empties the head reference but leaves the tail pointing at the node just removed. A later enqueue then links onto that detached node while head stays empty, so the item is lost and the queue looks permanently empty.

A power-of-two capacity makes index mod N exactly index & (N-1): a bitwise mask instead of a division, which matters in tight per-item loops. It stops paying when rounding capacity up wastes real memory.

A stack returns the most recent push, so pushing children left to right makes the rightmost child come out first. Pushing them right to left puts the leftmost on top, which reproduces the order recursion visits siblings in.

Operands are pushed left to right, so the top of the stack is the right-hand operand and the value beneath it is the left. Reversing the two pops silently inverts subtraction and division while sums and products still look correct.

Two conventions exist: top indexes the last element (empty is top == -1, push increments then writes), or top indexes the next free slot (empty is top == 0, push writes then increments). Pick one and check every operation against it.

Both backings hit O(1) at each end, so the decision is constants: a linked list pays two pointers and an allocation per element and defeats cache prefetching, while array-backed storage keeps elements contiguous. The linked form wins mainly when per-operation worst-case latency matters more than throughput.

Amortized O(1) enqueue hides one operation that copies the whole buffer, landing on one unlucky player at the tail. Reserve the peak capacity up front, or use a backing with no bulk copy, then verify against the tail percentile.

One must be linear because a queue only removes from the front while the newest element sits at the back. Make push linear when reads and removals dominate; make removal linear when insertions dominate. Nothing here amortizes.

Memory fails first: an unbounded queue turns a rate mismatch into unbounded growth, so the backlog itself becomes the leak. Queueing delay grows with it, and a crash discards every job still resident.

Overwrite when recency beats completeness — a crash-diagnosis recorder wants the last N events whatever came before. Reject when every record must survive, such as billed usage or an audit trail. Either way, count the losses and expose them.

Redo entries are only meaningful against the exact state they were undone from. A new action rewrites history from that point, so replaying them would target objects that no longer exist. Clearing the redo stack keeps the model honest.

Signal the failure out of band. A sentinel is safe only when it lies outside the element domain, and for signed sensor readings -1 is a legal reading, so the caller cannot tell emptiness from data and the corruption is silent.