Implementing Stacks: Array vs. Linked List

1. The Stack: A Last-In, First-Out (LIFO) Data Structure

A stack is an Abstract Data Type (ADT) that follows a simple but powerful principle: Last-In, First-Out (LIFO). Think of a stack of plates: the last plate you place on top is the first one you take off.

The core operations of a stack are:

• push(item): Adds an item to the top of the stack.
• pop(): Removes and returns the item from the top of the stack.
• peek() (or top()): Returns the top item without removing it.
• isEmpty(): Checks if the stack contains any elements.
• size(): Returns the number of elements in the stack.

To formalize this, let's look at how a Stack interface can be defined in Java. It's good practice to use generics (<T>) to make our stack type-safe, allowing it to hold any type of object without messy casting.

2. Implementation 1: Using an Array

Our first implementation will use an array. The idea is to use an array to store the elements and an integer variable, let's call it top, to keep track of the index of the most recently added element.

Here's the logic:

• Initialization: We create an array of a certain capacity and initialize top = -1 to signify that the stack is empty.
• Push: To push an element, we increment top and then place the new element at array[top]. We must first check if the stack is full (i.e., if top is already at the last index). This is known as a stack overflow condition.
• Pop: To pop an element, we retrieve the element at array[top] and then decrement top. We must first check if the stack is empty (i.e., if top == -1). Attempting to pop from an empty stack is a stack underflow condition.

The following video provides an excellent visual demonstration of this process.

Java Implementation (Array-based)

Here is a complete, generic implementation in Java based on the principles we've discussed.

import java.util.EmptyStackException;

public class ArrayStack<T> {
    private T[] arr;
    private int top;
    private static final int DEFAULT_CAPACITY = 10;

    @SuppressWarnings("unchecked")
    public ArrayStack(int capacity) {
        // Java doesn't allow direct creation of generic arrays.
        // This is a standard workaround.
        arr = (T[]) new Object[capacity];
        top = -1;
    }

    public ArrayStack() {
        this(DEFAULT_CAPACITY);
    }

    // Pushes an element onto the top of the stack. O(1)
    public void push(T element) {
        if (top == arr.length - 1) {
            // In a real-world scenario, you might resize the array here.
            // For this implementation, we'll consider it a fixed-capacity stack.
            throw new StackOverflowError("Stack is full");
        }
        top++;
        arr[top] = element;
    }

    // Removes and returns the element at the top of the stack. O(1)
    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        T element = arr[top];
        arr[top] = null; // Help garbage collection
        top--;
        return element;
    }

    // Returns the element at the top of the stack without removing it. O(1)
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return arr[top];
    }

    // Returns true if the stack is empty. O(1)
    public boolean isEmpty() {
        return top == -1;
    }

    // Returns the number of elements in the stack. O(1)
    public int size() {
        return top + 1;
    }
}

The key advantage of the array implementation is its efficiency. All operations (push, pop, peek, isEmpty, size) are constant time, O(1). The main disadvantage is its fixed size. If you fill the array, you either get an overflow or have to perform a costly resize operation (creating a new, larger array and copying all elements, which is O(n)).

3. Implementation 2: Using a Linked List

Now, let's address the fixed-size limitation by using a linked list. This should feel familiar after your work in the previous module. The head of our linked list will serve as the top of our stack.

Here's the logic:

• Initialization: We have a single reference, top, which initially points to null.
• Push: To push a new element, we create a new Node. We set this new node's next pointer to the current top node, and then we update top to be this new node. This is identical to adding an element to the front of a singly linked list.
• Pop: To pop, we simply move the top pointer to the next node in the list (top = top.next). The old top node is now disconnected and will be garbage collected. We must handle the underflow case where top is null.

Let's watch a video that walks through this implementation.

Java Implementation (Linked List-based)

Here is a complete, generic implementation using a linked list. Notice how it naturally handles dynamic sizing.

import java.util.EmptyStackException;

public class LinkedListStack<T> {

    private class Node {
        T data;
        Node next;

        Node(T data) {
            this.data = data;
        }
    }

    private Node top;
    private int size;

    public LinkedListStack() {
        top = null;
        size = 0;
    }

    // Pushes an element onto the top of the stack. O(1)
    public void push(T element) {
        Node newNode = new Node(element);
        newNode.next = top;
        top = newNode;
        size++;
    }

    // Removes and returns the element at the top of the stack. O(1)
    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        T element = top.data;
        top = top.next;
        size--;
        return element;
    }

    // Returns the element at the top of the stack without removing it. O(1)
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return top.data;
    }

    // Returns true if the stack is empty. O(1)
    public boolean isEmpty() {
        return top == null;
    }

    // Returns the number of elements in the stack. O(1)
    public int size() {
        return size;
    }
}

Like the array version, all operations are O(1). The major advantage is that the stack can grow and shrink dynamically without any expensive resizing operations. The trade-off is slightly higher memory usage, as each element requires a Node object which stores both the data and a next reference.

4. Comparing the Implementations

Both implementations are valid and efficient, but they are suited for different scenarios. Your choice depends on whether you know the maximum size of your data beforehand and how you want to manage memory.

In practice, for competitive programming and general use in Java, java.util.ArrayDeque is often preferred over the legacy java.util.Stack class (which is Vector-based and synchronized) when a stack implementation is needed. However, understanding how to build one from scratch is a crucial skill.

Conclusion

Great work! You have successfully learned how to implement one of the most fundamental data structures, the stack, using two different approaches.

Key Takeaways:

• A stack is a LIFO (Last-In, First-Out) data structure with push, pop, and peek as its main operations.
• An array-based stack is fast and memory-efficient but has a fixed size, leading to potential overflow. It uses an index top to manage the stack.
• A linked-list-based stack is dynamic and flexible, avoiding overflow issues. It uses a top (or head) reference to manage the stack by adding and removing nodes from the front of the list.
• Both implementations provide O(1) time complexity for all core operations. The choice between them involves a trade-off between memory management (fixed vs. dynamic) and performance characteristics (cache locality).

Preview of the next lesson:
Now that you can build a stack, it's time to use it. In the next lesson, we will solve the classic "balanced parentheses" problem. It's a perfect first application that showcases the power of the stack's LIFO property and is a very common question in technical interviews.