Back to Study Material Data Structures and Algorithms

Stack

A stack is a linear data structure that follows the last-in, first-out principle, meaning the element added most recently is the first one removed. Think o...

Stack

Understanding the Stack: Last-In, First-Out Memory

A stack is a linear data structure that follows the last-in, first-out principle, meaning the element added most recently is the first one removed. Think of a stack of dinner plates: you place a new plate on top and remove from the top as well. You cannot reach a plate in the middle without first lifting every plate above it. This constraint is not a limitation but a deliberate design that makes stacks extremely useful in scenarios where the most recent context matters most.

In memory, a stack is typically implemented either with an array or a singly linked list. The array-based implementation uses a pointer called top that starts at minus one to indicate an empty stack. When an element is pushed, top increments and the value is stored at that index. When an element is popped, the value at top is returned and top decrements. With a linked list, each new node is inserted at the head and removal also happens at the head, keeping both operations at O(1) time.

The time complexity of all fundamental stack operations is O(1): push, pop, and peek are all constant time regardless of how many elements exist in the stack. The space complexity is O(n) where n is the number of elements stored. This efficiency comes from operating exclusively at one end, eliminating any need to shift or traverse elements.

Programming languages themselves rely on stacks. Every time a function is called, a new stack frame is pushed onto the call stack holding local variables, parameters, and the return address. When the function finishes, its frame is popped and control returns to the calling function. Recursive algorithms that call themselves many times can overflow the call stack if the recursion depth is too large, causing a stack overflow error.

Worked example: trace a call to factorial(3). The runtime pushes frames for factorial(3), factorial(2), and factorial(1) in order. Factorial(1) returns 1, its frame is popped, then factorial(2) multiplies and its frame pops, finally factorial(3) completes. The stack depth equals the recursion depth.

Interview tip: whenever a problem involves matching, reversing, or tracking the most recently seen element, consider a stack as your first candidate data structure before exploring more complex approaches.

Array vs Linked List Stack Implementations

Choosing between an array-backed stack and a linked list stack involves trade-offs in memory layout, cache behavior, and flexibility. Both achieve O(1) push and pop, but they differ in how memory is allocated and accessed.

An array-backed stack allocates a contiguous block of memory upfront. Elements sit side by side, giving the CPU cache a chance to prefetch upcoming values during iteration. Access by index is O(1). The downside is a fixed capacity: once the array fills, the stack must either throw an overflow error or resize. Dynamic resizing doubles the array when full, which is O(n) for that single operation but amortized O(1) across many pushes. Memory may be wasted if the stack is small relative to the allocated array.

A linked list stack allocates memory for each node independently on the heap. Each node holds a value and a pointer to the next node. Pushing a new element allocates a node and points it to the current head; the head pointer then moves to the new node. Popping reads the head value, moves the head pointer to the next node, and frees the old node. There is no fixed capacity, so the stack grows as needed up to available memory. The cost is extra memory per node for the pointer and poorer cache locality since nodes may be scattered across the heap.

For most practical purposes, an array-backed stack with dynamic resizing is preferred because of its cache friendliness and simpler memory management. Linked list stacks shine when the maximum size is completely unknown and memory fragmentation is acceptable.

Worked example: a stack holding integers 1, 2, 3 (3 on top) is represented as an array [1, 2, 3] with top equal to index 2. Pop returns 3 and sets top to 1. A subsequent push of 5 stores 5 at index 2 and sets top back to 2, giving [1, 2, 5].

Interview tip: when asked to implement a stack from scratch, clarify whether a fixed size is acceptable. Mention amortized complexity if you choose dynamic resizing, as it signals awareness of hidden costs in reallocation.

Real-World Applications of Stacks in Software

Stacks appear throughout software engineering in contexts that require tracking recent history or reversing order of operations. Understanding these patterns helps you recognize stack problems quickly under interview pressure.

Browser navigation maintains two stacks: a back stack and a forward stack. Each time you visit a new page, the current page is pushed onto the back stack and the forward stack is cleared. Pressing back pops from the back stack and pushes the page onto the forward stack. Pressing forward reverses the process. This design gives browsers O(1) navigation in both directions using only two stacks.

Text editors implement undo and redo with the same two-stack approach. Each user action, typing a character, deleting a word, or formatting text, is pushed as a command object onto the undo stack. Pressing Ctrl+Z pops the most recent command, reverses it, and pushes it onto the redo stack. Pressing Ctrl+Y pops from the redo stack and re-applies the command. Any new user action clears the redo stack because the history has diverged.

Compilers and interpreters use stacks during parsing to track nested structures like parentheses, brackets, and braces. The compiler pushes an opening symbol onto the stack and, upon encountering a closing symbol, checks whether the top of the stack is the matching opener. This is the basis for the balanced parentheses problem discussed in its own topic.

Depth-first search in graph traversal can be implemented iteratively using an explicit stack instead of recursive calls. Push the starting node, then repeatedly pop a node, process it, and push its unvisited neighbors. This avoids the risk of call stack overflow for very deep graphs.

Worked example: an IDE syntax checker reads the expression ( [ { } ] ). It pushes (, then [, then {. On }, it pops { and verifies the match. On ], it pops [ and verifies. On ), it pops ( and verifies. Stack is empty and all matches succeeded, so the expression is valid.

Interview tip: if a problem mentions undo, backtracking, or nested structures, state immediately that a stack models the problem naturally. Articulating the connection before coding demonstrates clear algorithmic thinking.