6. Stack

Introduction to Stacks

A stack is a linear data structure that follows the Last‑In, First‑Out (LIFO) principle: the most recently added element is the first one to be removed. Think of a stack of plates; you can only take the top plate or add a new plate on top. This simple yet powerful model underlies many algorithms and system mechanisms.

In this chapter we will examine:

• The fundamental stack operations and their time complexities.
• Two common concrete implementations: using a fixed‑size array and using a singly linked list.
• Real‑world applications that rely on stack behavior, including browser navigation, undo/redo functionality, function call handling, and expression evaluation.

Core Operations

Regardless of the underlying representation, a stack supports four primary operations, each achievable in O(1) constant time:

1. push(x) – Place element x on top of the stack.
2. pop() – Remove and return the top element; if the stack is empty, this operation signals an underflow condition.
3. peek() / top() – Return the value of the top element without removing it.
4. isEmpty() – Check whether the stack contains any elements; returns true for an empty stack.

Because each operation touches only the top element, no traversal of the structure is required, guaranteeing constant‑time performance.

Array‑Based Implementation

When a maximum capacity is known in advance, an array provides a simple and cache‑friendly storage mechanism.

Data Layout

• arr[0 … capacity‑1] – The underlying static array.
• top – Integer index indicating the position of the next free slot (i.e., where the next pushed element will be stored). Initially top = -1 for an empty stack.

Push Operation

To insert x:

if (top == capacity - 1) {
    // overflow: stack is full
    throw new OverflowException();
}
arr[++top] = x;   // increment top then store

The expression arr[++top] = x first increments top (making it point to the next free cell) and then stores x at that location.

Pop Operation

To retrieve and remove the top element:

if (top == -1) {
    // underflow: stack is empty
    throw new UnderflowException();
}
int value = arr[top--];   // read then decrement top
return value;

Peek and isEmpty

int peek() { return arr[top]; }   // assumes !isEmpty()
boolean isEmpty() { return top == -1; }

Overflow Condition

Overflow occurs when top == capacity‑1, meaning the array is completely filled and no further pushes can be accommodated without resizing (which would break the fixed‑capacity guarantee).

Advantages and Disadvantages

Linked‑List Implementation

When the maximum number of elements is unknown or may vary dramatically, a singly linked list offers dynamic growth without a predefined capacity limit.

Node Structure

struct>Node { int data; Node* next; }
The stack maintains a reference head to the node that represents the top of the stack.
Push Operation
Creating a new node and linking it in front of the current head:
Node* newNode = new Node();
newNode->data = x;
newNode->next = head;   // new node points to old head
head = newNode;         // head now points to the new node

Pop Operation
Removing the node pointed to by head:
if (head == nullptr) {
    // underflow
    throw new UnderflowException();
}
int value = head->data;
Node* temp = head;
head = head->next;      // bypass the node to be removed
delete temp;            // free memory
return value;

Peek and isEmpty
int peek() { return head->data; }   // assumes !isEmpty()
boolean isEmpty() { return head == nullptr; }

Advantages and Disadvantages


Aspect
Linked‑List Implementation


Memory overhead
Higher due to storage of a pointer per node
Access speed
Still O(1) but involves pointer chasing; slightly slower than array due to cache misses
Flexibility
Dynamic size; limited only by available system memory
Overflow
No fixed‑capacity overflow; only possible underflow when popping from an empty stack



Applications of Stacks
The LIFO property makes stacks ideal for scenarios where the most recent item must be processed first. Below we discuss four classic use cases.

Browser Back Button
Web browsers maintain a stack of visited URLs. Each time the user navigates to a new page, the URL is pushed onto the stack. When the user clicks the Back button, the browser pops the top URL, restoring the previous page.

Example sequence:

Visit A.com → push A.com
Navigate to B.com → push B.com
Navigate to C.com → push C.com
Press Back → pop → current page = B.com
Press Back again → pop → current page = A.com


If the stack becomes empty, the Back button is disabled.

Undo Feature
Many text editors and graphic applications implement undo by storing each user action on a stack. Performing an action pushes a description (or inverse operation) onto the stack. Selecting Undo pops the most recent action and applies its inverse, effectively reverting the state.
Redo can be supported with a second stack: popped actions from the undo stack are pushed onto a redo stack, allowing the user to re‑apply undone steps.

Function Calls and the Call Stack
During program execution, the runtime maintains a call stack (also known as the execution stack). Each time a function is invoked:

The return address (where execution should resume after the function finishes) is pushed.
Function parameters and local variables are allocated space, often also pushed.

When the function returns, the top frame is popped, restoring the previous execution context.
Recursive functions rely heavily on the call stack; deep recursion can exhaust stack space, leading to a stack overflow error. This illustrates the practical limit of stack size in many systems.

Expression Evaluation
Stacks are central to both converting infix expressions to postfix (Reverse Polish Notation) and evaluating postfix expressions.
Infix to Postfix – Shunting Yard Algorithm
The algorithm scans the infix token stream and uses an operator stack to reorder operators according to precedence and associativity.

Operands are sent directly to the output queue.
When an operator op1 is read:

While there is an operator op2 at the top of the stack with higher precedence, or equal precedence and left‑associative, pop op2 to the output.
Push op1 onto the operator stack.

Left parenthesis ( is pushed; right parenthesis ) causes popping until a matching ( is found.

After processing all tokens, any remaining operators are popped to the output.
Postfix Evaluation
Evaluating a postfix expression employs an operand stack:

Scan tokens left to right.
If the token is an operand, push it onto the stack.
If the token is an operator, pop the required number of operands (two for binary operators), apply the operator, and push the result back.
At the end, the stack contains a single value – the expression result.

Example: Evaluate the postfix expression 2 3 + 4 *

Push 2 → stack: [2]
Push 3 → stack: [2, 3]
Encounter +: pop 3, pop 2, compute 2+3=5, push 5 → stack: [5]
Push 4 → stack: [5, 4]
Encounter *: pop 4, pop 5, compute 5*4=20, push 20 → stack: [20]
Result: 20

Both conversion and evaluation run in linear time O(n) with respect to the number of tokens, and each stack operation remains O(1).

Summary
We have examined the stack abstract data type from its theoretical foundations to concrete implementations and practical applications. Key takeaways include:

Stacks support push, pop, peek, and isEmpty in constant time.
Array‑based stacks offer low overhead and excellent cache performance but require a predefined capacity and overflow handling.
Linked‑list stacks provide dynamic size at the cost of extra memory per node and slightly slower access due to pointer indirection.
Real‑world systems—web browsers, editors, language runtimes, and calculators—rely on stacks to manage history, state, control flow, and expression processing.

Understanding stacks equips you with a versatile tool for solving a wide range of algorithmic problems and for appreciating the inner workings of many software systems.