Stacks, Expression Processing and Call Frames

A stack is a linear abstract data type in which insertion and removal take place at one distinguished end called the top. The most recently inserted item is the first item removed. This ordering is known as last in, first out or LIFO. A stack describes behavior rather than a particular storage technique: the same operations can be implemented with an array, a linked list or another suitable structure.

A useful physical model is a pile of plates. A new plate is placed on top and the next available plate is removed from the top. Items below the top remain inaccessible until the items above them have been removed. This restricted access is precisely what makes a stack useful. It automatically remembers items in reverse order and therefore supports nested work, reversal, backtracking, expression processing and function calls.

The Stack Abstract Data Type

The essential stack operations are:

• push(x) inserts x at the top.
• pop() removes and returns the top item.
• peek() or top() returns the top item without removing it.
• isEmpty() reports whether the stack contains no items.
• size() returns the number of stored items.

Some interfaces also provide clear(), which removes every item or isFull(), which is meaningful for a fixed-capacity implementation. If A, B and C are pushed in that order, the stack from bottom to top is A, B, C. Three successive pops return C, then B, then A.

The LIFO rule is the central invariant. A correct implementation must ensure that pop removes exactly the item returned by peek and that a push followed immediately by a pop restores the previous logical contents. The public interface should also define what happens when an invalid operation is requested. Popping or peeking at an empty stack is underflow. Pushing into a full fixed array is overflow. An implementation may throw an exception, return a status value or grow its storage, but the contract must be unambiguous.

For n stored items, a conventional stack requires O(n) space. Push, pop, peek and emptiness testing should take O(1) time. A dynamically resized array has occasional costly resizing operations, but its push operation is still O(1) amortized.

Array Representation

An array stack stores items in consecutive array positions and maintains an integer that identifies the logical top. One common convention initializes top to -1. The stack is empty when top == -1 and its size is top + 1. A push first checks capacity, increments top and writes the new value into items[top]. A pop reads items[top], clears that position when references are stored, decrements top and returns the saved value.

For an array of capacity c, the last valid index is c - 1; therefore, the stack is full when top == c - 1. Another valid convention stores the number of elements rather than the last occupied index. In that design, size == 0 means empty, the next insertion uses items[size] and fullness means size == capacity. Both conventions work, but mixing their formulas causes off-by-one errors.

The array portion from index 0 through top contains the logical stack and positions above top do not. That statement is the representation invariant. An operation must preserve it. For example, a pop must not decrement top before saving the item unless it subsequently reads the old location correctly.

When the array stores object references, a removed position should normally be assigned null. Changing top makes the position logically unused, but the stale reference may still prevent garbage collection of the object. Clearing the slot removes this unnecessary retention.

A fixed array offers predictable memory use and no resizing pauses, but it has a hard capacity. A dynamic array removes that restriction. When full, it allocates a larger array, commonly twice the old capacity and copies the existing elements. A single growth costs O(n), yet geometric growth makes a long sequence of pushes cost linear time overall. Increasing capacity by only one on every overflow would cause repeated copying and quadratic total work.

Array stacks have good cache locality and little per-element overhead. Their unused capacity may waste some space and resizing temporarily requires both old and new arrays. These tradeoffs are often favorable in practice.

Linked Representation

A linked stack represents each item with a node containing a value and a link to the next node. The head reference is used as the top. To push x, create a node whose next link points to the old head and then make the new node the head. To pop, save the head value, move the head to head.next and return the saved value. An empty stack has a null head.

Both operations take O(1) time because no traversal is required. Using the tail of a singly linked list would make removal expensive unless a predecessor were also available. The head is therefore the natural stack end.

A linked stack grows one node at a time and has no fixed logical capacity. It can still fail when memory is exhausted. Each element needs an additional link field and usually a separate allocation, so it has greater memory overhead and poorer locality than an array. It is useful when stable incremental growth matters or when nodes are already part of a larger linked structure.

Balanced Delimiters

Programming languages and mathematical notation use nested delimiter pairs such as (), [] and {}. A valid closing delimiter must match the most recent opening delimiter that has not yet been matched. This is a LIFO relationship.

The checking algorithm scans from left to right. When it sees an opening delimiter, it pushes it. When it sees a closing delimiter, it first verifies that the stack is nonempty. It then pops the latest opening delimiter and checks that the types form a valid pair. Any mismatch or premature closing delimiter makes the input invalid. After the complete scan, the input is balanced only if the stack is empty; remaining openings are unmatched.

