Using queue specific variable(s) to efficiently delete expired items in an ordered queue without necessarily checking each queued item's expiry time

摘要

A method for deleting expired items in a queue data structure, the queue data structure comprising a sequential list of ordered data items including a queue head at one end of the sequential list and a queue tail at another end of the sequential list, wherein each data item includes an expiry time, the method comprising: generating a maximum interval value corresponding to a maximum time interval between an expiry time of a first item in the queue and an expiry time of a second item in the queue, wherein the second item is nearer the queue head than the first item; sequentially scanning the list of ordered items from the queue head; responsive to a determination that a scanned item is expired, deleting the scanned item; responsive to a determination that a scanned item will not expire for a time interval greater than the maximum interval value, terminating scanning of the list of ordered items.