Queue using Set of Fixed-Length Arrays

Problem

Implement a queue using a set of fixed-length arrays.

The queue should support enqueue, dequeue, and get_size operations.

Examples

Example 1:

Input:
Operations: ["enqueue(1)", "enqueue(2)", "enqueue(3)", "dequeue()", "get_size()"]
Output: [null, null, null, 1, 2]
Explanation:
1. Enqueue 1: Queue becomes [1]
2. Enqueue 2: Queue becomes [1, 2]  
3. Enqueue 3: Queue becomes [1, 2, 3]
4. Dequeue: Remove 1, queue becomes [2, 3]
5. get_size(): Returns 2

Example 2:

Input: (with segment size = 2)
Operations: ["enqueue(1)", "enqueue(2)", "enqueue(3)", "enqueue(4)", "dequeue()", "dequeue()"]
Output: [null, null, null, null, 1, 2]
Explanation:
1. Enqueue 1: Segment1=[1, _]
2. Enqueue 2: Segment1=[1, 2] (segment full)
3. Enqueue 3: Segment1=[1, 2], Segment2=[3, _] (new segment created)
4. Enqueue 4: Segment1=[1, 2], Segment2=[3, 4] 
5. Dequeue: Remove 1, Segment1=[_, 2], Segment2=[3, 4]
6. Dequeue: Remove 2, Segment1 deleted, Segment2=[3, 4]

Solution

The key insight is to use multiple fixed-size arrays (segments) organized as a linked structure. This approach provides:

1. Memory efficiency: Only allocate segments when needed
2. Constant amortized time: Operations are O(1) amortized
3. No memory waste: Remove empty segments automatically
4. Scalability: Can grow to any size by adding segments

Method 1 - Segmented Array Queue

Approach

1. Segment Structure: Each segment is a fixed-size array with front/rear pointers
2. Queue Structure: Maintain pointers to front and rear segments
3. Enqueue Logic:
   • Add to rear segment if space available
   • Create new rear segment if current is full
4. Dequeue Logic:
   • Remove from front segment
   • Delete front segment if it becomes empty
   • Move to next segment as new front

Code

Java

import java.util.*;

public class SegmentedArrayQueue {
    private static final int SEGMENT_SIZE = 1000; // Fixed segment size
    
    // Segment class to represent each fixed-length array
    private static class Segment {
        int[] arr;
        int front;
        int rear;
        int count;
        Segment next;
        
        public Segment() {
            arr = new int[SEGMENT_SIZE];
            front = 0;
            rear = 0;
            count = 0;
            next = null;
        }
        
        public boolean isFull() {
            return count == SEGMENT_SIZE;
        }
        
        public boolean isEmpty() {
            return count == 0;
        }
        
        public void enqueue(int value) {
            if (isFull()) {
                throw new IllegalStateException("Segment is full");
            }
            arr[rear] = value;
            rear = (rear + 1) % SEGMENT_SIZE;
            count++;
        }
        
        public int dequeue() {
            if (isEmpty()) {
                throw new IllegalStateException("Segment is empty");
            }
            int value = arr[front];
            front = (front + 1) % SEGMENT_SIZE;
            count--;
            return value;
        }
        
        public int peek() {
            if (isEmpty()) {
                throw new IllegalStateException("Segment is empty");
            }
            return arr[front];
        }
    }
    
    private Segment frontSegment;
    private Segment rearSegment;
    private int totalSize;
    
    public SegmentedArrayQueue() {
        frontSegment = new Segment();
        rearSegment = frontSegment;
        totalSize = 0;
    }
    
    public void enqueue(int value) {
        // If rear segment is full, create a new one
        if (rearSegment.isFull()) {
            Segment newSegment = new Segment();
            rearSegment.next = newSegment;
            rearSegment = newSegment;
        }
        
        rearSegment.enqueue(value);
        totalSize++;
    }
    
    public int dequeue() {
        if (totalSize == 0) {
            throw new IllegalStateException("Queue is empty");
        }
        
        int value = frontSegment.dequeue();
        totalSize--;
        
        // If front segment becomes empty and there are more segments, remove it
        if (frontSegment.isEmpty() && frontSegment.next != null) {
            frontSegment = frontSegment.next;
        }
        
        return value;
    }
    
    public int get_size() {
        return totalSize;
    }
    
    public boolean isEmpty() {
        return totalSize == 0;
    }
    
    public int peek() {
        if (totalSize == 0) {
            throw new IllegalStateException("Queue is empty");
        }
        return frontSegment.peek();
    }
    
