0
# Priority Queues and Stacks
1

2
Specialized priority queue implementations including indirect priority queues and stack interfaces with enhanced functionality beyond standard Java collections.
3

4
## Overview
5

6
FastUtil provides several types of priority-based data structures:
7

8
- **Priority Queues**: Standard priority queues with enqueue/dequeue operations
9
- **Indirect Priority Queues**: Priority queues that operate on indices rather than elements directly
10
- **Stacks**: Stack interfaces with optional enhanced functionality like peeking at arbitrary depths
11
- **Utility Classes**: Helper classes for creating synchronized wrappers and other queue operations
12

13
These implementations focus on performance and provide additional functionality not available in standard Java collections.
14

15
## Capabilities
16

17
### Priority Queue Interface
18

19
Standard priority queue interface with enqueue/dequeue operations and optional bidirectional access.
20

21
```java { .api }
22
/**
23
 * Priority queue with enqueue/dequeue operations
24
 * @param <K> the type of elements
25
 */
26
public interface PriorityQueue<K> {
27
    /**
28
     * Add element to the queue
29
     * @param x the element to add
30
     */
31
    void enqueue(K x);
32
    
33
    /**
34
     * Remove and return the first (highest priority) element
35
     * @return the first element
36
     * @throws NoSuchElementException if queue is empty
37
     */
38
    K dequeue();
39
    
40
    /**
41
     * Get the first (highest priority) element without removing it
42
     * @return the first element
43
     * @throws NoSuchElementException if queue is empty
44
     */
45
    K first();
46
    
47
    /**
48
     * Get the last (lowest priority) element without removing it (optional operation)
49
     * @return the last element
50
     * @throws NoSuchElementException if queue is empty
51
     * @throws UnsupportedOperationException if not supported
52
     */
53
    K last();
54
    
55
    /**
56
     * Notify that the first element has been changed externally (optional operation)
57
     * This method should be called after modifying the first element in place
58
     * @throws UnsupportedOperationException if not supported
59
     */
60
    void changed();
61
    
62
    /**
63
     * Test if the queue is empty
64
     * @return true if the queue contains no elements
65
     */
66
    boolean isEmpty();
67
    
68
    /**
69
     * Get the number of elements in the queue
70
     * @return the number of elements
71
     */
72
    int size();
73
    
74
    /**
75
     * Remove all elements from the queue
76
     */
77
    void clear();
78
    
79
    /**
80
     * Get the comparator used to order elements
81
     * @return the comparator, or null if natural ordering is used
82
     */
83
    Comparator<? super K> comparator();
84
}
85
```
86

87
**Usage Examples:**
88

89
```java
90
import it.unimi.dsi.fastutil.objects.*;
91
import java.util.Comparator;
92

93
// Create priority queue with natural ordering
94
ObjectHeapPriorityQueue<String> queue = new ObjectHeapPriorityQueue<>();
95
queue.enqueue("zebra");
96
queue.enqueue("apple");
97
queue.enqueue("banana");
98

99
// Dequeue in sorted order
100
while (!queue.isEmpty()) {
101
    String item = queue.dequeue();
102
    System.out.println(item); // apple, banana, zebra
103
}
104

105
// Priority queue with custom comparator (reverse order)
106
ObjectHeapPriorityQueue<Integer> numbers = new ObjectHeapPriorityQueue<>(
107
    Comparator.reverseOrder());
108
numbers.enqueue(5);
109
numbers.enqueue(2);
110
numbers.enqueue(8);
111

112
System.out.println(numbers.first()); // 8 (highest number first)
113
System.out.println(numbers.last());  // 2 (lowest number last)
114
```
115

116
### Indirect Priority Queue Interface
117

118
Priority queue that operates on integer indices rather than elements directly, useful when elements are stored separately.
119

