Skip to content

Instantly share code, notes, and snippets.

@jesslilly
Created March 16, 2014 02:28
Show Gist options
  • Save jesslilly/9577700 to your computer and use it in GitHub Desktop.
Save jesslilly/9577700 to your computer and use it in GitHub Desktop.
Stack with push, pop, and min all of complexity O(1). With unit tests.
#!/usr/bin/env node
/*
* Design a stack with a push, pop, and min method.
* Min returns the smallest element.
* All methods must operate in O(1) time.
* I implemented this with simple numbers, but I could enhance it
* to use objects with a comparator function.
*/
var Stack = (function() {
var Stack = function() {
// _data [ 3, 1, 2, 0, 4, -1 ]
// _mins [ 3, 1, 1, 0, 0, -1 ]
this._data = [];
this._mins = [];
this._top = null;
};
Stack.prototype.push = function(newNum) {
this._top = (this._top === null) ? 0 : ++this._top;
this._data.push(newNum);
if (this._isMin(newNum))
this._mins.push(newNum);
else
this._mins.push(this._mins[this._top - 1]);
return this;
};
Stack.prototype.pop = function() {
this._top = (this._top === 0) ? null : --this._top;
this._data.pop();
this._mins.pop();
return this;
};
Stack.prototype.getMin = function() {
if (this._top === null) {
return null;
}
return this._mins[this._top];
};
Stack.prototype._isMin = function(newNum) {
if (this._mins.length === 0) {
return true;
}
return (newNum < this._mins[this._top - 1]);
};
return Stack;
}());
var expect = function(num1) {
return {
toBe : function(num2) {
if (num1 === num2) {
console.log( "ok. " + num1 + " = " + num2);
} else {
console.log( "FAIL! " + num1 + " != " + num2);
}
}
};
};
// Tests.
var s1 = new Stack();
s1.push(3).push(1).push(2);
expect(s1.getMin()).toBe(1);
expect(s1.pop().getMin()).toBe(1);
expect(s1.pop().getMin()).toBe(3);
expect(s1.pop().getMin()).toBe(null);
expect(s1.push(-1).getMin()).toBe(-1);
expect(s1.push(-2).getMin()).toBe(-2);
expect(s1.push(1).getMin()).toBe(-2);
expect(s1.push(-3).getMin()).toBe(-3);
expect(s1.pop().getMin()).toBe(-2);
var s2 = new Stack();
expect(s2.push(0).push(0).push(0).pop().getMin()).toBe(0);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment