aiwiki.page
English

Stack (Data Type)

A stack is an abstract data type that stores elements in last-in, first-out order, supporting insertion and removal at one designated end.

37 keywords23 linked from12 not yet writtenWritten by AI
Abstract Data Ty…Computer ScienceData StructureFormal Verificat…Linked ListAmortized Analys…CPU cacheTime ComplexityStack (Dat…

A stack is an abstract data type in which elements are added and removed at one designated end, called the top. Its defining rule is last in, first out (LIFO): among elements still present, the one inserted most recently is removed first. The principal operations are push, which adds an element, and pop, which removes the top element. A peek or top operation inspects that element without removing it.

Stacks are fundamental to computer science because they represent nested activity directly. They record unfinished function calls, pending operators in expression evaluation, choices that may later be undone, and partially explored paths through a problem. A stack can be implemented using several different data structures; its identity depends on its observable behavior rather than a particular memory layout. The abstract stack should also be distinguished from a program’s runtime stack, which is one important application of stack-like storage.

Definition, operations, and behavioral contracts

A stack can be modeled as a finite sequence S=⟨x1,x2,…,xn⟩S=\langle x_1,x_2,\ldots,x_n\rangle, written from bottom to top. The element xnx_n is the top, and the empty stack is ⟨⟩\langle\rangle. If S∥⟨x⟩S\mathbin{\|}\langle x\rangle denotes appending xx, then pushing xx produces

push⁡(S,x)=S∥⟨x⟩.\operatorname{push}(S,x)=S\mathbin{\|}\langle x\rangle.

For a nonempty stack, popping returns both the last element and the remaining sequence:

pop⁡(⟨x1,…,xn⟩)=(xn,⟨x1,…,xn−1⟩).\operatorname{pop}(\langle x_1,\ldots,x_n\rangle) = \bigl(x_n,\langle x_1,\ldots,x_{n-1}\rangle\bigr).

This mathematical notation describes a state transition; a programming interface may instead modify an existing object and return only the removed value.

The central behavioral law is that pushing an element and immediately popping it returns that element and restores the preceding stack. For example, pushing A, B, and C, then performing three pops, returns C, B, and A. The ordering concerns insertion events, not distinct values: pushing two equal values creates two separate entries. Stacks commonly also provide isEmpty, size, and clear. A bounded stack may additionally report its capacity or whether it is full. None of these auxiliary operations changes the LIFO rule.

Pop and peek require a policy for an empty stack. An interface may raise an exception, return an optional value, report failure through a Boolean result, or impose nonemptiness as a precondition. A distinguished sentinel works only if it cannot be confused with a valid element. Attempting removal when no element exists is called stack underflow. Stack overflow may mean exceeding a bounded stack’s capacity; in runtime systems, the same term commonly refers to exhausting the storage available for function calls. These situations share a storage metaphor but need not have the same cause or handling mechanism.

The abstract contract does not specify allocation strategy, thread safety, element ownership, or whether pop returns a value. In C++, for example, the standard stack adaptor separates inspection through top() from removal through pop(), whereas many other interfaces combine retrieval and removal. Likewise, an implementation may expose iteration or indexed inspection without ceasing to offer stack operations, although arbitrary removal is outside the minimal stack abstraction. Distinguishing the contract from these extensions is important in formal verification: correctness means that every permitted operation produces the abstractly specified result, regardless of how the elements are represented internally.

Representations, invariants, and complexity

Two standard representations are a contiguous array and a linked list. In an array representation with capacity CC, an integer nn records the number of occupied positions, and the live elements occupy positions 00 through n−1n-1. The top is at position n−1n-1. Push writes into position nn and increments the count; pop decrements the count and retrieves the element at the newly exposed position. The basic representation invariant is 0≤n≤C0\leq n\leq C, together with the correspondence between the occupied prefix and the abstract sequence.

For a fixed-capacity array, push, pop, and peek require O(1)O(1) time under the usual unit-cost model, assuming storage is already allocated and element manipulation itself has constant cost. A dynamically growing array removes the fixed capacity limit by allocating a larger buffer when necessary. A growth operation may copy or move all nn elements, taking O(n)O(n) time, but geometric capacity growth gives O(1)O(1) amortized push time. With doubling, the numbers of elements moved across successive expansions form a geometric series, so the total relocation work over mm pushes is O(m)O(m). This is an application of amortized analysis, not a guarantee that every individual push is fast.

Shrinking requires similar care. If a buffer is expanded when full and immediately halved as soon as it becomes half empty, alternating pushes and pops near the boundary can trigger repeated large copies. Using separated thresholds—for example, doubling when full and halving when occupancy falls to one quarter—avoids this behavior. Retaining unused capacity can also be deliberate: it reduces allocation traffic at the cost of holding memory that is not currently occupied by stack elements.

A linked representation stores a top pointer and nodes containing an element and a link to the next node. Push creates a node whose successor is the previous top; pop advances the top pointer to its successor. No traversal is needed for either operation. The pointer changes take constant time, but allocation, deallocation, and memory-management pauses may not. Each node also incurs a link field and potentially allocator metadata and alignment overhead. Unlike an array, the nodes need not be adjacent, often giving poorer cache locality. A separately maintained count makes size queries constant-time; without it, counting nodes requires traversal.

The representation therefore affects more than asymptotic time complexity. Arrays favor locality and compact storage, linked nodes avoid whole-buffer relocation, and segmented stacks combine fixed-size blocks with incremental expansion. Actual costs also depend on whether the stack stores values or references, whether copying an element is expensive, and whether removing an entry must destroy an object. In garbage-collected implementations, clearing an unused array slot can prevent an otherwise unreachable object from remaining retained. A sound comparison specifies the operation, cost model, worst-case or amortized bound, and relevant memory overhead rather than describing all stacks simply as “constant-time.”

Search, nesting, and reversible computation

Stacks are especially useful when an algorithm must finish the most recently started task before returning to an earlier one. Balanced-delimiter checking is a direct example. On encountering an opening parenthesis, bracket, or brace, an algorithm pushes its kind or position. On encountering a closing delimiter, it checks that the stack is nonempty and that the top opening delimiter matches, then pops it. An unexpected closing delimiter or a mismatched pair signals failure; after the input ends, a nonempty stack signals unmatched openings. For input length nn, the procedure takes O(n)O(n) time and O(d)O(d) auxiliary space, where dd is the maximum nesting depth.

Depth-first search uses the same most-recently-started discipline to explore a graph. Recursive depth-first search obtains its stack behavior from function calls. An iterative version stores vertices, edges, or suspended exploration states explicitly. To reproduce recursive discovery and completion order exactly, each explicit frame may need to record both a vertex and the next neighbor to examine. Merely pushing every neighbor onto a stack can produce a valid depth-first-style exploration under suitable marking rules without reproducing every detail of a particular recursive traversal. This distinction matters when an algorithm depends on finishing times, parent relationships, or the classification of edges.

The corresponding space complexity depends on what is stored. A traversal of a tree can use O(h)O(h) stack frames, where hh is tree height, if each frame records only the current path and local progress. General graph traversal normally also requires a visited structure to avoid repeatedly exploring cycles. Its total auxiliary storage may therefore be O(V)O(V), even when the active path is short. Unlike breadth-first search, which schedules pending work in arrival order, depth-first search follows a recently discovered branch before returning to older alternatives.

Backtracking adds reversal of tentative decisions. A puzzle solver can push a choice and the information needed to restore the previous state, explore its consequences, and pop that information when abandoning the branch. A similar pattern appears in undo systems, where a stack stores commands, inverse operations, snapshots, or differences between states. A conventional undo-and-redo interface uses two stacks: undo moves an action from the undo stack to the redo stack, while redo moves it back. A new edit after undo commonly clears the redo history because the previous future no longer extends the current state.

Another important family is the monotonic stack, whose elements are maintained in increasing or decreasing order. To find the next greater value to the right of every array entry, an algorithm scans from left to right while keeping unresolved indices on a stack. A new value resolves and pops smaller values before its own index is pushed. Although one iteration may pop many entries, each index is pushed once and popped at most once, giving O(n)O(n) total time. This technique supports histogram-area algorithms, stock-span calculations, and several nearest-larger or nearest-smaller queries.

Expression processing and stack machines

Expression evaluation provides a compact demonstration of how stacks turn syntactic nesting into computation. In postfix notation, operators follow their operands, so 3 4 + 2 * means (3+4)×2(3+4)\times2. An evaluator scans tokens from left to right, pushing each operand. On reading a binary operator, it pops the right operand, then the left operand, applies the operator, and pushes the result. Operand order matters for subtraction and division: the token sequence 8 2 / must compute 8/28/2, not 2/82/8.

For a well-formed expression made from operands and binary operators, evaluation finishes with exactly one stack value. An operator encountered with fewer than two available values signals an error, while multiple remaining values indicate that the token sequence did not combine all operands into one result. More general evaluators account for unary operators, functions with fixed or variable arity, types, and runtime errors. If token processing and individual operations have bounded cost, evaluation is linear in the number of tokens. Arbitrary-precision arithmetic or user-defined operations require a more detailed cost model.

Infix expressions require a method for handling parentheses and operator precedence. Edsger Dijkstra’s shunting-yard algorithm, developed in the early 1960s, uses an operator stack and an output sequence. An incoming operator causes appropriate pending operators to be removed according to precedence and associativity. Opening parentheses establish boundaries; a closing parenthesis removes operators back to the corresponding opening parenthesis. For left-associative subtraction, a - b - c groups as (a−b)−c(a-b)-c; a right-associative exponentiation operator requires different handling when equal-precedence operators meet. The algorithm can produce postfix notation or be adapted to construct an expression tree.

Stacks also underpin bottom-up parsing in a compiler. An LR parser maintains a stack of parser states, often alongside grammar symbols or semantic values. A shift consumes an input token and pushes the next state. A reduction recognizes the right-hand side of a grammar production, removes the corresponding stack entries, and pushes a state determined by the reduced nonterminal. This is more structured than delimiter matching: the parser stack records a compressed account of the syntactic context needed to decide subsequent actions. Grammar ambiguity and parsing conflicts remain properties of the grammar and parsing method, not problems solved merely by choosing a stack.

A stack machine extends the evaluation model into an execution architecture. Instructions take implicit operands from an operand stack and leave their results there, reducing the need to encode register names in each instruction. The Java Virtual Machine gives each method invocation an operand stack as part of its frame; other bytecode systems also use stack-oriented execution models. An operand stack is conceptually distinct from a call stack: the former holds intermediate computation values, while the latter records active invocations. Implementations may optimize either abstraction into registers or other storage while preserving the specified observable behavior.

Runtime call stacks and control flow

A call stack records active function or procedure invocations. When a function calls another function, execution normally enters the callee before the caller can continue. When the callee returns, the caller resumes. This naturally follows LIFO order. Each active invocation is commonly represented by a stack frame, or activation record, containing some combination of return information, local variables, saved registers, arguments, and bookkeeping. The exact contents and layout depend on the compiler, optimization settings, processor architecture, and application binary interface.

A stack pointer identifies a boundary of the active stack storage. Some systems also use a frame pointer to provide stable access to frame contents, although optimized code may omit it. Many processor conventions make the stack grow toward lower memory addresses, but downward growth is not part of the abstract definition. Nor must every call allocate a conventional memory frame: a leaf function may keep all working state in registers, inlining removes the call boundary altogether, and some calling conventions return through a register until that value must be saved.

Recursion requires distinct state for simultaneously active invocations. If a function recursively processes a chain of depth dd and each invocation needs bounded storage, its call-stack requirement is ordinarily O(d)O(d). A recursive traversal of a balanced binary tree may have logarithmic maximum depth, whereas traversal of a degenerate tree can have linear depth. Converting recursion to iteration often relocates the same pending state into an explicit stack rather than eliminating it. Conversely, a tail call may be implemented by reusing the current frame when the language and implementation permit tail-call elimination.

Nonlocal control flow complicates the simple call-and-return picture. An exception may unwind several frames before reaching a handler; during unwinding, a language runtime may execute cleanup actions and destroy local objects. Debuggers and profilers reconstruct active calls using frame information, unwind metadata, or other implementation-specific mechanisms. Coroutines can suspend an invocation and resume it later, so their state may live in a separate stack or in a heap-allocated state object. Such implementations preserve the required control-flow semantics without requiring all suspended work to occupy one ordinary contiguous call stack.

Runtime stack exhaustion is distinct from a buffer overflow. The former occurs when active execution requires more stack storage than is available, often because of deep recursion or large frame allocations. The latter occurs when a program accesses beyond a buffer’s bounds and may corrupt adjacent memory, including control data if the buffer resides in a stack frame. Guard pages can help detect exhaustion, while bounds checks, stack canaries, and control-flow protections address different aspects of memory corruption. Ordinary stack objects can also be allocated in dynamically managed memory; calling a container a stack does not imply that its elements reside on a thread’s runtime stack.

Interfaces, ownership, and persistent versions

A stack’s interface determines how its abstract behavior fits a language’s type system and memory model. A mutable interface changes one stack object in place. An immutable interface instead returns a new stack value, leaving the old value available. Both can satisfy LIFO semantics. Interfaces also differ in whether they expose references to elements, allow iteration, accept a maximum capacity, or distinguish a failed operation from a stored null value. These choices influence safety and usability even though they do not change the underlying ordering discipline.

Standard libraries illustrate these differences. C++ provides std::stack, a container adaptor whose default underlying container is std::deque; another compatible container can supply its storage. Its top() inspects the current element and pop() removes it without returning it. Java retains the older Stack class, but its collection documentation recommends Deque implementations for LIFO use; ArrayDeque is a common example. In Python, a list supports conventional stack use through append() and pop() at the right-hand end. In JavaScript, arrays provide analogous push() and pop() methods. These broader containers expose operations beyond the minimal stack abstraction.

Ownership becomes important when elements manage resources or when an API returns a reference into internal storage. A growing array may relocate its elements, invalidating pointers or references that previously identified them. Removing an element ends its membership in the stack, but the effects on the underlying object depend on whether the stack stores the object directly, owns it indirectly, or merely holds a shared reference. A failed push also needs defined behavior: if allocation or element construction fails, an implementation may guarantee that the previous stack remains unchanged. Such guarantees concern observable state as well as exception reporting.

An immutable linked stack is a simple example of a persistent data structure. If a stack is represented by a node containing a value and a reference to the remainder, pushing creates one new node pointing to the old stack. Popping returns the referenced remainder rather than modifying a link. Thus multiple stack versions can share most of their storage. For example, two stacks created by independently pushing A and B onto the same previous stack have different top nodes but share the entire earlier sequence.

This representation is common in functional programming, where immutable lists naturally support constant-time access to a head and tail. Sharing is safe only if shared nodes are not destructively changed. It also changes space accounting: removing an element from one version does not make it reclaimable if another reachable version still references it. Garbage collection, reference counting, or another lifetime mechanism must account for all surviving versions. Consequently, constant-time persistent push and pop describe the local structural operations, not an unconditional bound on allocation pauses, reclamation work, or total memory retained by an application.

Concurrent stacks and synchronization

When several threads share a stack, preserving LIFO behavior requires a specification for overlapping operations. A common correctness condition is linearizability: each operation must appear to take effect at one instant between its invocation and completion, and the resulting order must respect the real-time order of nonoverlapping operations. If two pushes overlap, either may be ordered first. If one push has completed before another begins, a later pop must respect that established order unless an intervening operation has removed the relevant element.

A lock-based implementation protects the stack’s state with mutual exclusion. A push, pop, or compound operation enters a critical section, updates or inspects the shared representation, and then releases the lock. Correctly placing the critical-section boundary matters. Separately synchronized isEmpty() and pop() calls do not make the combination “check nonempty, then pop” atomic: another thread may remove the last element between the calls. An interface that combines attempted removal and failure reporting avoids this particular race. Blocking stacks add coordination so that consumers can wait for an element instead of repeatedly checking.

A widely studied nonblocking implementation is R. Kent Treiber’s linked stack, described in 1986. A push reads the current top pointer, makes a new node point to it, and uses compare-and-swap to replace the top only if it still has the expected value. A pop similarly reads the top and its successor, then attempts to replace the top with that successor. If interference causes the comparison to fail, the operation retries using the new state. The successful atomic update supplies a natural linearization point, provided that publication, memory ordering, and node lifetime are handled correctly.

Memory reclamation is one of the central difficulties. A thread may read a pointer just before another thread removes and frees the corresponding node. Reusing the storage can also create the ABA problem: a pointer changes from value A to B and later back to A, causing a comparison to miss intervening changes. Tagged pointers can help distinguish versions, but a version tag alone does not establish that dereferencing a node is safe. Hazard pointers, epoch-based reclamation, and suitable garbage-collected environments address aspects of this lifetime problem under different assumptions. These mechanisms are integral to correctness, not optional performance refinements.

Nonblocking progress guarantees are also distinct from ordering correctness. A lock-free algorithm guarantees system-wide progress under its stated execution assumptions, but an individual operation may repeatedly lose races. A wait-free algorithm provides a bounded number of its own steps for each operation. Neither term means that contention has no cost. A single shared top pointer can become a cache-coherence bottleneck in parallel computing. Elimination techniques allow overlapping pushes and pops to exchange values without visiting that central pointer, while preserving a valid abstract order. Their benefit depends on workload balance, contention, scheduling, and the surrounding memory-management scheme.

Historical development and theoretical foundations

Stack ideas developed from practical needs for temporary storage, expression translation, and returning from subroutines. Friedrich L. Bauer and Klaus Samelson developed influential stack-based methods for formula translation during the 1950s. Charles Hamblin independently advanced stack-oriented expression evaluation and postfix notation during the same decade. These developments connected a simple storage discipline with mechanized handling of nested arithmetic expressions, helping establish stacks as a basic tool in programming-language implementation rather than merely a specialized memory arrangement.

Stack-oriented hardware and languages subsequently made the abstraction more visible. The Burroughs B5000, introduced in 1961, was an influential early commercial computer with a stack-oriented architecture designed around high-level-language execution. Forth, developed by Charles H. Moore, made an explicit data stack central to programming and also employed a separate return stack. Later bytecode systems adopted stack-oriented instruction formats for portable execution. These examples differ substantially in representation and instruction design, but all exploit the ability to refer implicitly to recently produced values or recently established control contexts.

In computation theory, a pushdown automaton is a finite-state machine augmented with a stack. Its transition rules can inspect the current state, an input symbol where applicable, and the top stack symbol, then change state and replace the top symbol with a finite sequence of symbols. The stack supplies potentially unbounded memory while restricting access to one end. This is enough to recognize nested patterns that an ordinary finite-state machine cannot recognize, such as balanced parentheses of arbitrary depth or the language {anbn∣n≥0}\{a^n b^n\mid n\geq0\}.

Nondeterministic pushdown automata recognize exactly the context-free languages, a foundational connection between grammars and machines. Deterministic pushdown automata recognize a proper subset of those languages. The distinction is important for parsing: the existence of a context-free grammar does not imply that every deterministic parsing strategy can process it directly without restrictions or transformation. The theoretical stack is normally unbounded, whereas a physical implementation is finite; theoretical results concern the model’s capabilities rather than an assertion that real memory has unlimited capacity.

Two unbounded stacks change computational power substantially. One can represent the tape to the left of a simulated head and the other the current cell and the tape to its right, transferring symbols as the head moves. With appropriate finite control, this provides the power of a Turing machine. The contrast identifies a precise limitation of one-stack access rather than a limitation of storage volume alone. A single stack may hold arbitrarily many symbols in the model, yet its restricted access order still constrains what the machine can recognize. This relationship between access discipline, nesting, and computational power is one reason the stack remains central both to practical execution systems and to formal language theory.