Wednesday, November 14, 2012

circular queue with array

circular-queue:
    capacity
    buffer
    head = 0
    tail = 0
    count = 0

    //ctor
    circular-queue(capacity):
        capacity = capacity
        buffer = new [capacity]

    enqueue(x):
        if count == capacity:
            throw "full" // or resize()
        buffer[tail] = x
        //count
        count++
        //tail
        tail++
        if tail == capacity:
            tail = 0
    
    resize():
        buffercopy = new [capacity *2] //overflow
        j = head
        for i = 0, i < capacity, i++:
            buffercopy[i] = buffer[j]
            j = j++ % capacity
        head = 0
        tail = capacity
        capacity = buffercopy.length
        buffer = buffercopy
    
    x dequeue():
        if count == 0:
            throw "empty"
        x = buffer[head]
        //count
        count--
        //head
        head++
        if head == capacity:
            head = 0
        return x
    
    bool isempty():
        return count == 0
    
    int size():
        return count

    clear():
        head = tail = count = 0
    
    x peek():
        if count == 0:
            throw "empty"
        return a[head]

Iterator for circular queue:
// usage
cq = new circular-queue<int>()
e = cq.getEnumerator()
while e.hasnext():
    x = e.next()

// OR
foreach x in cq:
    x

// enumerator
class circular-queue: ienumerable
    ienumerator get-enumerator():
        return new cq-enumerator(this)

class cq-enumerator:
    eindex
    ecount
    
    q-enumerator(cq):
        // cache all members
        buffer, head, tail, count, capacity
        reset()
    
    reset():
        eindex = head
        ecount = 0
    
    bool hasnext():
        return ecount < count
    
    x next():
        if !hasnext():
            throw "no more elements"
        x = buffer[eindex]
        ecount++
        eindex = eindex++ % capacity
        return x

No comments:

Post a Comment