120
```java { .api }
121
/**
122
 * Priority queue operating on indices instead of elements directly
123
 * Elements are stored separately and referenced by integer indices
124
 */
125
public interface IndirectPriorityQueue {
126
    /**
127
     * Add index to the queue
128
     * @param x the index to add
129
     */
130
    void enqueue(int x);
131
    
132
    /**
133
     * Remove and return the first (highest priority) index
134
     * @return the first index
135
     * @throws NoSuchElementException if queue is empty
136
     */
137
    int dequeue();
138
    
139
    /**
140
     * Get the first (highest priority) index without removing it
141
     * @return the first index
142
     * @throws NoSuchElementException if queue is empty
143
     */
144
    int first();
145
    
146
    /**
147
     * Get the last (lowest priority) index without removing it (optional operation)
148
     * @return the last index
149
     * @throws NoSuchElementException if queue is empty
150
     * @throws UnsupportedOperationException if not supported
151
     */
152
    int last();
153
    
154
    /**
155
     * Notify that the first element has been changed externally (optional operation)
156
     * @throws UnsupportedOperationException if not supported
157
     */
158
    void changed();
159
    
160
    /**
161
     * Notify that the element at specified index has been changed (optional operation)
162
     * @param i the index of the changed element
163
     * @throws UnsupportedOperationException if not supported
164
     */
165
    void changed(int i);
166
    
167
    /**
168
     * Notify that all elements have been changed externally (optional operation)
169
     * @throws UnsupportedOperationException if not supported
170
     */
171
    void allChanged();
172
    
173
    /**
174
     * Test if the queue contains the specified index
175
     * @param index the index to test
176
     * @return true if the index is in the queue
177
     */
178
    boolean contains(int index);
179
    
180
    /**
181
     * Remove specific index from the queue
182
     * @param index the index to remove
183
     * @return the position of the removed index in the queue
184
     * @throws NoSuchElementException if index is not in queue
185
     */
186
    int remove(int index);
187
    
188
    /**
189
     * Test if the queue is empty
190
     * @return true if the queue contains no indices
191
     */
192
    boolean isEmpty();
193
    
194
    /**
195
     * Get the number of indices in the queue
196
     * @return the number of indices
197
     */
198
    int size();
199
    
200
    /**
201
     * Remove all indices from the queue
202
     */
203
    void clear();
204
    
205
    /**
206
     * Get the comparator used to order elements by index
207
     * @return the comparator used for element comparison
208
     */
209
    Comparator<?> comparator();
210
}
211
```
212

213
**Usage Examples:**
214

215
```java
216
import it.unimi.dsi.fastutil.ints.*;
217
import it.unimi.dsi.fastutil.objects.*;
218

219
// Separate storage for elements
220
String[] elements = {"zebra", "apple", "banana", "cherry"};
221

222
// Indirect priority queue orders indices based on element values
223
IndirectPriorityQueue queue = new ObjectHeapIndirectPriorityQueue<>(
224
    elements, String::compareTo);
225

226
// Add indices to queue
227
queue.enqueue(0); // "zebra"
228
queue.enqueue(1); // "apple"  
229
queue.enqueue(2); // "banana"
230
queue.enqueue(3); // "cherry"
231

232
// Dequeue indices in order of element priority
233
while (!queue.isEmpty()) {
234
    int index = queue.dequeue();
235
    System.out.println("Index " + index + ": " + elements[index]);
236
    // Index 1: apple
237
    // Index 2: banana  
238
    // Index 3: cherry
239
    // Index 0: zebra
240
}
241

242
// Modify element and notify queue
243
elements[1] = "aardvark"; // Change "apple" to "aardvark"
244
if (queue.contains(1)) {
245
    queue.changed(1); // Notify that element at index 1 changed
246
}
247
```
248

249
### Stack Interface
250

251
Stack interface with push/pop operations and optional enhanced functionality.
252

253
```java { .api }
254
/**
255
 * Stack with push/pop operations and optional peeking
256
 * @param <K> the type of elements
257
 */
258
public interface Stack<K> {
259
    /**
260
     * Push element onto the top of the stack
261
     * @param o the element to push
262
     */
263
    void push(K o);
264
    
265
    /**
266
     * Pop element from the top of the stack
267
     * @return the top element
268
     * @throws NoSuchElementException if stack is empty
269
     */
270
    K pop();
271
    
272
    /**
273
     * Test if the stack is empty
274
     * @return true if the stack contains no elements
275
     */
276
    boolean isEmpty();
277
    
278
    /**
279
     * Peek at the top element without removing it (optional operation)
280
     * @return the top element
281
     * @throws NoSuchElementException if stack is empty
282
     * @throws UnsupportedOperationException if not supported
283
     */
284
    K top();
285
    
286
    /**
287
     * Peek at the i-th element from the top (optional operation)
288
     * @param i distance from top (0 = top element, 1 = second from top, etc.)
289
     * @return the element at position i from top
290
     * @throws IndexOutOfBoundsException if i is invalid
291
     * @throws UnsupportedOperationException if not supported
292
     */
293
    K peek(int i);
294
}
295
```
296

297
**Usage Examples:**
298

