Wednesday, May 06, 2015

circular queue, overwrite when full

Used for last n items from a stream.
circular-queue:
    capacity
    buffer
    head = 0
    tail = 0
    count = 0

    //ctor
    circular-queue(capacity):
        if capacity <= 0:
            throw
        capacity = capacity
        buffer = new [capacity]

    enqueue(x):
        buffer[tail] = x
        //count
        //count stays at capacity when full
        if count < capacity:
            count++
        //tail
        tail++
        if tail == capacity:
            tail = 0
        //head
        //when queue is full, head = tail
        if count == capacity:
            head = tail

    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]
    
    x[] foreach():
        for i = 0, i < count, i++:
            yield a[(head +i) % capacity]
last-n-items(stream, n):
    if n < 0:
        throw
    if n == 0:
        return [] //empty
    q = new circular-queue(n)
    foreach item in stream:
        q.enqueue(item)
    items = new
    while !q.empty():
        items.add(q.dequeue())
    return items

[Hat tip to ctci]

No comments:

Post a Comment