Queue

What is the opposite of a stack? This may be a weird question. However, a stack follows LIFO, last in first out. The opposite of that is first-in-first-out (FIFO). So, in some sense, a FIFO ADT can be considered as the opposite of a stack. This is not very different from a queue of people waiting for a bus or at a doctor's clinic. The first person to show up gets the first chance to get onto the bus or to get to see the doctor. The second person gets the second chance. No wonder, such an abstract data type is called a queue. Appending to the end of a queue is called enqueuing and removing from it is called dequeuing. The contract is, of course, that the first value that is enqueued would be the first to be dequeued. The following figure illustrates this operation:

The queue ADT has the following operations:

• Enqueue: This adds an element at the back of the queue
• Dequeue: This removes an element from the front of the queue
• Peek: This checks the element that would be dequeued next

The queue will be represented by the following interface:

public interface Queue<E> {
  void enqueue(E value);
  E dequeue();
  E peek();
}

Fixed-sized queue using an array

Just like the stack, we have an array-based implementation of a queue. However, since a queue receives new values and removes old values from opposite sides, the body of the queue moves as it does. The following figure will illustrate this point:

This means that after a sequence of a few such operations, the end of the queue will reach the end of the array, and there will be space left at the beginning of the array. At this point, we don't want to stop receiving new values as there is space left, so we roll over to the beginning of the array. That is to say, we continue adding the new values at the beginning of the array.

To do all these manipulations, we must have separate variables storing the indexes of the beginning and the end of the queue. Also, since due to roll over, sometimes the end is smaller than the beginning, we store the length separately to avoid confusion. We start with the bare bone implementation of the class just as before. The start represents the index of the element that would be dequeued next and the end represents the position of the next value that would be enqueued. This is illustrated in the following code:

public class QueueImplArray<E>  implements Queue<E>{
  protected E[] array;
  protected int start=0;
  protected int end=0;
  protected int length=0;
  public QueueImplArray(int size){
    array = (E[]) new Object[size];
  }
}

The enqueue operation does not change the start position. The new value is put at the end position of the array and the end is incremented by one. The end, of course, needs to be rolled over in case it goes beyond the maximum index of the array, as shown in the following code:

@Override
public void enqueue(E value) {
  if(length>=array.length){
    throw new NoSpaceException("No more space to add an element");
  }
  array[end] = value;

The modulo operator will make sure that the index goes to the beginning of the array when it hits the end of the array, as follows:

  end = (end+1) % array.length;
  length++;
}

The dequeue operation does not change the end position. We read from the start index and then increment the start index with rollover, as follows:

@Override
public E dequeue() {
  if(length<=0){
    return null;
  }
  E value = array[start];
  start = (start+1) % array.length;
  length--;
  return value;
}

The peek operation lets us see the element that would be dequeued next, without removing it. It is, of course, simpler. We just return the next element to be dequeued. This is shown in the following code:

@Override
public E peek() {
  if(length<=0){
    return null;
  }
  return array[start];
}

A queue backed up by an array can be resized in a similar manner as described for the case of a stack, and this too will be O(n), since we must copy all the old elements to the newly allocated array one by one.

Variable-sized queue using a linked list

Just like a stack, we want to implement a queue using a linked list. We need to remember that all operations must be O(1) in running time. If we enqueue by appending new elements at the beginning of the linked list, we will need to remove elements from the end of the list during dequeuing. This will not work as removal of an element from the end of a linked list is O(n). But appending at the end of a linked list is O(1) and so is removing from the beginning of the list. Hence, the end of the queue, where new elements are enqueued, would be the end of the list. And the start of the queue, where the elements are dequeued from, would be the beginning of the linked list.

Given this, the implementation of a queue using a linked list is straightforward. Again, we create an instance of the list only using a getNewLinkedList() method, which can be overridden by a subclass to use a different linked list, as follows:

public class QueueImplLinkedList<E> implements Queue<E>{
  protected LinkedList<E> list = getNewLinkedList();

  protected LinkedList<E> getNewLinkedList(){
    return new LinkedList<>();
  }

The enqueue operation simply appends at the end of the list as follows:

  @Override
  public void enqueue(E value) {
    list.appendLast(value);
  }

The dequeue operation first checks if the list is empty so it can return null, and then it simply removes the first element from the list. It must also return the element that it just removed:

  @Override
  public E dequeue() {
    if(list.getLength()==0){
      return null;
    }
    E value = list.getFirst();
    list.removeFirst();
    return value;
  }

Just like the dequeue operation, the peek operation first needs to check whether the list is empty, in which case it has to return a null value, otherwise it simply returns the element at the beginning of the list that would be dequeued on the next dequeue operation, as shown in the following code:

  @Override
  public E peek() {
    if(list.getLength()==0){
      return null;
    }
    return list.getFirst();
  }
}