299
```java
300
import it.unimi.dsi.fastutil.objects.*;
301

302
// Create stack implementation
303
ObjectArrayList<String> stackImpl = new ObjectArrayList<>();
304
Stack<String> stack = new AbstractStack<String>() {
305
    public void push(String o) { stackImpl.add(o); }
306
    public String pop() { return stackImpl.remove(stackImpl.size() - 1); }
307
    public boolean isEmpty() { return stackImpl.isEmpty(); }
308
    public String top() { return stackImpl.get(stackImpl.size() - 1); }
309
    public String peek(int i) { return stackImpl.get(stackImpl.size() - 1 - i); }
310
};
311

312
// Use stack operations
313
stack.push("first");
314
stack.push("second"); 
315
stack.push("third");
316

317
// Peek at elements without removing
318
System.out.println("Top: " + stack.top());        // "third"
319
System.out.println("Second: " + stack.peek(1));   // "second"
320
System.out.println("Bottom: " + stack.peek(2));   // "first"
321

322
// Pop elements
323
while (!stack.isEmpty()) {
324
    System.out.println("Popped: " + stack.pop());
325
    // Popped: third
326
    // Popped: second
327
    // Popped: first
328
}
329
```
330

331
### Abstract Base Classes
332

333
Abstract implementations providing common functionality for priority queues and stacks.
334

335
```java { .api }
336
/**
337
 * Abstract base class for priority queue implementations
338
 * @param <K> the type of elements
339
 */
340
public abstract class AbstractPriorityQueue<K> implements PriorityQueue<K> {
341
    /**
342
     * Default implementation throws UnsupportedOperationException
343
     * @return the last element
344
     * @throws UnsupportedOperationException always
345
     */
346
    public K last() {
347
        throw new UnsupportedOperationException();
348
    }
349
    
350
    /**
351
     * Default implementation throws UnsupportedOperationException  
352
     * @throws UnsupportedOperationException always
353
     */
354
    public void changed() {
355
        throw new UnsupportedOperationException();
356
    }
357
    
358
    /**
359
     * Default implementation returns null (natural ordering)
360
     * @return null
361
     */
362
    public Comparator<? super K> comparator() {
363
        return null;
364
    }
365
}
366

367
/**
368
 * Abstract base class for indirect priority queue implementations
369
 */
370
public abstract class AbstractIndirectPriorityQueue implements IndirectPriorityQueue {
371
    /**
372
     * Default implementation throws UnsupportedOperationException
373
     * @return the last index
374
     * @throws UnsupportedOperationException always
375
     */
376
    public int last() {
377
        throw new UnsupportedOperationException();
378
    }
379
    
380
    /**
381
     * Default implementation throws UnsupportedOperationException
382
     * @throws UnsupportedOperationException always
383
     */
384
    public void changed() {
385
        throw new UnsupportedOperationException();
386
    }
387
    
388
    /**
389
     * Default implementation throws UnsupportedOperationException
390
     * @param i the index of changed element
391
     * @throws UnsupportedOperationException always
392
     */
393
    public void changed(int i) {
394
        throw new UnsupportedOperationException();
395
    }
396
    
397
    /**
398
     * Default implementation throws UnsupportedOperationException
399
     * @throws UnsupportedOperationException always
400
     */
401
    public void allChanged() {
402
        throw new UnsupportedOperationException();
403
    }
404
}
405

406
/**
407
 * Abstract base class for stack implementations
408
 * @param <K> the type of elements
409
 */
410
public abstract class AbstractStack<K> implements Stack<K> {
411
    /**
412
     * Default implementation throws UnsupportedOperationException
413
     * @return the top element
414
     * @throws UnsupportedOperationException always
415
     */
416
    public K top() {
417
        throw new UnsupportedOperationException();
418
    }
419
    
420
    /**
421
     * Default implementation throws UnsupportedOperationException
422
     * @param i distance from top
423
     * @return the element at position i
424
     * @throws UnsupportedOperationException always
425
     */
426
    public K peek(int i) {
427
        throw new UnsupportedOperationException();
428
    }
429
}
430
```
431

432
### Utility Classes
433

434
Utility classes providing helper methods for creating synchronized wrappers and other operations.
435

