Priority Queues and Stacks

/**
 * Priority queue with enqueue/dequeue operations
 * @param <K> the type of elements
 */
public interface PriorityQueue<K> {
    /**
     * Add element to the queue
     * @param x the element to add
     */
    void enqueue(K x);
    
    /**
     * Remove and return the first (highest priority) element
     * @return the first element
     * @throws NoSuchElementException if queue is empty
     */
    K dequeue();
    
    /**
     * Get the first (highest priority) element without removing it
     * @return the first element
     * @throws NoSuchElementException if queue is empty
     */
    K first();
    
    /**
     * Get the last (lowest priority) element without removing it (optional operation)
     * @return the last element
     * @throws NoSuchElementException if queue is empty
     * @throws UnsupportedOperationException if not supported
     */
    K last();
    
    /**
     * Notify that the first element has been changed externally (optional operation)
     * This method should be called after modifying the first element in place
     * @throws UnsupportedOperationException if not supported
     */
    void changed();
    
    /**
     * Test if the queue is empty
     * @return true if the queue contains no elements
     */
    boolean isEmpty();
    
    /**
     * Get the number of elements in the queue
     * @return the number of elements
     */
    int size();
    
    /**
     * Remove all elements from the queue
     */
    void clear();
    
    /**
     * Get the comparator used to order elements
     * @return the comparator, or null if natural ordering is used
     */
    Comparator<? super K> comparator();
}

import it.unimi.dsi.fastutil.objects.*;
import java.util.Comparator;

// Create priority queue with natural ordering
ObjectHeapPriorityQueue<String> queue = new ObjectHeapPriorityQueue<>();
queue.enqueue("zebra");
queue.enqueue("apple");
queue.enqueue("banana");

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

// Priority queue with custom comparator (reverse order)
ObjectHeapPriorityQueue<Integer> numbers = new ObjectHeapPriorityQueue<>(
    Comparator.reverseOrder());
numbers.enqueue(5);
numbers.enqueue(2);
numbers.enqueue(8);

System.out.println(numbers.first()); // 8 (highest number first)
System.out.println(numbers.last());  // 2 (lowest number last)

/**
 * Priority queue operating on indices instead of elements directly
 * Elements are stored separately and referenced by integer indices
 */
public interface IndirectPriorityQueue {
    /**
     * Add index to the queue
     * @param x the index to add
     */
    void enqueue(int x);
    
    /**
     * Remove and return the first (highest priority) index
     * @return the first index
     * @throws NoSuchElementException if queue is empty
     */
    int dequeue();
    
    /**
     * Get the first (highest priority) index without removing it
     * @return the first index
     * @throws NoSuchElementException if queue is empty
     */
    int first();
    
    /**
     * Get the last (lowest priority) index without removing it (optional operation)
     * @return the last index
     * @throws NoSuchElementException if queue is empty
     * @throws UnsupportedOperationException if not supported
     */
    int last();
    
    /**
     * Notify that the first element has been changed externally (optional operation)
     * @throws UnsupportedOperationException if not supported
     */
    void changed();
    
    /**
     * Notify that the element at specified index has been changed (optional operation)
     * @param i the index of the changed element
     * @throws UnsupportedOperationException if not supported
     */
    void changed(int i);
    
    /**
     * Notify that all elements have been changed externally (optional operation)
     * @throws UnsupportedOperationException if not supported
     */
    void allChanged();
    
    /**
     * Test if the queue contains the specified index
     * @param index the index to test
     * @return true if the index is in the queue
     */
    boolean contains(int index);
    
    /**
     * Remove specific index from the queue
     * @param index the index to remove
     * @return the position of the removed index in the queue
     * @throws NoSuchElementException if index is not in queue
     */
    int remove(int index);
    
    /**
     * Test if the queue is empty
     * @return true if the queue contains no indices
     */
    boolean isEmpty();
    
    /**
     * Get the number of indices in the queue
     * @return the number of indices
     */
    int size();
    
    /**
     * Remove all indices from the queue
     */
    void clear();
    
    /**
     * Get the comparator used to order elements by index
     * @return the comparator used for element comparison
     */
    Comparator<?> comparator();
}

import it.unimi.dsi.fastutil.ints.*;
import it.unimi.dsi.fastutil.objects.*;

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

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

// Add indices to queue
queue.enqueue(0); // "zebra"
queue.enqueue(1); // "apple"  
queue.enqueue(2); // "banana"
queue.enqueue(3); // "cherry"

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

// Modify element and notify queue
elements[1] = "aardvark"; // Change "apple" to "aardvark"
if (queue.contains(1)) {
    queue.changed(1); // Notify that element at index 1 changed
}

/**
 * Stack with push/pop operations and optional peeking
 * @param <K> the type of elements
 */
public interface Stack<K> {
    /**
     * Push element onto the top of the stack
     * @param o the element to push
     */
    void push(K o);
    
    /**
     * Pop element from the top of the stack
     * @return the top element
     * @throws NoSuchElementException if stack is empty
     */
    K pop();
    
    /**
     * Test if the stack is empty
     * @return true if the stack contains no elements
     */
    boolean isEmpty();
    
    /**
     * Peek at the top element without removing it (optional operation)
     * @return the top element
     * @throws NoSuchElementException if stack is empty
     * @throws UnsupportedOperationException if not supported
     */
    K top();
    
