Stack Implementations (Array-based, Linked List-based)

Stack Implementations: Array-based vs. Linked List-based

Now that we understand the theoretical LIFO principle and core operations of a stack, let's explore how to bring these concepts to life in code. There are two primary ways to implement a stack: using arrays and using linked lists. Each has its own advantages and disadvantages.

---

1. Array-based Stack Implementation

An array provides a straightforward way to implement a stack, especially when you have a general idea of the maximum number of elements the stack might hold. The "top" of the stack can be represented by the last element in the array.

• Concept:

  • Maintain an underlying array (or dynamic array/list in languages that support it).
  • Keep track of an index or pointer (top or size) that indicates the position of the last element (the top of the stack).

• Illustration:

  Stack: []
  Push(10)
  Stack: [10]
  Push(20)
  Stack: [10, 20]
  Push(30)
  Stack: [10, 20, 30]  <- top
  Pop()
  Stack: [10, 20]     <- top (30 was removed)
  

• JavaScript Example (using Array's built-in methods):

  JavaScript's Array type naturally supports stack-like operations with push() and pop().

  class ArrayStack {
    constructor() {
      this.items = []; // The underlying array
    }
  
    // Add an element to the top of the stack
    push(element) {
      this.items.push(element); // Uses Array's push to add to the end
    }
  
    // Remove and return the top element
    pop() {
      if (this.isEmpty()) {
        return "Underflow"; // Stack is empty
      }
      return this.items.pop(); // Uses Array's pop to remove from the end
    }
  
    // Return the top element without removing it
    peek() {
      if (this.isEmpty()) {
        return "Stack is empty";
      }
      return this.items[this.items.length - 1]; // Access the last element
    }
  
    // Check if the stack is empty
    isEmpty() {
      return this.items.length === 0;
    }
  
    // Return the number of elements in the stack
    size() {
      return this.items.length;
    }
  
    // For demonstration (not a standard stack operation)
    printStack() {
      let str = "";
      for (let i = 0; i < this.items.length; i++) {
        str += this.items[i] + " ";
      }
      console.log(str.trim());
    }
  }
  
  // Example Usage:
  const stack = new ArrayStack();
  stack.push(10);
  stack.push(20);
  stack.push(30);
  console.log("Stack elements:", stack.items); // [10, 20, 30]
  console.log("Top element:", stack.peek()); // 30
  console.log("Popped element:", stack.pop()); // 30
  console.log("Stack elements after pop:", stack.items); // [10, 20]
  console.log("Is stack empty?", stack.isEmpty()); // false
  console.log("Stack size:", stack.size()); // 2
  

• Time Complexity:

  • push(): O(1) on average. If the underlying array needs to resize (e.g., in a dynamic array), it can be O(N) in the worst case, but amortized O(1).
  • pop(): O(1)
  • peek(): O(1)
  • isEmpty(): O(1)
  • size(): O(1)

• Advantages:

  • Simplicity: Very easy to implement, especially with built-in array methods.
  • Cache Locality: Elements are stored contiguously in memory, which can lead to better performance due to CPU caching.
  • Space Efficiency: Generally more memory-efficient than linked lists for storing elements themselves (no extra pointers per element).

• Disadvantages:

  • Fixed Size (for static arrays): If using a static array, the stack has a fixed maximum capacity. If you try to push beyond this, you'll get an "overflow" error.
  • Resizing Overhead (for dynamic arrays): While dynamic arrays can grow, resizing involves allocating new memory and copying all existing elements, which is an O(N) operation and can be costly if it happens frequently.

---

2. Linked List-based Stack Implementation

A linked list provides a flexible alternative for implementing a stack. In this approach, the "top" of the stack is always represented by the head of the linked list.

• Concept:

  • Each element is a Node containing data and a reference (next) to the subsequent node.
  • The head of the linked list points to the top of the stack.
  • push involves adding a new node at the head.
  • pop involves removing the head node.

• Illustration:

  Stack (empty): head -> null
  Push(10): 10 -> null (head points to 10)
  Push(20): 20 -> 10 -> null (head points to 20)
  Push(30): 30 -> 20 -> 10 -> null (head points to 30) <- top
  Pop(): (removes 30) 20 -> 10 -> null (head points to 20) <- top
  

• JavaScript Example (using a simple Node class):

  class Node {
    constructor(value) {
      this.value = value;
      this.next = null;
    }
  }
  
  class LinkedListStack {
    constructor() {
      this.head = null; // Represents the top of the stack
      this.size = 0;
    }
  
    // Add an element to the top (front) of the list
    push(element) {
      const newNode = new Node(element);
      newNode.next = this.head; // New node points to the current head
      this.head = newNode; // Head now points to the new node
      this.size++;
    }
  
    // Remove and return the top (front) element
    pop() {
      if (this.isEmpty()) {
        return "Underflow";
      }
      const removedValue = this.head.value;
      this.head = this.head.next; // Move head to the next node
      this.size--;
      return removedValue;
    }
  
    // Return the top (front) element without removing it
    peek() {
      if (this.isEmpty()) {
        return "Stack is empty";
      }
      return this.head.value;
    }
  
    // Check if the stack is empty
    isEmpty() {
      return this.size === 0;
    }
  
    // Return the number of elements in the stack
    getSize() {
      return this.size;
    }
  
    // For demonstration (not a standard stack operation)
    printStack() {
      let current = this.head;
      let str = "";
      while (current) {
        str += current.value + " ";
        current = current.next;
      }
      console.log(str.trim());
    }
  }
  
  // Example Usage:
  const linkedStack = new LinkedListStack();
  linkedStack.push("A");
  linkedStack.push("B");
  linkedStack.push("C");
  console.log("Linked Stack elements (top to bottom):");
  linkedStack.printStack(); // C B A
  console.log("Top element:", linkedStack.peek()); // C
  console.log("Popped element:", linkedStack.pop()); // C
  console.log("Linked Stack elements after pop:");
  linkedStack.printStack(); // B A
  console.log("Is linked stack empty?", linkedStack.isEmpty()); // false
  console.log("Linked stack size:", linkedStack.getSize()); // 2
  

• Time Complexity:

  • push(): O(1) (always just updating the head pointer).
  • pop(): O(1) (always just updating the head pointer).
  • peek(): O(1)
  • isEmpty(): O(1)
  • getSize(): O(1) (if size is maintained).

• Advantages:

  • Dynamic Size: Can grow or shrink as needed without the overhead of resizing, as memory is allocated dynamically for each node.
  • No Overflow Issues: As long as memory is available, you won't encounter an "overflow" error due to fixed capacity.

• Disadvantages:

  • Memory Overhead: Each node requires extra memory to store the pointer to the next node, which can be less space-efficient than an array for a large number of small elements.
  • Cache Performance: Elements are not stored contiguously, which can sometimes lead to poorer cache performance compared to arrays.

---

3. Choosing the Right Implementation

The choice between an array-based and a linked list-based stack depends on your specific requirements:

Feature	Array-based Stack	Linked List-based Stack
Size	Fixed (static) or Dynamic (if resizable)	Dynamic, grows/shrinks naturally
Memory	Less overhead per element	More overhead per element (for pointers)
Performance	Good cache locality; O(N) for resizing	No resizing overhead; poorer cache locality
Use Case	When max size is known or bounded	When unpredictable size changes are common
Simplicity	Very simple with built-in array methods	Requires custom Node class

In JavaScript, where arrays are dynamic by default, the array-based implementation is often the simplest and most performant choice for general-purpose stacks, as the underlying array handles resizing efficiently. However, understanding the linked list implementation is crucial for grasping the fundamental differences in how data structures manage memory and connectivity.

---

Tip: For languages with built-in dynamic arrays (like JavaScript's Array, Python's list, Java's ArrayList), using them directly for stack operations (push/pop or equivalent append/remove from end) is often the most practical and efficient approach due to their optimized internal implementations.