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 if count < capacity: count++ tail = wrapindex(tail +1, n) //when queue is full, head = tail if count == capacity: head = tail x dequeue(): if isempty(): throw "empty" x = buffer[head] count-- head = wrapindex(head +1, n) return x bool isempty(): return count == 0 int size(): return count clear(): head = tail = count = 0 x peek(): if isempty(): throw "empty" return a[head] x[] foreach(): index = head for i = 0, i < count, i++: yield buffer[index] index = wrapindex(index +1) int wrapindex(i, n): index = i %n // -1 or -6 %5 is -1 if index < 0: index += n return index
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) for item in queue: yield item
[Hat tip to ctci]
No comments:
Post a Comment