Sunday, June 21, 2015

implement 3 stacks in an array

- Each stack has a neighbor stack on its right.
- push(): push into current stack. If current stack is full, borrow from neighbor (which, if full, borrows from its neighbor and so on recursively) and push. If all stacks are full, throw.
- move(): If the stack has space, shift its elements to right and lend. If not, check its neighbor. When all stacks are full, the calls will loop around to same stack. So note the first stack that calls move(). Adjust top and capacity here.
- shift: shift elements to right and wrap around.
- pop(): Typical. No adjusting here.

Note:
It is better that move() returns false and push() throws "stacks full" instead of move() throwing. The exception stack would be cluttered if move() throws as it would throw after looping back. stack-combined could throw in its push() by keeping its own count but then logic is in different classes and stack is not whole.

stack:
    a
    id
    top // no need to track start
    capacity
    count
    stack neighbor
    
    stack(a, id, top, capacity):
        a = a
        id = id
        top = top
        capacity = capacity
        count = 0
    
    // push into current or borrow from neighbor and push
    push(T x):
        if count < capacity:
            push_(x)
        else if neighbor.move(id):
            capacity++
            push_(x)
        else:
            throw "stacks full"
    push_(T x):
        a[top] = x
        // last stack overflows into first
        top = mod(top+1, a.length())
        count++
    
    // check current stack and then neighbor
    bool move(id):
        // all stacks are full and back to same stack
        if id == this.id:
            return false
        if count < capacity:
            shift()
            top = mod(top+1, a.length())
            capacity--
            return true
        if neighbor.move(id):
            shift()
            top = mod(top+1, a.length())
            return true
        return false
    
    // move elements to right
    shift():
        i = top
        for c = 0, c < count, c++:
            // wrap around, so a[i] = a[i-1] except a[0] = a[last]
            previ = mod(i-1, a.length())
            a[i] = a[previ]
            i = previ
        // clear for clarity
        a[i] = null
    
    T pop():
        if count == 0:
            throw "stack {id} empty"
        count--
        top = mod(top-1, a.length())
        t = a[top]
        // clear for clarity
        a[top] = null
        return t

    mod(x, n):
        m = x % n
        if m < 0:
            m += n
        return m

// n stacks with capacity capacity
stack-combined:
    stack-combined(n, capacity):
        // assume equal capacity for all
        a = new [size *n]
        stacks = new stack[n]
        for i = 0, i < n, i++:
            stacks[i] = new stack(a, id: i, top: capacity*i, capacity)
        // 0's neighbor is 1, (n-1)'s is 0
        for i = 0, i < n, i++:
            stacks[i].neighbor = stack[mod(i+1, n)]
    
    push(id, x):
        if !(0 <= id < n):
            throw
        stacks[id].push(x)
    pop(id):
        if !(0 <= id < n):
            throw
        stacks[id].pop()

[Hat tip to ctci]

No comments:

Post a Comment