436
```java { .api }
437
/**
438
 * Utility class for priority queue operations
439
 */
440
public class PriorityQueues {
441
    /**
442
     * Create synchronized wrapper for priority queue
443
     * @param q the priority queue to wrap
444
     * @return synchronized priority queue
445
     */
446
    public static <K> PriorityQueue<K> synchronize(PriorityQueue<K> q);
447
    
448
    /**
449
     * Create synchronized wrapper with custom lock object
450
     * @param q the priority queue to wrap
451
     * @param sync the lock object to use
452
     * @return synchronized priority queue
453
     */
454
    public static <K> PriorityQueue<K> synchronize(PriorityQueue<K> q, Object sync);
455
    
456
    // Type-specific synchronization methods for primitive priority queues
457
    public static IntPriorityQueue synchronize(IntPriorityQueue q);
458
    public static LongPriorityQueue synchronize(LongPriorityQueue q);
459
    public static DoublePriorityQueue synchronize(DoublePriorityQueue q);
460
    // ... similar methods for other primitive types
461
}
462

463
/**
464
 * Utility class for indirect priority queue operations
465
 */
466
public class IndirectPriorityQueues {
467
    /**
468
     * Create synchronized wrapper for indirect priority queue
469
     * @param q the indirect priority queue to wrap
470
     * @return synchronized indirect priority queue
471
     */
472
    public static IndirectPriorityQueue synchronize(IndirectPriorityQueue q);
473
    
474
    /**
475
     * Create synchronized wrapper with custom lock object
476
     * @param q the indirect priority queue to wrap
477
     * @param sync the lock object to use
478
     * @return synchronized indirect priority queue
479
     */
480
    public static IndirectPriorityQueue synchronize(IndirectPriorityQueue q, Object sync);
481
}
482
```
483

484
**Usage Examples:**
485

486
```java
487
import it.unimi.dsi.fastutil.objects.*;
488
import it.unimi.dsi.fastutil.ints.*;
489

490
// Create thread-safe priority queue
491
ObjectHeapPriorityQueue<String> originalQueue = new ObjectHeapPriorityQueue<>();
492
PriorityQueue<String> syncQueue = PriorityQueues.synchronize(originalQueue);
493

494
// Use from multiple threads safely
495
syncQueue.enqueue("thread-safe-item");
496
String item = syncQueue.dequeue();
497

498
// Create thread-safe indirect priority queue
499
String[] data = {"a", "b", "c"};
500
ObjectHeapIndirectPriorityQueue<String> originalIndirect = 
501
    new ObjectHeapIndirectPriorityQueue<>(data);
502
IndirectPriorityQueue syncIndirect = IndirectPriorityQueues.synchronize(originalIndirect);
503

504
// Thread-safe indirect operations
505
syncIndirect.enqueue(0);
506
int index = syncIndirect.dequeue();
507

508
// Type-specific synchronized priority queue
509
IntHeapPriorityQueue intQueue = new IntHeapPriorityQueue();
510
IntPriorityQueue syncIntQueue = PriorityQueues.synchronize(intQueue);
511
syncIntQueue.enqueue(42);
512
int value = syncIntQueue.dequeueInt(); // Type-specific dequeue
513
```
514

515
## Implementation Classes
516

517
### Priority Queue Implementations
518

519
**ObjectHeapPriorityQueue<K>**
520
- Heap-based priority queue for objects
521
- Efficient O(log n) enqueue/dequeue operations
522
- Supports custom comparators
523

524
**Type-Specific Priority Queues**
525
- **`IntHeapPriorityQueue`**, **`LongHeapPriorityQueue`**, etc.
526
- Primitive-optimized versions avoiding boxing overhead
527
- Methods like `enqueueInt()`, `dequeueInt()` for direct primitive access
528

529
### Indirect Priority Queue Implementations
530

531
**ObjectHeapIndirectPriorityQueue<K>**
532
- Heap-based indirect priority queue for objects
533
- Maintains separate element storage and index-based priority ordering
534
- Supports element change notifications
535

536
**Type-Specific Indirect Priority Queues**  
537
- **`IntHeapIndirectPriorityQueue`**, **`LongHeapIndirectPriorityQueue`**, etc.
538
- Optimized for primitive element types
539
- Direct primitive access methods
540

541
### Performance Characteristics
542

543
- **Priority Queues**: O(log n) enqueue/dequeue, O(1) peek operations
544
- **Indirect Priority Queues**: O(log n) operations with additional O(1) contains/remove by index
545
- **Synchronized Wrappers**: Same complexity with synchronization overhead
546
- **Memory Usage**: Heap-based implementations use compact array storage
547

548
### Usage Guidelines
549

550
1. **Choose Direct vs Indirect**: Use indirect queues when elements are stored separately or when you need to modify priorities of existing elements
551
2. **Thread Safety**: Use synchronized wrappers for multi-threaded access
552
3. **Primitive Types**: Use type-specific implementations to avoid boxing overhead
553
4. **Change Notifications**: Call `changed()` methods after modifying elements in-place for indirect queues
554
5. **Comparators**: Provide appropriate comparators for custom ordering requirements