3.3 Implementation of Stacks and Queues using Arrays and Linked Lists

Array-based and Linked List-based Implementations of Stacks and Queues

Stacks with arrays vs linked lists

Both array-based and linked list-based stacks support the same operations (push, pop, peek), but they differ in how they manage memory under the hood. Your choice depends on whether you know the maximum size ahead of time and how much you care about memory overhead.

Array-based stack uses a fixed-size array and a top variable that tracks the index of the topmost element. Pushing increments top and places the element; popping reads the element at top and decrements it.

• Advantages
  • Straightforward implementation
  • Constant time ($O(1)$) access to elements by index
  • Memory-efficient since no extra space is needed for pointers
  • Better cache locality because elements sit in contiguous memory
• Disadvantages
  • Fixed size can cause stack overflow if the array fills up
  • Wastes memory if you allocate a large array but only use a fraction of it
  • Resizing (if supported) requires copying all elements to a new array, which costs $O(n)$

Linked list-based stack uses a singly linked list where the head of the list acts as the top of the stack. Pushing inserts a new node at the head; popping removes the head node.

• Advantages
  • Dynamic size, so the stack grows and shrinks as needed
  • No overflow (as long as the system has free memory)
  • No wasted capacity since each node is allocated only when needed
• Disadvantages
  • Each node carries extra memory overhead for its pointer (typically 4 or 8 bytes per node)
  • Nodes are scattered in memory, so cache performance is worse than arrays
  • Slightly more complex to implement due to pointer management

Queues with arrays vs linked lists

Queues add at the rear and remove from the front (FIFO). The tricky part with an array-based queue is that naive implementations waste space as the front index advances. That's why array-based queues almost always use a circular array design.

Array-based queue (circular) uses a fixed-size array with two indices, front and rear, that wrap around using modular arithmetic. For example, the next position after index $i$ is $(i + 1) \mod n$, where $n$ is the array capacity. This prevents the "used-up front slots" problem.

• Advantages
  • Straightforward once you understand the wrap-around logic
  • Constant time ($O(1)$) enqueue and dequeue
  • Memory-efficient with no pointer overhead
• Disadvantages
  • Fixed size can cause queue overflow if the array fills up
  • You need to decide the capacity upfront (or implement costly resizing)
  • Distinguishing between "full" and "empty" requires care (common approach: track a size counter, or keep one slot unused)

Linked list-based queue uses a singly linked list with a front pointer (for dequeue) and a rear pointer (for enqueue). Enqueue appends a new node at rear; dequeue removes the node at front.

• Advantages
  • Dynamic size with no overflow concern
  • Memory is allocated per element, so nothing is wasted
  • No wrap-around logic needed
• Disadvantages
  • Extra memory for pointers in every node
  • Worse cache locality than arrays
  • Must handle the edge case where front and rear both point to the same node (single-element queue)

Performance of stack and queue implementations

Both implementations achieve the same time complexity for core operations, so the real differences come down to memory behavior and constant factors.

A few things worth noting:

• Array-based push is $O(1)$ amortized if you support dynamic resizing (doubling the array when full). Individual resizes cost $O(n)$, but averaged over many operations it stays $O(1)$.
• Linked list operations have slightly higher constant overhead due to memory allocation on each push/enqueue and deallocation on each pop/dequeue.
• Array-based structures tend to perform better in practice because of CPU cache effects, even though the Big-O is identical.

Error handling in stacks and queues

Robust implementations need to handle edge cases gracefully. Here are the main ones to watch for:

• Underflow (empty stack/queue): Always check if the structure is empty before calling pop or dequeue. If it's empty, throw an exception or return a sentinel value depending on your language and design.
• Overflow (array-based only): Check if the structure is full before push or enqueue. Either throw an exception, or resize the underlying array if your implementation supports it.
• Null elements: Decide upfront whether your stack or queue allows null values. If it does, you can't use null as a "not found" return value for pop/dequeue, so you'll need exceptions or wrapper types instead.
• Concurrent access: If multiple threads share a stack or queue, you need synchronization (locks, semaphores, or lock-free designs) to prevent race conditions. Without it, two threads could pop the same element or corrupt internal pointers.