Basics Queue

A queue is a collection that is based on the first-in-first-out (FIFO) policy. The concept of queues can be found in everyday tasks, such as standing line at the bank or waiting for the next porta-potty to become free. Queue establishes a sense of fairness that is first come first served.

Java has different implementation of queues, but for a now let derive a queue from the ground up.

At this moment you are thinking, “Why do I need to implement queues when Java already provides them?”

By understanding a basic queue helps to determine when and when not to use a queue. Queues perform well when maintaining the order of objects, but should be avoided when a task requires:

  • Inserting objects (except at the last position)
  • Deleting or removing objects (except at the first position)
  • Randomly accessing objects

It’s not the end of the world if you use any of the previous actions, but it will cost you in performance.

Below, is a basic queue framework and to gain a better understanding I suggest that you commit this to memory. In addition, by having the framework committed to memory helps when transitioning to other programming languages.

public class BasicQueue<Item>
// adds item to queue
void enqueue(Item item)
// removes and return queue item
Item dequeue()
// return true if queue is empty
boolean isEmpty()
// return the number of items
int size()

Below is a simple implementation. Take the time to understand this implementation and pay close attention to how the Node objects link to form a queue. This linking technique is commonly referred to as linked-list.

public class BasicQueue<Item> {
Node<Item> first = null;
Node<Item> last = null;
int cnt = 0;

public class Node<Item> {
Node next;
Item item;
public Node(Item item) {
this.item = item;
}
}

public void enqueue(Item item) {
Node oldLast = last;
last = new Node(item);
last.next = null;
if (isEmpty()) {
first = last;
} else {
oldLast.next = last;
}
cnt++;
}

public Item dequeue() throws NoSuchElementException {
if (isEmpty()) {
throw new NoSuchElementException("invalid request");
}
Item oldFirst = first.item;
first = oldFirst.next;
cnt--;
return oldFirst;
}

public boolean isEmpty() {
return first == null;
}

public int size() {
return cnt;
}
}

Queues are a basic collection that is implemented in many computer science disciplines. As you move deeper into programming, especially the study algorithms, queues play an important role. So, by getting a firm understanding of queues will help you later.