Double-Ended Queue

data-structures

Definition

Double-Ended Queue

A double-ended queue is a queue that allows symmetric access on both sides, i.e. behaviour is variable (FIFO, LIFO, …).

Implementations

Java Implementation

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