Problem#
Implement a queue using a set of fixed-length arrays.
The queue should support enqueue, dequeue, and get_size operations.
Examples#
Example 1:
1
2
3
4
5
6
7
8
9
|
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:
1
2
3
4
5
6
7
8
9
10
|
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:
- Memory efficiency: Only allocate segments when needed
- Constant amortized time: Operations are O(1) amortized
- No memory waste: Remove empty segments automatically
- Scalability: Can grow to any size by adding segments
Method 1 - Segmented Array Queue#
Approach#
- Segment Structure: Each segment is a fixed-size array with front/rear pointers
- Queue Structure: Maintain pointers to front and rear segments
- Enqueue Logic:
- Add to rear segment if space available
- Create new rear segment if current is full
- Dequeue Logic:
- Remove from front segment
- Delete front segment if it becomes empty
- Move to next segment as new front
Code#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
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#
Method 2 - Generic Segmented Queue#
This version provides type safety and can work with any data type.
Code#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
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();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
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#
- Memory Efficiency: Only allocates memory when needed, deallocates when segments are empty
- Scalability: Can grow to any size by adding segments
- Cache Locality: Elements in the same segment have good cache locality
- Constant Amortized Time: All operations are O(1) amortized
- 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.