Service priority queue implemented with ordered sub-queues and sub-queue

Abstract

A priority queue structure and algorithm for managing the structure which in most cases performs in constant time. In other words, most of the time the inventive algorithm performs its work in an amount of time that is independent on the number of priority classes or elements that exist in the queue. The queue itself consists of a linked list of elements ordered into subqueues corresponding to priority classes, with higher priority subqueues appearing earlier in the queue. An array of priority pointers contains an entry for each subqueue that points to the last element of each subqueue. Elements are removed for processing from the top of the queue. Removal takes constant time. Items are inserted into an appropriate subqueue by linking it at the end of its respective subqueue. The only case that requires a variable amount of time depending on the length of the queue and the number of priority classes occurs when an item is added to an empty subqueue which is of lower priority than the element at the top of the queue. All subsequent additions to that subqueue consume constant time until the subqueue becomes empty once again. A feature of the invention prevents the possibility of perpetually locking out lower priority items in the queue by promoting the priority of a preempted item residing directly below a newly inserted item on the queue.