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.

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();
  }
}