Patent ID: 7802032

Claim:
A method of implementing a queue, comprising the steps of: (a) enqueueing a user node to the end of a queue, wherein prior to the enqueueing step (a), the queue comprises at least a dummy node having a next pointer to a next node, and wherein the user node has a next pointer to a next node, and wherein the enqueueing step (a) includes the steps of: linking the user node to the end of the queue by setting the next pointer of a tail node to point to the user node; updating a tail pointer of the queue to point to the user node, wherein the updating step is not completed during the enqueueing step (a) but is completed during a subsequent enqueue operation or a subsequent dequeue operation; (b) after the enqueueing step (a), dequeueing the dummy node from the queue; (c) after the dequeueing step (b), conditionally dequeueing a head node from the queue; (d) during the conditional dequeueing step (c), enqueueing another dummy node to the end of the queue but only if the queue contains one and no more than one user node.