For example, {[()]} succeeds because each closer matches the current top. {[(])} fails when ] encounters ( at the top. ()) fails through underflow at the final ), while (() fails because one opening remains. With n characters, the algorithm takes O(n) time and at most O(n) auxiliary space.

Real source-code processing also recognizes that delimiter characters inside strings or comments may not have structural meaning. A full parser combines the stack logic with lexical rules rather than treating every visible bracket alike.

Infix, Prefix and Postfix Expressions

In infix notation, an operator appears between its operands, as in A + B. Familiar infix expressions require precedence, associativity and parentheses to determine evaluation order. Multiplication normally has higher precedence than addition, so A + B * C means A + (B * C). Left-associative subtraction makes A - B - C mean (A - B) - C. Assignment and exponentiation in some languages are right-associative.

In prefix notation, the operator precedes its operands: + A B. In postfix notation, it follows them: A B +. Once the arity of each operator is known, prefix and postfix need no precedence rules or parentheses. The infix expression A + B * C becomes + A * B C in prefix and A B C * + in postfix.

Tokens must be distinguished from characters. The postfix expression 12 3 + has two numeric operands, not three single-digit operands. A practical evaluator first tokenizes the input, recognizing numbers, identifiers, operators and delimiters.

Converting Infix to Postfix

An operator stack temporarily holds operators whose right operands have not yet been fully processed. The output sequence holds the postfix result. The expression is scanned token by token:

1. Send an operand directly to the output.
2. Push an opening parenthesis onto the operator stack.
3. On a closing parenthesis, pop operators to the output until the matching opening parenthesis appears, then discard that opening parenthesis.
4. On an operator, first pop operators that must be performed earlier. Then push the incoming operator.
5. After the input ends, pop all remaining operators. An unmatched parenthesis is an error.

For a left-associative incoming operator, operators of greater or equal precedence are popped. For a right-associative incoming operator, only operators of strictly greater precedence are popped. This difference is essential for operators such as exponentiation. Parentheses act as barriers and do not appear in the final postfix expression.

Consider A + B * C. A goes to output, + is pushed, B goes to output and * is pushed because it has higher precedence than +. After C, the stack is drained, producing A B C * +. With n tokens, every token is pushed and popped at most once, so conversion takes O(n) time and O(n) auxiliary space.

Evaluating Postfix and Prefix Expressions

A postfix evaluator scans left to right. It pushes each operand. On an operator of arity two, it pops the right operand first and the left operand second, computes left operator right and pushes the result. At the end, exactly one value must remain.

For 8 2 - 3 *, push 8, push 2, then apply subtraction to obtain 6. Push 3, apply multiplication and obtain 18. Operand order matters: 8 2 - is 8 - 2, not 2 - 8. Too few operands causes underflow; extra values at the end indicate a malformed expression.

Prefix evaluation uses the same principle in the opposite direction. Scan from right to left. Push operands and when an operator appears, pop its left operand first and right operand second. An alternative is to build an expression tree and evaluate it recursively.

These methods separate parsing order from computation. Compilers use related structures when translating source expressions into syntax trees or intermediate instructions, though full language grammars need more than a basic operator stack.

The Runtime Call Stack

During a function call, the runtime must remember enough information to resume the caller. It creates an activation record, also called a stack frame. A frame may contain arguments, local variables, saved registers, temporary values and a return address. Calling a function pushes a logical frame; returning removes that frame and transfers control to the saved continuation.

Nested calls naturally require LIFO order. If main calls f and f calls g, then g must finish before f can resume and f must finish before main can resume. Each active recursive call has its own frame, so different invocations can hold different parameter and local-variable values.

The runtime call stack and a stack ADT created by an application share LIFO behavior, but they are not the same object. An application stack stores values chosen by the program. The runtime stack supports execution and is managed according to the language and platform implementation.

Deep or nonterminating recursion may exhaust the available call-stack region and cause stack overflow. This differs from overflow of a fixed array stack, although both indicate that a bounded resource has been exceeded. An iterative algorithm with an explicit stack moves the stored state into a program-controlled data structure, which may permit larger workloads but still consumes memory.

Stack-Based Algorithms and Design Choices

Depth-first search uses a stack explicitly or through recursion. Backtracking algorithms push decisions and later return to the most recent unresolved choice. Editors implement undo by recording recent actions; a second stack can support redo. Browsers can model backward and forward navigation with two stacks. Reversing a sequence follows directly from pushing items in original order and popping them in reverse order.

A monotonic stack keeps its elements in increasing or decreasing order while scanning data. It supports problems such as finding the next greater element or the nearest smaller boundary. Each item is pushed once and popped at most once, often giving O(n) time even though a pop loop appears inside the scan.

In Java, ArrayDeque is generally a suitable concrete stack through push, pop and peek. It avoids the legacy synchronization and older design of Stack. A program should use one end consistently and should not insert null, because null would make an absent result ambiguous in deque-style APIs.

Choosing a stack should follow from the access pattern. If work must be removed in the reverse of its arrival order or if the newest unfinished context must be resumed first, LIFO is appropriate. If the oldest item must be served first, a queue is the correct abstraction. A clear interface, a stated empty-stack policy and preserved representation invariants make either array or linked implementations reliable.