Created
November 16, 2018 00:52
-
-
Save AlexeiDarmin/9c988b440d397301fb4c9293e4737313 to your computer and use it in GitHub Desktop.
SetOfStacks should be composed of several stacks and should create a new stack once the previous one exceeds capacity.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
Stack of plates: Imagine a literal stack of plates. If the stack gets too high, it might topple. | |
Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. | |
Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks and | |
should create a new stack once the previous one exceeds capacity. | |
SetOfStacks.push() and SetfStacks.pop() should behave identically to a single stack | |
That is pop should return the same valeues as it would if there were just a single stack. | |
*/ | |
class SetOfStacks<T> { | |
threshold: number | |
stacks: MyStack<T>[] | |
stackSizes: number[] | |
constructor(threshold: number) { | |
this.threshold = threshold | |
this.stacks = [] | |
this.stackSizes = [] | |
} | |
push(num: T) { | |
let stack = null | |
let stackIndex = 0 | |
while (!stack && stackIndex < this.stacks.length) { | |
if (this.stackSizes[stackIndex] < this.threshold) { | |
stack = this.stacks[stackIndex] | |
} else { | |
++stackIndex | |
} | |
} | |
if (!stack) { | |
this.pushStack() | |
stack = this.peakStack() | |
} | |
stack.push(num) | |
++this.stackSizes[stackIndex] | |
} | |
pop() { | |
const stack = this.peakStack() | |
const item = stack.pop() | |
--this.stackSizes[this.stacks.length - 1] | |
if (stack.isEmpty()) { | |
this.popStack() | |
} | |
return item | |
} | |
pushStack(){ | |
this.stacks.push(new MyStack()) | |
this.stackSizes.push(0) | |
} | |
popStack() { | |
console.log('popping stack') | |
this.stacks.pop() | |
this.stackSizes.pop() | |
} | |
peakStack() { | |
return this.stacks[this.stacks.length - 1] | |
} | |
isEmpty() { | |
return this.stacks.length === 0 | |
} | |
} | |
let newstackset = new SetOfStacks(2) | |
newstackset.push(2) | |
newstackset.push(1) | |
newstackset.push(1) | |
newstackset.push(3) | |
newstackset.push(0) | |
while (!newstackset.isEmpty()) { | |
for (let i = 0; i < newstackset.stacks.length; ++i) { | |
console.log('stack size at ',i, newstackset.stackSizes[i]) | |
} | |
console.log(newstackset.pop().data) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment