Thursday, March 26, 2015

circular stack

Used for undo operations.
circular-stack:
    a, capacity
    count = 0
    top = 0
    circular-stack(capacity):
        capacity = capacity
        a = new [capacity]
        
    push(x):
        a[top] = x
        top++
        if top == capacity:
            top = 0
        if count < capacity:
            count++
    x pop():
        if empty():
            throw
        if top == 0:
            top = capacity
        top--
        count--
        return a[top]
    x peek():
        if empty():
            throw
        tos = (top == 0 ? capacity : top) -1
        return a[tos]
    isempty():
        return count == 0
    count():
        return count
    clear():
        top = count = 0
    foreach():
        tos = top
        for i = 0, i < count, i++:
            tos = (tos == 0 ? capacity : tos) -1
            yield a[tos]

[Hat tip to 2048]

No comments:

Post a Comment