- 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