    // Additional method to get number of active segments (for debugging)
    public int getSegmentCount() {
        int count = 0;
        Segment current = frontSegment;
        while (current != null) {
            count++;
            current = current.next;
        }
        return count;
    }
}

Python

from typing import Optional

class SegmentedArrayQueue:
    SEGMENT_SIZE = 1000  # Fixed segment size
    
    class Segment:
        def __init__(self):
            self.arr = [None] * SegmentedArrayQueue.SEGMENT_SIZE
            self.front = 0
            self.rear = 0
            self.count = 0
            self.next: Optional['SegmentedArrayQueue.Segment'] = None
        
        def is_full(self) -> bool:
            return self.count == SegmentedArrayQueue.SEGMENT_SIZE
        
        def is_empty(self) -> bool:
            return self.count == 0
        
        def enqueue(self, value: int) -> None:
            if self.is_full():
                raise OverflowError("Segment is full")
            self.arr[self.rear] = value
            self.rear = (self.rear + 1) % SegmentedArrayQueue.SEGMENT_SIZE
            self.count += 1
        
        def dequeue(self) -> int:
            if self.is_empty():
                raise IndexError("Segment is empty")
            value = self.arr[self.front]
            self.front = (self.front + 1) % SegmentedArrayQueue.SEGMENT_SIZE
            self.count -= 1
            return value
        
        def peek(self) -> int:
            if self.is_empty():
                raise IndexError("Segment is empty")
            return self.arr[self.front]
    
    def __init__(self):
        self.front_segment = self.Segment()
        self.rear_segment = self.front_segment
        self.total_size = 0
    
    def enqueue(self, value: int) -> None:
        # If rear segment is full, create a new one
        if self.rear_segment.is_full():
            new_segment = self.Segment()
            self.rear_segment.next = new_segment
            self.rear_segment = new_segment
        
        self.rear_segment.enqueue(value)
        self.total_size += 1
    
    def dequeue(self) -> int:
        if self.total_size == 0:
            raise IndexError("Queue is empty")
        
        value = self.front_segment.dequeue()
        self.total_size -= 1
        
        # If front segment becomes empty and there are more segments, remove it
        if self.front_segment.is_empty() and self.front_segment.next is not None:
            self.front_segment = self.front_segment.next
        
        return value
    
    def get_size(self) -> int:
        return self.total_size
    
    def is_empty(self) -> bool:
        return self.total_size == 0
    
    def peek(self) -> int:
        if self.total_size == 0:
            raise IndexError("Queue is empty")
        return self.front_segment.peek()
    
    # Additional method to get number of active segments (for debugging)
    def get_segment_count(self) -> int:
        count = 0
        current = self.front_segment
        while current is not None:
            count += 1
            current = current.next
        return count

Complexity

• ⏰ Time complexity:

  • Enqueue: O(1) amortized - occasionally O(1) to create new segment
  • Dequeue: O(1) amortized - occasionally O(1) to remove empty segment
  • get_size: O(1) - maintained as instance variable
  • peek: O(1) - direct access to front element

• 🧺 Space complexity: O(n) where n is the number of elements in the queue

  • Memory usage: ⌈n/SEGMENT_SIZE⌉ × SEGMENT_SIZE
  • Memory overhead: At most SEGMENT_SIZE - 1 unused slots in the rear segment

Method 2 - Generic Segmented Queue

This version provides type safety and can work with any data type.

Code

Java

import java.lang.reflect.Array;

public class GenericSegmentedQueue<T> {
    private static final int SEGMENT_SIZE = 1000;
    
    private static class Segment<T> {
        T[] arr;
        int front;
        int rear;
        int count;
        Segment<T> next;
        
        @SuppressWarnings("unchecked")
        public Segment(Class<T> clazz) {
            arr = (T[]) Array.newInstance(clazz, SEGMENT_SIZE);
            front = 0;
            rear = 0;
            count = 0;
            next = null;
        }
        
        public boolean isFull() {
            return count == SEGMENT_SIZE;
        }
        
        public boolean isEmpty() {
            return count == 0;
        }
        
        public void enqueue(T value) {
            if (isFull()) {
                throw new IllegalStateException("Segment is full");
            }
            arr[rear] = value;
            rear = (rear + 1) % SEGMENT_SIZE;
            count++;
        }
        
        public T dequeue() {
            if (isEmpty()) {
                throw new IllegalStateException("Segment is empty");
            }
            T value = arr[front];
            arr[front] = null; // Help GC
            front = (front + 1) % SEGMENT_SIZE;
            count--;
            return value;
        }
        
        public T peek() {
            if (isEmpty()) {
                throw new IllegalStateException("Segment is empty");
            }
            return arr[front];
        }
    }
    
