Implement a stack that returns its largest item in O(1)
A browser-based level editor keeps an undo stack of placed blocks. The toolbar always shows the tallest block still on the stack, and it re-renders after every push and every undo, so finding that block must not scan the whole stack.
Implement a class PeakStack: a last-in, first-out stack that also reports its largest item in constant time.
const stack = new PeakStack(compare?);
stack.push(...items) // adds items in order (the last argument ends on top); returns the new size
stack.pop() // removes and returns the top item, or undefined when empty
stack.peek() // returns the top item without removing it, or undefined when empty
stack.peak() // returns the largest item currently in the stack, or undefined when empty
stack.size() // number of items
stack.isEmpty() // true when size() is 0
stack.toArray() // a new array of the items, bottom first
compare(a, b) works like the callback of Array.prototype.sort: negative when a is smaller, positive when a is larger, 0 when they tie. Without it, compare with < and > (numbers numerically, strings alphabetically).peak() returns the one pushed most recently.push() with no arguments adds nothing and returns the current size.pop(), peek(), and peak() on an empty stack return undefined and do not throw.peak() must be O(1), even right after a pop(). Stacks in the tests hold tens of thousands of items.toArray() returns a copy: changing it does not change the stack. Each instance has its own items.const heights = new PeakStack();
heights.push(3, 7); // => 2
heights.push(2); // => 3
heights.peek(); // => 2
heights.peak(); // => 7
heights.toArray(); // => [3, 7, 2]
heights.pop(); // => 2
heights.pop(); // => 7
heights.peak(); // => 3
const tasks = new PeakStack((a, b) => a.priority - b.priority);
tasks.push({ id: 'lint', priority: 2 }, { id: 'deploy', priority: 5 }, { id: 'test', priority: 5 });
tasks.peak().id; // => 'test' (ties go to the newest item)