实现最多分配2个元素的3元素调度器，避免元素饥饿

Let's break down the requirements and implement the scheduler correctly. The key points we need to handle are:

• Maintain a FIFO queue for available elements, prioritizing unused elements over released ones (to avoid starvation)
• Track currently allocated elements to enforce the maximum 2-element limit
• Handle element release by returning them to the end of the available queue

Implementation Code #

import java.util.LinkedList;
import java.util.HashSet;

public class Main {
    public static void main(String[] args) {
        myScheduler p = new myScheduler();
        /* available elements: "0","1","2" imagine them being in a queue */
        /* elements taken: non */
        String show = p.requestElement(); //Should return "0"
        /* available elements: "1","2" imagine them being in a queue */
        /* elements taken: "0" */
        System.out.println(show);
        show = p.requestElement(); //Should return "1"
        /* available elements: "2" queue cannot be empty */
        /* elements taken: "0","1" imagine them being a linked list (at most 2 elements can be taken) */
        System.out.println(show);
        show = p.requestElement(); //Should return "full"
        /* available elements: "2" queue cannot be empty */
        /* elements taken: "0","1" note: it didn't change (at most 2 elements can be taken) */
        System.out.println(show);
        show = p.abandonElement("1"); //Should return "1"
        /* available elements: "2","1" imagine them being in a queue */
        /* elements taken: "0" */
        System.out.println(show);
        show = p.requestElement(); //Should return "2"
        /* available elements: "1" queue cannot be empty */
        /* elements taken: "0","2" (at most 2 elements can be taken) */
        System.out.println(show);
        show = p.requestElement(); //Should return "full"
        /* available elements: "1" queue cannot be empty */
        /* elements taken: "0","2" note: it did not change (at most 2 elements can be taken) */
        System.out.println(show);
        show = p.abandonElement("0"); //Should return "0"
        /* available elements: "1","0" */
        /* elements taken: "2" */
        System.out.println(show);
        show = p.requestElement(); //Should return "1"
        /* available elements: "0" */
        /* elements taken: "2","1" */
        System.out.println(show);
    }
}

class myScheduler {
    // Queue to manage available elements (FIFO order)
    private LinkedList<String> availableQueue;
    // Set to track currently allocated elements (O(1) lookups)
    private HashSet<String> allocatedSet;

    public myScheduler() {
        // Initialize available queue with the default elements in order
        availableQueue = new LinkedList<>();
        availableQueue.add("0");
        availableQueue.add("1");
        availableQueue.add("2");
        allocatedSet = new HashSet<>();
    }

    /**
     * Handles element allocation requests
     * @return The allocated element, or "full" if maximum capacity is reached
     */
    public String requestElement(){
        // Check if we've reached the maximum allocation limit (2 elements)
        if (allocatedSet.size() >= 2) {
            return "full";
        }
        // Take the first element from the available queue
        String element = availableQueue.poll();
        // Mark the element as allocated
        allocatedSet.add(element);
        return element;
    }

    /**
     * Handles element release requests
     * @param element The element to be released
     * @return The released element, or "not found" if the element isn't allocated
     */
    public String abandonElement(String element){
        // Check if the element is currently allocated
        if (!allocatedSet.contains(element)) {
            return "not found";
        }
        // Remove from allocated set
        allocatedSet.remove(element);
        // Add back to the END of the available queue (to maintain FIFO order for reused elements)
        availableQueue.add(element);
        return element;
    }
}

Key Explanations #

• Available Queue: We use LinkedList to implement a FIFO queue. Unused elements start in the queue, and when elements are released, they're added to the end of the queue. This ensures that unused elements are prioritized over reused ones, preventing starvation.
• Allocated Set: HashSet provides O(1) time complexity for checking if an element is allocated and for adding/removing elements, making the operations efficient.
• Request Logic: If we haven't hit the 2-element limit, we take the first element from the queue, mark it as allocated, and return it. If we're at capacity, return "full".
• Release Logic: Verify the element is allocated first. If it is, remove it from the allocated set and add it back to the end of the available queue, then return the element. If not, return "not found".

Test Output #

When you run the Main class, the output will be exactly as expected:

0
1
full
1
2
full
0
1

内容的提问来源于stack exchange，提问作者T_man