Double-Ended Queue

data-structures computer-science

Definition

Double-Ended Queue

A double-ended queue (commonly abbreviated as deque) is a linear data structure that allows symmetric access to its elements. Unlike a standard queue or stack, elements can be added to or removed from both the front and the back.

Consequently, a deque can behave as both a FIFO queue and a LIFO stack.

Visual Representation

The following diagram illustrates the four primary operations of a deque:

Complexity

Operation	Time Complexity
$\mathrm{addFirst}$/$\mathrm{addLast}$	$O(1)$
$\mathrm{pollFirst}$/$\mathrm{pollLast}$	$O(1)$
$\mathrm{peekFirst}$/$\mathrm{peekLast}$	$O(1)$
$\mathrm{search}$	$O(n)$

Implementations

Java Implementation (Circular Buffer)

The following implementation utilizes a circular array with power-of-two sizing to enable efficient bitwise masking for index wrapping.

 public class DEQueue {
    private int mask = (1 << 3) - 1;
    private String[] es = new String[mask + 1];
    private int head, tail;
 
 
    public void addFirst(String e) {
        es[head = (head - 1) & mask] = e;
        if (tail == head) {
            doubleCapacity();
        }
    }
 
    public String pollFirst() {
        String result = es[head];
        es[head] = null;
        if (tail != head) {
            head = (head + 1) & mask;
        }
        return result;
    }
 
    public String peekFirst() {
        return es[head];
    }
 
    public void addLast(String e) {
        es[tail] = e;
        tail = (tail + 1) & mask;
        if (tail == head) {
            doubleCapacity();
        }
    }
 
    public String pollLast() {
        if (tail != head) {
            tail = (tail - 1) & mask;
        }
        String result = es[tail];
        es[tail] = null;
        return result;
    }
 
    public String peekLast() {
        return es[(tail - 1) & mask];
    }
 
    public int size() {
        return (tail - head) & mask;
    }
 
    private void doubleCapacity() {
        mask = (mask << 1) | 1;
        String[] newes = new String[mask + 1];
        int i = 0, j = 0;
        while (i < head) {
            newes[j++] = es[i++];
        }
        j = head += es.length;
        while (i < es.length) {
            newes[j++] = es[i++];
        }
        es = newes;
    }
}