Stacks from Scratch

IB Syllabus: B4.1.1 (HL) – Explain the properties and purpose of ADTs in programming. Implement a stack as an ADT using linked list nodes.

This page is HL only.

---

Key Concepts

In Stacks you learned to use Java’s built-in Stack class – calling push, pop, and peek without worrying about how they work inside. On this page you will build a stack from scratch using linked list nodes, understanding every line of the implementation.

Using vs Building

Aspect	Using (B2.2.3)	Building (B4.1.1)
Code	Stack<String> s = new Stack<>();	Write your own LinkedStack class
Focus	What operations are available	How operations work internally
Knowledge	Interface only	Interface + implementation
Node class	Hidden inside Java library	You write it yourself

Stack Operations Recap

A stack follows the LIFO (Last In, First Out) principle:

Operation	Description	Time
push(item)	Add item to the top	O(1)
pop()	Remove and return item from the top	O(1)
peek()	View the top item without removing it	O(1)
isEmpty()	Check if the stack has no elements	O(1)
size()	Return the number of elements	O(1)

Why Use a Linked List?

A stack built with a linked list has no fixed capacity – it grows and shrinks dynamically. Each push creates a new node; each pop removes one. The top of the stack is the head of the linked list, so all operations are O(1) with no shifting.

An array-based stack is also possible but requires choosing a capacity upfront. If the array fills up, you must create a larger array and copy all elements – an expensive operation that a linked list avoids entirely.

---

Worked Examples

Example 1: LinkedStack Implementation

public class LinkedStack {
    private Node top;    // head of the linked list = top of stack
    private int count;

    public LinkedStack() {
        top = null;
        count = 0;
    }

    // Push: add to the top (front of linked list)
    public void push(String item) {
        Node newNode = new Node(item);
        newNode.next = top;
        top = newNode;
        count++;
    }

    // Pop: remove and return from the top
    public String pop() {
        if (top == null) {
            System.out.println("Stack is empty");
            return null;
        }
        String data = top.data;
        top = top.next;
        count--;
        return data;
    }

    // Peek: view top without removing
    public String peek() {
        if (top == null) {
            System.out.println("Stack is empty");
            return null;
        }
        return top.data;
    }

    public boolean isEmpty() {
        return top == null;
    }

    public int size() {
        return count;
    }

    public void printStack() {
        System.out.print("TOP -> ");
        Node current = top;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        LinkedStack stack = new LinkedStack();
        stack.push("Red");
        stack.push("Green");
        stack.push("Blue");

        stack.printStack();
        System.out.println("Peek: " + stack.peek());
        System.out.println("Size: " + stack.size());

        System.out.println("Pop: " + stack.pop());
        System.out.println("Pop: " + stack.pop());
        stack.printStack();
        System.out.println("Size: " + stack.size());
    }
}

# The Node class from the Linked Lists page
class Node():
    def __init__(self, data):
        self.data = data    # the value this node stores
        self.next = None    # reference to the next node

class LinkedStack():
    def __init__(self):
        self._top = None    # head of the linked list = top of stack
        self._count = 0     # the leading underscore marks these as private (IB convention)

    # Push: add to the top (front of linked list)
    def push(self, item):
        new_node = Node(item)
        new_node.next = self._top
        self._top = new_node
        self._count = self._count + 1

    # Pop: remove and return from the top
    def pop(self):
        if self._top == None:
            print("Stack is empty")
            return None
        data = self._top.data
        self._top = self._top.next
        self._count = self._count - 1
        return data

    # Peek: view top without removing
    def peek(self):
        if self._top == None:
            print("Stack is empty")
            return None
        return self._top.data

    def isEmpty(self):
        return self._top == None

    def size(self):
        return self._count

    def print_stack(self):
        print("TOP -> ", end="")
        current = self._top
        while current != None:
            print(current.data + " -> ", end="")
            current = current.next
        print("null")    # printed as text -- it marks the end of the chain

