The difference between a FIFO queue and a pushdown stack () is that new items are inserted at the end, rather than the beginning. This class keeps a pointer tail to the last node of the list so that the method put can add a new node by linking that node to the node referenced by tail and updating tail to point to the new node. The constructor, get, andempty are identical to their counterparts for the linked-list-pushdown-stack implementation of . The node constructor has only one parameter because new nodes are always inserted at the end of the list and thus have a null next field. 

class intQueue { private class Node { int item; Node next; Node(int item) { this.item = item; next = null; } } private Node head, tail; intQueue(int max) { head = null; tail = null; } boolean empty() { return (head == null); } void put(int item) { Node t = tail; tail = new Node(item); if (empty()) head = tail; else t.next = tail; } int get() { int v = head.item; Node t = head.next; head = t; return v; } }

We can also use an array to implement a FIFO queue, although we have to exercise care to keep the running time constant for both the put and get operations. That performance goal dictates that we can not move the elements of the queue within the array, unlike what might be suggested by a literal interpretation of . Accordingly, as we did with the linked-list implementation, we maintain two indices into the array: one to the beginning of the queue and one to the end of the queue. We consider the contents of the queue to be the elements between the indices. To get an element, we remove it from the beginning (head) of the queue and increment the head index; to put an element, we add it to the end (tail) of the queue and increment the tail index. A sequence of put and get operations causes the queue to appear to move through the array, as illustrated in . When it hits the end of the array, we arrange for it to wrap around to the beginning. The details of this computation are in the code in .