Queues (Abstract Data Type)

Queues (Abstract Data Type)

FIFO queue

public class Queue<Item> implements Iterable<Item>
Queue() - create an empty queue
void enqueue(Item item) - add an item
Item dequeue() - remove the least recently added item
boolean isEmpty() - is the queue empty?
int size() - number of items in the queue

A FIFO queue (or just a queue) is a collection that is based on the first-in-first-out (FIFO) policy. The policy of doing tasks in the same order that they arrive is one that we encounter frequently in everyday life: from people waiting in line at a theater, to cars waiting in line at a toll booth, to tasks waiting to be serviced by an application on your computer. One bed-rock principle of any service policy is the perception of fairness. The first idea that comes to mind when most people think about fairness is that whoever has been waiting the longest should be served first. That is precisely the FIFO discipline. Queues are a natural model for many everyday phenomena, and they play a central role in numerous applications. When a client iterates through the items in a queue with the foreach construct, the items are processed in the order they were added to the queue. A typical reason to use a queue in an application is to save items in a collection while at the same time preserving their relative order : they come out in the same order in which they were put in. For example, the client below (TODO : implement) is a possible implementation of the readDoubles() static method from our In class. The problem that this method solves for the client is that the client can get numbers from a file into an array without knowing the file size ahead of time. We enqueue the numbers from the file, use the size() method from Queue to find the size needed for the array, create the array, and then dequeue the numbers to move them to the array.

Some uses:

1. Scheduling access to shared resource (e.g., printer)

Implemented by LinkedList and ArrayDeque in Java