1. A method, comprising: using a computer to perform: providing a shared first-in-first-out (FIFO) queue that includes a central queue and an elimination data structure, wherein the elimination data structure comprises one or more entries each indicating an enqueue or dequeue operation to attempt to eliminate as part of an enqueue-dequeue operation pair; receiving a request for an enqueue operation that would add an element to the FIFO queue or a dequeue operation that would remove an element from the FIFO queue; in response to said receiving, dynamically determining whether to allow access to the central queue to add an element to or remove an element from the central queue as specified by the request, or to attempt elimination of an enqueue-dequeue operation pair comprising the requested enqueue or dequeue operation, wherein attempting elimination comprises: updating one or more entries of the elimination data structure; and examining one or more entries of the elimination data structure in an attempt to locate a corresponding enqueue or dequeue operation with which to form the enqueue-dequeue operation pair; wherein said determining comprises determining whether the elimination would result in invalid behavior for the FIFO queue; and allowing access to the central queue or attempting elimination without accessing the central queue, dependent on results of said determining.