Double ended queue

A double ended queue is a combination of a stack and a queue. The idea is that you are allowed to insert and remove elements at both ends of the queue. If you remove elements from the side you have inserted, it will behave like a stack. On the other hand, if you insert and remove on opposite ends, it will behave like a queue. You can mix these operations and use them in any order you like. The following figure shows a few operations to clarify this idea:

A double ended queue has the following operations all with a complexity of O(n):

• Push: This inserts an element at the beginning
• Pop: This removes an element from the beginning
• Inject: This inserts an element at the end
• Eject: This removes an element from the end
• Peek: This checks the first element
• PeekLast: This checks the last element

A double ended queue will be represented by the following interface:

public interface DoubleEndedQueue<E> extends Stack<E> {
  void inject(E value);
  E eject();
  E peekLast();
}

Note that since a double ended queue has push and pop operations just like a stack and it preserves the same meaning, we create this interface extending the Stack interface.

Fixed-length double ended queue using an array

Since we have created the double ended queue as an extension of a stack, one would expect its implementation to extend a stack implementation as well. However, remember that a double ended queue is both a stack and a queue. The array-based implementation for a queue was more complex than that for a stack due to rollover of the indexes. We don't want to reprogram those, so we choose to extend a queue implementation instead of a stack implementation, as shown in the following code:

public class DoubleEndedQueueImplArray<E> extends QueueImplArray<E> implements DoubleEndedQueue<E> {

We initialize the queue to the fixed length, as follows:

  public DoubleEndedQueueImplArray(int size) {
    super(size);
  }

This is appended at the end of the double ended queue, which is the same as the enqueue operation of a queue:

  @Override
  public void inject(E value) {
    enqueue(value);
  }

The eject operation is the removal of an element from the end of the double ended queue. We don't have an equivalent operation in a simple queue. So, we must code for it as follows:

  @Override
  public E eject() {
    if (length <= 0) {
      return null;
    }

The end has to decrement by one with a provision for rollover. But if the end is already at zero, it will become negative, which will not work well with the modulo operator, because it will return a negative value. To always keep it positive, we add the length of the array to it. Note that it does not change the remainder when pided by the length of the array. This is shown in the following code:

    end = (end + array.length - 1) % array.length;
    E value = array[end];
    length--;
    return value;
  }

The peekLast operation simply needs to return the element that would have been returned by the eject operation without modifying anything, as shown in the following code:

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

The push operation is the insertion of an element at the beginning of the double ended queue. There is no equivalent operation in a simple queue. Hence, we need to code for it as follows:

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

This operation is very similar to updating the end index eject operation, as shown in the following code:

    start = (start + array.length - 1) % array.length;
    array[start] = value;
    length++;
  }

The pop operation is the removal of the element at the beginning of the queue, which is the same as the dequeue operation of an ordinary queue. This is illustrated in the following code:

  @Override
  public E pop() {
    return dequeue();
  }
}

Note that we don't write any code for the peek operation, which should return the element at the beginning of the double ended queue, as it is the same as the peek operation for a simple queue.

The array-based implementation is, of course, fixed in size and cannot hold more elements than it's fixed size. Next, we develop a linked list-based implementation.

Variable-sized double ended queue using a linked list

We had earlier used a simple linked list to implement both a queue and a stack. However, remember again that all operations must be O(1). Now, we must both add and remove elements at both ends of the underlying linked list. We know that removal from the end of a singly linked list is O(n) and we cannot use it. So, we must use a doubly linked list instead.

This time we do not have to worry about rollovers and so we will extend the linked list implementation of a stack, which is the natural choice. We will replace its singly linked list with a doubly linked list by overriding the getLinkedList() method, as follows:

public class DoubleEndedQueueImplLinkedList<E> extends StackImplLinkedList<E> implements DoubleEndedQueue<E> {

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

The inject operation inserts a new element at the end of the list as shown in the following code:

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

The eject operation must remove and return the last element of the list. This is illustrated in the following code:

  @Override 
  public E eject() {
    if(list.getLength()==0){
      return null;
    }
    E value = list.getLast();
    list.removeLast();
    return value;
  }

Finally, the peekLast() method will just return the last element of the doubly linked list as follows:

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

We only had to implement the inject(), eject(), and peekLast() methods as the other methods are already implemented by the stack we extend.