stack = LinkedStack()
stack.push("Red")
stack.push("Green")
stack.push("Blue")

stack.print_stack()
print("Peek:", stack.peek())
print("Size:", stack.size())

print("Pop:", stack.pop())
print("Pop:", stack.pop())
stack.print_stack()
print("Size:", stack.size())

Output:

TOP -> Blue -> Green -> Red -> null
Peek: Blue
Size: 3
Pop: Blue
Pop: Green
TOP -> Red -> null
Size: 1

Notice: push is identical to addToFront in a singly linked list. pop removes the head and returns its data. Both are O(1) – no traversal needed.

Example 2: Bracket Matching

A classic stack application: checking whether parentheses are balanced.

public class BracketChecker {
    public static boolean isBalanced(String expression) {
        LinkedStack stack = new LinkedStack();

        for (int i = 0; i < expression.length(); i++) {
            char ch = expression.charAt(i);

            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(String.valueOf(ch));
            } else if (ch == ')' || ch == ']' || ch == '}') {
                if (stack.isEmpty()) {
                    return false;  // closing bracket with no opener
                }
                String opener = stack.pop();
                if (!matches(opener.charAt(0), ch)) {
                    return false;  // mismatched pair
                }
            }
        }
        return stack.isEmpty();  // true if all openers were matched
    }

    private static boolean matches(char open, char close) {
        return (open == '(' && close == ')')
            || (open == '[' && close == ']')
            || (open == '{' && close == '}');
    }

    public static void main(String[] args) {
        System.out.println(isBalanced("((a + b) * c)"));
        System.out.println(isBalanced("{[()]}"));
        System.out.println(isBalanced("(a + b]"));
        System.out.println(isBalanced("((())"));
    }
}

# Python has no char type -- each character is just a one-letter string
def is_balanced(expression):
    stack = LinkedStack()

    for i in range(len(expression)):
        ch = expression[i]

        if ch == "(" or ch == "[" or ch == "{":
            stack.push(ch)
        elif ch == ")" or ch == "]" or ch == "}":
            if stack.isEmpty():
                return False    # closing bracket with no opener
            opener = stack.pop()
            if matches(opener, ch) == False:
                return False    # mismatched pair
    return stack.isEmpty()      # True if all openers were matched

def matches(opener, closer):
    return (opener == "(" and closer == ")") \
        or (opener == "[" and closer == "]") \
        or (opener == "{" and closer == "}")

# Python prints booleans capitalised (True/False) -- Java prints true/false
print(is_balanced("((a + b) * c)"))
print(is_balanced("{[()]}"))
print(is_balanced("(a + b]"))
print(is_balanced("((())"))

Output:

true
true
false
false

Each opening bracket is pushed onto the stack. Each closing bracket pops the most recent opener and checks if they match. If the stack is empty at the end, every opener was matched.

Example 3: Reversing a String

Since a stack is LIFO, pushing characters and then popping them produces the reverse order.

public static String reverse(String input) {
    LinkedStack stack = new LinkedStack();
    for (int i = 0; i < input.length(); i++) {
        stack.push(String.valueOf(input.charAt(i)));
    }
    String result = "";
    while (!stack.isEmpty()) {
        result += stack.pop();
    }
    return result;
}

// reverse("HELLO") returns "OLLEH"

def reverse(text):    # "text", not "input" -- input is a built-in function in Python
    stack = LinkedStack()
    for i in range(len(text)):
        stack.push(text[i])
    result = ""
    while stack.isEmpty() == False:
        result = result + stack.pop()
    return result

# reverse("HELLO") returns "OLLEH"

---

Quick Code Check

Q1. In a linked-list-based stack, which node represents the top of the stack?

Q2. The push operation on a linked stack is equivalent to which linked list operation?

Q3. What advantage does a linked-list stack have over an array-based stack?