    /**
     * Peek at the i-th element from the top (optional operation)
     * @param i distance from top (0 = top element, 1 = second from top, etc.)
     * @return the element at position i from top
     * @throws IndexOutOfBoundsException if i is invalid
     * @throws UnsupportedOperationException if not supported
     */
    K peek(int i);
}

import it.unimi.dsi.fastutil.objects.*;

// Create stack implementation
ObjectArrayList<String> stackImpl = new ObjectArrayList<>();
Stack<String> stack = new AbstractStack<String>() {
    public void push(String o) { stackImpl.add(o); }
    public String pop() { return stackImpl.remove(stackImpl.size() - 1); }
    public boolean isEmpty() { return stackImpl.isEmpty(); }
    public String top() { return stackImpl.get(stackImpl.size() - 1); }
    public String peek(int i) { return stackImpl.get(stackImpl.size() - 1 - i); }
};

// Use stack operations
stack.push("first");
stack.push("second"); 
stack.push("third");

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

// Pop elements
while (!stack.isEmpty()) {
    System.out.println("Popped: " + stack.pop());
    // Popped: third
    // Popped: second
    // Popped: first
}

/**
 * Abstract base class for priority queue implementations
 * @param <K> the type of elements
 */
public abstract class AbstractPriorityQueue<K> implements PriorityQueue<K> {
    /**
     * Default implementation throws UnsupportedOperationException
     * @return the last element
     * @throws UnsupportedOperationException always
     */
    public K last() {
        throw new UnsupportedOperationException();
    }
    
    /**
     * Default implementation throws UnsupportedOperationException  
     * @throws UnsupportedOperationException always
     */
    public void changed() {
        throw new UnsupportedOperationException();
    }
    
    /**
     * Default implementation returns null (natural ordering)
     * @return null
     */
    public Comparator<? super K> comparator() {
        return null;
    }
}

/**
 * Abstract base class for indirect priority queue implementations
 */
public abstract class AbstractIndirectPriorityQueue implements IndirectPriorityQueue {
    /**
     * Default implementation throws UnsupportedOperationException
     * @return the last index
     * @throws UnsupportedOperationException always
     */
    public int last() {
        throw new UnsupportedOperationException();
    }
    
    /**
     * Default implementation throws UnsupportedOperationException
     * @throws UnsupportedOperationException always
     */
    public void changed() {
        throw new UnsupportedOperationException();
    }
    
    /**
     * Default implementation throws UnsupportedOperationException
     * @param i the index of changed element
     * @throws UnsupportedOperationException always
     */
    public void changed(int i) {
        throw new UnsupportedOperationException();
    }
    
    /**
     * Default implementation throws UnsupportedOperationException
     * @throws UnsupportedOperationException always
     */
    public void allChanged() {
        throw new UnsupportedOperationException();
    }
}

/**
 * Abstract base class for stack implementations
 * @param <K> the type of elements
 */
public abstract class AbstractStack<K> implements Stack<K> {
    /**
     * Default implementation throws UnsupportedOperationException
     * @return the top element
     * @throws UnsupportedOperationException always
     */
    public K top() {
        throw new UnsupportedOperationException();
    }
    
    /**
     * Default implementation throws UnsupportedOperationException
     * @param i distance from top
     * @return the element at position i
     * @throws UnsupportedOperationException always
     */
    public K peek(int i) {
        throw new UnsupportedOperationException();
    }
}

/**
 * Utility class for priority queue operations
 */
public class PriorityQueues {
    /**
     * Create synchronized wrapper for priority queue
     * @param q the priority queue to wrap
     * @return synchronized priority queue
     */
    public static <K> PriorityQueue<K> synchronize(PriorityQueue<K> q);
    
    /**
     * Create synchronized wrapper with custom lock object
     * @param q the priority queue to wrap
     * @param sync the lock object to use
     * @return synchronized priority queue
     */
    public static <K> PriorityQueue<K> synchronize(PriorityQueue<K> q, Object sync);
    
    // Type-specific synchronization methods for primitive priority queues
    public static IntPriorityQueue synchronize(IntPriorityQueue q);
    public static LongPriorityQueue synchronize(LongPriorityQueue q);
    public static DoublePriorityQueue synchronize(DoublePriorityQueue q);
    // ... similar methods for other primitive types
}

/**
 * Utility class for indirect priority queue operations
 */
public class IndirectPriorityQueues {
    /**
     * Create synchronized wrapper for indirect priority queue
     * @param q the indirect priority queue to wrap
     * @return synchronized indirect priority queue
     */
    public static IndirectPriorityQueue synchronize(IndirectPriorityQueue q);
    
    /**
     * Create synchronized wrapper with custom lock object
     * @param q the indirect priority queue to wrap
     * @param sync the lock object to use
     * @return synchronized indirect priority queue
     */
    public static IndirectPriorityQueue synchronize(IndirectPriorityQueue q, Object sync);
}

import it.unimi.dsi.fastutil.objects.*;
import it.unimi.dsi.fastutil.ints.*;

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

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

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

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

// Type-specific synchronized priority queue
IntHeapPriorityQueue intQueue = new IntHeapPriorityQueue();
IntPriorityQueue syncIntQueue = PriorityQueues.synchronize(intQueue);
syncIntQueue.enqueue(42);
int value = syncIntQueue.dequeueInt(); // Type-specific dequeue