Stack Operations
Every stack implementation exposes a small, well-defined set of operations. Understanding each one precisely, including its behavior on edge cases, is esse...
Push, Pop, Peek and isEmpty: The Core Stack API
Every stack implementation exposes a small, well-defined set of operations. Understanding each one precisely, including its behavior on edge cases, is essential for using stacks correctly and for implementing them without bugs.
Push adds an element to the top of the stack. In an array implementation, the top pointer increments and the new value is stored at that position. If the array is full and resizing is not supported, push raises a stack overflow error. In a linked list implementation, a new node is created, its next pointer is set to the current head, and the head pointer updates to the new node. Push is O(1) in both cases.
Pop removes and returns the top element. In an array, the value at the top index is read, and the top pointer decrements. In a linked list, the value at the head node is read, the head pointer moves to the next node, and the old node is freed. Calling pop on an empty stack must raise an underflow error or return a sentinel value such as null, depending on the language convention. Pop is O(1).
Peek, sometimes called top or front, returns the value of the topmost element without removing it. This is useful when a decision depends on what is at the top before committing to a pop. Peek is O(1) and should also check for an empty stack before attempting to read.
isEmpty returns a boolean indicating whether the stack has zero elements. An array stack checks whether top equals minus one. A linked list stack checks whether head is null. This operation gates all other operations and prevents underflow errors. Size, a related operation, returns the number of elements currently stored; it is O(1) if a counter is maintained alongside the structure.
Worked example: starting with an empty stack, push 4, push 7, peek (returns 7 without removing), push 2, pop (returns 2), pop (returns 7), pop (returns 4), isEmpty (returns true). Every operation completes in constant time independent of how many pushes and pops occurred.
Interview tip: always handle the empty stack case explicitly in code. Interviewers watch for unguarded pop or peek calls as a signal that a candidate overlooks edge cases under time pressure.
Implementing a Generic Stack with Dynamic Resizing
A production-quality stack should work with any data type and handle any number of elements without requiring the caller to specify a fixed capacity in advance. Achieving this requires generics or templates and an amortized resizing strategy.
Begin with an internal array of a small initial capacity, say four slots. Maintain a top pointer initialized to minus one and a count of stored elements. On each push, if count equals the array length, allocate a new array of double the size, copy all existing elements, and replace the internal reference. Then store the new element at the incremented top. This doubling strategy ensures that N total push operations require O(N) total work for all resizing steps combined, giving an amortized cost of O(1) per push.
For memory efficiency, consider shrinking the array when it is less than one-quarter full. Shrink to half the current size rather than to the exact count. This hysteresis prevents thrashing: if the stack size hovers around the shrink threshold, repeatedly alternating push and pop will not trigger repeated resizing.
In languages like Java or C#, generics allow the internal array to hold a typed element, producing compile-time safety without casting. In C++, templates achieve the same goal. In Python, lists already handle dynamic resizing internally, so a Python stack wraps a list and restricts operations to append and pop from the end.
In terms of complexity, push and pop are O(1) amortized. Worst-case for a single push that triggers a resize is O(n), but this occurs rarely and is offset by the O(1) average. Space complexity is O(n) with a constant factor of at most two due to the doubling strategy.
Worked example: a stack initialized with capacity 2 receives pushes of A, B, C. After pushing B, the array is full. Pushing C triggers a resize to capacity 4, copying A and B, then stores C at index 2. The stack holds [A, B, C] with top at index 2.
Interview tip: mention amortized analysis unprompted when discussing dynamic resizing. It shows you understand the difference between worst-case and average-case behavior, a key distinction in system design discussions.
Common Stack Pitfalls and Debugging Strategies
Even though stacks are conceptually simple, subtle bugs appear frequently in both interviews and production code. Knowing the most common failure modes and how to diagnose them saves significant debugging time.
Off-by-one errors are the most frequent mistake. In an array-backed stack, the top pointer represents the index of the current top element, not the next available slot. Initializing top to zero instead of minus one means an empty stack appears to have one element. Always verify: after push of the first element, top should equal zero; after pop of the last element, top should return to minus one.
Stack overflow occurs when you push onto a full fixed-capacity stack without resizing. This most often happens in recursive algorithms where the recursion depth exceeds the call stack limit. To detect it early, add a size check at the start of push and raise a meaningful error with the current capacity included in the message.
Stack underflow occurs when pop or peek is called on an empty stack. Every stack operation that reads from the top must be guarded by an isEmpty check. In an interview, always write this guard explicitly rather than relying on the language to throw an index error, because an uncaught index error reveals you did not think about the edge case intentionally.
Memory leaks in languages with manual memory management appear when popped nodes from a linked list stack are not freed. The pop operation must explicitly release the old head node after moving the pointer forward. In garbage-collected languages, ensure no external references hold onto popped objects unnecessarily, as this prevents the garbage collector from reclaiming memory.
Confusion between peek and pop is a logic error common in complex algorithms. Peek should never modify the stack state. If multiple parts of your algorithm call peek and later call pop separately, verify that no intermediate code pushes to the stack between the two calls, inadvertently removing the wrong element.
Worked example: a bug causes a balanced parentheses checker to return true for the string ( [ ) ]. Tracing through: push (, push [, encounter ), pop [ expecting ( but they do not match. The bug is in the match check, not in the stack mechanics. The stack correctly held the state; the comparison logic was wrong.
Interview tip: when your stack-based algorithm produces an incorrect result, trace the top pointer manually on a small test case before reaching for a debugger. Most stack bugs become obvious during a careful manual trace.