deque

node:
    next
    prev
    value
    
dq:
    head, tail = null
    
    node enqueue(T t):
        n = new node(t)
        if head == tail == null:
            head = tail = n
        else:
            tail.next = n
            n.prev = tail
            tail = n
        return n
    
    T dequeue():
        if head == null:
            throw "empty"
        n = head
        if head == tail:
            head = tail = null
        else:
            head = head.next
            n.next = head.prev = null
        return n.value
    
    delete(n):
        if n == null || head == null || tail == null:
            throw
        if n == head && head == tail:
            head = tail = null
        else if n == head:
            head = head.next
            n.next = head.prev = null
        else if n == tail:
            tail = tail.prev
            n.prev = tail.next = null
        else:
            n.prev.next = n.next
            n.next.prev = n.prev
            n.prev = n.next = null
    
    // make an existing node in deque the tail.
    // note: deque cannot be empty, as it has at least 1 node
    // to make the tail.
    makeTail(n):
        if n == null || head == null || tail == null:
            throw
        if n == tail:
            return
        if n == head:
            head = head.next
            head.prev = null
        else:
            n.prev.next = n.next
            n.next.prev = n.prev
        n.prev = n.next = null
        tail.next = n
        n.prev = tail
        tail = n