Saturday, February 08, 2014

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

Use deque and map.
q<T>:
    dq  //<T>
    map //<T, queue<node>>
    
    enqueue(T t):
        node = dq.enqueue(t)
        q
        if map.haskey(t):
            q = map[t]
        else:
            q = new queue<node>()
            map[t] = q
        q.enqueue(node)
    
    T dequeue():
        if dq.empty():
            throw "empty"
        t = dq.dequeue()
        q = map[t]
        q.dequeue()
        if q.empty():
            map.remove(t)
        return t
    
    bool find(T t):
        if t == null:
            throw
        return map.haskey(t)
    
    delete(T t):
        if !map.haskey(t):
            throw "item not present"
        q = map[t]
        node = q.dequeue()
        if q.empty():
            map.remove(t)
        dq.delete(node)

[Hat tip to MB]

No comments:

Post a Comment