    private final Class<T> elementClass;
    private Segment<T> frontSegment;
    private Segment<T> rearSegment;
    private int totalSize;
    
    public GenericSegmentedQueue(Class<T> clazz) {
        this.elementClass = clazz;
        frontSegment = new Segment<>(clazz);
        rearSegment = frontSegment;
        totalSize = 0;
    }
    
    public void enqueue(T value) {
        if (rearSegment.isFull()) {
            Segment<T> newSegment = new Segment<>(elementClass);
            rearSegment.next = newSegment;
            rearSegment = newSegment;
        }
        
        rearSegment.enqueue(value);
        totalSize++;
    }
    
    public T dequeue() {
        if (totalSize == 0) {
            throw new IllegalStateException("Queue is empty");
        }
        
        T value = frontSegment.dequeue();
        totalSize--;
        
        if (frontSegment.isEmpty() && frontSegment.next != null) {
            frontSegment = frontSegment.next;
        }
        
        return value;
    }
    
    public int get_size() {
        return totalSize;
    }
    
    public boolean isEmpty() {
        return totalSize == 0;
    }
    
    public T peek() {
        if (totalSize == 0) {
            throw new IllegalStateException("Queue is empty");
        }
        return frontSegment.peek();
    }
}

Python

from typing import TypeVar, Generic, Optional, List

T = TypeVar('T')

class GenericSegmentedQueue(Generic[T]):
    SEGMENT_SIZE = 1000
    
    class Segment(Generic[T]):
        def __init__(self):
            self.arr: List[Optional[T]] = [None] * GenericSegmentedQueue.SEGMENT_SIZE
            self.front = 0
            self.rear = 0
            self.count = 0
            self.next: Optional['GenericSegmentedQueue.Segment[T]'] = None
        
        def is_full(self) -> bool:
            return self.count == GenericSegmentedQueue.SEGMENT_SIZE
        
        def is_empty(self) -> bool:
            return self.count == 0
        
        def enqueue(self, value: T) -> None:
            if self.is_full():
                raise OverflowError("Segment is full")
            self.arr[self.rear] = value
            self.rear = (self.rear + 1) % GenericSegmentedQueue.SEGMENT_SIZE
            self.count += 1
        
        def dequeue(self) -> T:
            if self.is_empty():
                raise IndexError("Segment is empty")
            value = self.arr[self.front]
            self.arr[self.front] = None  # Help GC
            self.front = (self.front + 1) % GenericSegmentedQueue.SEGMENT_SIZE
            self.count -= 1
            return value
        
        def peek(self) -> T:
            if self.is_empty():
                raise IndexError("Segment is empty")
            return self.arr[self.front]
    
    def __init__(self):
        self.front_segment: GenericSegmentedQueue.Segment[T] = self.Segment()
        self.rear_segment = self.front_segment
        self.total_size = 0
    
    def enqueue(self, value: T) -> None:
        if self.rear_segment.is_full():
            new_segment: GenericSegmentedQueue.Segment[T] = self.Segment()
            self.rear_segment.next = new_segment
            self.rear_segment = new_segment
        
        self.rear_segment.enqueue(value)
        self.total_size += 1
    
    def dequeue(self) -> T:
        if self.total_size == 0:
            raise IndexError("Queue is empty")
        
        value = self.front_segment.dequeue()
        self.total_size -= 1
        
        if self.front_segment.is_empty() and self.front_segment.next is not None:
            self.front_segment = self.front_segment.next
        
        return value
    
    def get_size(self) -> int:
        return self.total_size
    
    def is_empty(self) -> bool:
        return self.total_size == 0
    
    def peek(self) -> T:
        if self.total_size == 0:
            raise IndexError("Queue is empty")
        return self.front_segment.peek()

# Example usage with type hints
# queue_int: GenericSegmentedQueue[int] = GenericSegmentedQueue()
# queue_str: GenericSegmentedQueue[str] = GenericSegmentedQueue()

Complexity

Same as Method 1, but with additional type safety and generic support.

Key Advantages

1. Memory Efficiency: Only allocates memory when needed, deallocates when segments are empty
2. Scalability: Can grow to any size by adding segments
3. Cache Locality: Elements in the same segment have good cache locality
4. Constant Amortized Time: All operations are O(1) amortized
5. No Memory Fragmentation: Uses fixed-size segments, reducing fragmentation

Use Cases

• High-throughput systems: Where queue size varies dramatically
• Memory-constrained environments: Where memory efficiency is critical
• Streaming data processing: Where data arrives in bursts
• Producer-consumer scenarios: With varying production/consumption rates

This implementation provides the best of both worlds: the memory efficiency of linked structures with the cache performance of arrays.