queue with O(1) find() and delete()

Use deque and map.

node{T}:
    T value
    node{T} prev
    node{T} next

// dq interface for deleting node
dq{T}:
    node{T} enqueue(t):
    delete(node{T} n):

q{T}:
    dq  //{T}
    map //{T, queue{node{T}}}
    
    enqueue(T t):
        node = dq.enqueue(t)
        if has(t):
            nodeq = map[t]
        else:
            nodeq = new queue{node{T}}()
            map[t] = nodeq
        nodeq.enqueue(node)
    
    T dequeue():
        if dq.empty():
            throw "empty"
        t = dq.dequeue()
        deleteFromMap(t)
        return t
    
    bool has(T t):
        return map.hasKey(t)
    
    bool delete(T t):
        if !has(t):
            return false
        node = deleteFromMap(t)
        dq.deleteNode(node)
        return true
    
    deleteFromMap(T t):
        nodeq = map[t]
        node = nodeq.dequeue()
        if nodeq.isEmpty():
            map.removeKey(t)
        return node
    
    bool isEmpty():
        return dq.isEmpty()
    int count():
        return dq.count()

If the map cannot contain null keys then t cannot be null. Workaround is to use NullObject pattern as:

nullT = new T()
enqueue(T t):
    t = t ?? nullT
    ...

[Hat tip to MB]