Course contentsShow
← Computer Science
Lesson 2578 of 2,87257. Concurrency FundamentalsFree lesson

Concurrent Queue: Array-Based Implementation

Building a thread-safe queue using arrays with head/tail pointers and synchronization primitives.

Concurrent Queue: Array-Based Implementation

You'll learn how to build a thread-safe queue using a fixed-size array with synchronized head and tail pointers.

The Core Idea

A concurrent queue allows multiple threads to safely enqueue and dequeue elements simultaneously. The array-based approach uses a circular buffer with two pointers: one tracking where to insert (tail) and one tracking where to remove (head). The challenge is preventing race conditions when multiple threads try to access or modify these pointers at the same time.

How It Works

Imagine a circular parking lot with entrance and exit gates. The "head" pointer marks the exit gate, the "tail" marks the entrance. Cars (data) enter at the tail and leave at the head. Without coordination, two cars might try to park in the same spot, or someone might try to leave through a spot that's already empty.

To prevent chaos, you need locks or atomic operations on critical operations:

  • Enqueue: Atomically claim the tail position, write data, then advance tail
  • Dequeue: Atomically claim the head position, read data, then advance head

The circular nature means when pointers reach the array's end, they wrap around to index 0 (using modulo arithmetic). You must also handle the queue-full condition (tail catches up to head) and queue-empty condition (head equals tail).

Synchronization Approach

You typically use either:

  • Single lock protecting both operations (simpler, less concurrent)
  • Two locks (one for head, one for tail) allowing simultaneous enqueue/dequeue
  • Atomic operations with compare-and-swap for lock-free variants

The array-based design offers predictable memory usage and cache-friendly access patterns compared to linked structures.

Key Takeaway: Array-based concurrent queues use synchronized head/tail pointers on a circular buffer to enable thread-safe producer-consumer patterns with bounded memory and good cache locality.