Deriving a Priority Queue from a Plain Vanilla Queue
The syntax for Reference Class inheritance is quite intuitive.
We need to modify only two of the methods. The most important of these is insert(), which is where all of the important stuff happens! I’ve added an additional parameter, priority, which gives the relative importance of the item to be inserted (with larger values indicating greater importance). The items are sorted according to priority, where items of higher priority are shifted to the front of the queue. Amongst items which have the same priority, the order of insertion is retained. The pop() method also needs modification: when items are removed from the queue, the corresponding priority is also discarded.
Priority Queue in Action
We create an instance of the Priority Queue and then insert four items with varying levels of importance.
According to the logic outlined above, the item “fourth” should move to the front of the queue since it has the highest priority. It will be followed by “second” which has next highest priority. Finally we have “first” and “second”, which have the same priority and thus retain the order in which they were inserted.
Next we can start extracting items from the queue. As expected, item “fourth” comes out first, followed in turn by “second”, “first” and “third”. The methods which were inherited without modification work as expected.
This code is now published in the liqueueR package.