Q4. What should pop() do if the stack is empty?

Q5. What is the time complexity of push, pop, and peek in a linked stack?

---

Trace Exercise

Trace the stack state after each operation.

LinkedStack s = new LinkedStack();
s.push("A");
s.push("B");
s.push("C");
s.pop();
s.push("D");
s.pop();

s = LinkedStack()
s.push("A")
s.push("B")
s.push("C")
s.pop()
s.push("D")
s.pop()

After operation	top (peek)	Stack (top to bottom)	size()
push("A")		A	1
push("B")			2
push("C")		C, B, A
pop() returns C			2
push("D")		D, B, A	3
pop() returns D

---

Code Completion

Complete the push method for a linked stack.

Fill in the blanks to add an item to the top of the stack:

public void push(String item) {
    Node newNode = new (item);
    newNode. = top;
     = newNode;
    count++;
}

---

Complete the pop method.

Fill in the blanks to remove and return the top item:

public String pop() {
    if (top == null) {
        return null;
    }
    String data = top.;
    top = top.;
    --;
    return data;
}

---

Spot the Bug

This push method causes an infinite loop when printing the stack:

1public void push(String item) { 2 Node newNode = new Node(item); 3 count++; 4 top = newNode; 5 newNode.next = top; 6}

Pick the correct fix:

---

This pop method returns the wrong item (the second item instead of the top):

1public String pop() { 2 if (top == null) { 3 return null; 4 } 5 top = top.next; 6 String data = top.data; 7 count--; 8 return data; 9}

Pick the correct fix:

---

Output Prediction

What does this code print?

LinkedStack s = new LinkedStack();
s.push("10");
s.push("20");
s.push("30");
System.out.println(s.pop());
s.push("40");
System.out.println(s.peek());
System.out.println(s.pop());
System.out.println(s.pop());

Type the exact output:

---

What does this code print?

LinkedStack s = new LinkedStack();
String word = "HELLO";
for (int i = 0; i < word.length(); i++) {
    s.push(String.valueOf(word.charAt(i)));
}
String result = "";
while (!s.isEmpty()) {
    result += s.pop();
}
System.out.println(result);

Type the exact output:

---

Practice Exercises

Core

1. Build and test – Create a LinkedStack, push 5 items, print the stack, pop 3 items (printing each popped value), then print the remaining stack. Verify the LIFO order.
2. isEmpty and size – Push 3 items, check isEmpty() (should be false) and size() (should be 3). Pop all items. Check isEmpty() (should be true) and size() (should be 0). Try pop() on the empty stack and verify it returns null.
3. Compare with java.util.Stack – Write a program that performs the same 10 operations on both your LinkedStack and java.util.Stack<String>. Verify both produce identical results for every operation.

Extension

1. Array-based stack – Implement a stack using a String[] array with a fixed capacity. Maintain a topIndex variable. Compare with the linked version: what happens when the array is full? What are the trade-offs?
2. Undo system – Build a simple text editor undo system. Each edit (a String describing the action) is pushed onto a stack. An undo() method pops the most recent action and prints “Undoing: [action]”. Test with 5 edits and 3 undos.

Challenge

1. Postfix evaluator – Write a method that evaluates a postfix (Reverse Polish Notation) expression like "3 4 + 2 *". Split by spaces, push numbers, and when you encounter an operator, pop two operands, compute, and push the result. Test with "5 3 + 8 2 - *" (expected result: 48).
2. Min stack – Design a stack that supports push, pop, peek, and getMin (return the minimum element) all in O(1) time. Hint: use two stacks – one for the data and one to track the current minimum at each level.

---

Connections

• Prerequisites: Linked Lists – Node class and addToFront/removeHead operations
• Prerequisites: Stacks – using the Stack ADT (B2.2.3)
• Related: Queues from Scratch – the FIFO counterpart, also built with nodes
• Next: Queues from Scratch – building a queue using linked list nodes