Deque

External

• https://en.wikipedia.org/wiki/Double-ended_queue

Internal

• Data Structures
• Queue
• Stack

Overview

A deque is a dynamic set that generalizes the concept of queue. The elements can be enqueued and dequeued both from the head and the tail of the deque. The INSERT and DELETE operations have each two versions:

• insert to head or push.
• delete from head or pop.
• insert to tail or inject.
• delete from tail or eject.

Implementation

The following implementation uses an array of length n for storage. Because we want to use all n elements of the array for storage of the deque elements, we need an extra boolean member variable "full" to tell whether the structure is empty or full - in both cases the head pointer overlaps the tail pointer.

/**
 * A deque of ints.
 */
public class Deque {

    private int[] storage;
    private int head;
    private int tail;
    private boolean full;

    public Deque(int capacity) {

        this.storage = new int[capacity];
        this.head = 0;
        this.tail = 0;
        this.full = false;
    }

    public void push(int i) throws DequeOverflowException {

        if (full) {

            throw new DequeOverflowException();
        }

        head = head - 1;

        if (head < 0) {

            head = storage.length - 1;
        }

        storage[head] = i;

        if (head == tail) {

            this.full = true;
        }
    }

    public int pop() throws DequeUnderflowException {

        if (head == tail && !full) {

            throw new DequeUnderflowException();
        }

        int result = storage[head];

        head = head + 1;

        if (head == storage.length) {

            head = 0;
        }

        full = false;

        return result;
    }

    public void inject(int i) throws DequeOverflowException {

        if (full) {

            throw new DequeOverflowException();
        }

        storage[tail] = i;

        tail = tail + 1;

        if (tail == storage.length) {

            tail = 0;
        }

        if (head == tail) {

            full = true;
        }
    }

    public int eject() throws DequeUnderflowException {

        if (head == tail && !full) {

            throw new DequeUnderflowException();
        }

        tail = tail - 1;

        if (tail < 0) {

            tail = storage.length - 1;
        }

        full = false;

        return storage[tail];
    }

    public boolean isEmpty() {

        return head == tail && !full;
    }

    public boolean isFull() {

        return full;
    }
}