[Project_owners] how to implement bounded stack in javascript?

Konstantin Svist fry.kun at gmail.com
Sun Apr 16 12:48:19 EDT 2006


lemme take a crack at it..

_boundedStack: {
   _max: 500,
   _stack: [],
   _current: 0,   // next position to be written
   _overfly: false,
   push: function(obj) {
     var current = this._current;	// minor optimization
     this._stack[current] = obj;
     if (current >= this._max) {
       this._current = 0;
       this._overfly = true;
     }
   },
   length: function() { return this._stack.length; },	// note_1
   item: function(idx) {		// note_2
     if (this._overfly) {
       idx += this._current;
       if (idx >= this._max) { idx -= this._max; }
     }
     return this._stack[idx];
   }
}

note_1: it'll probably be a little faster to call myStack._stack.length 
directly

note_2: caller needs to bound-check. this can be done implicitly: get 
the length first, then only ask for elements within that length.


logic check: _current points to next field to write into. when getting 
an element by index, _current points to oldest element iff there was an 
overflow.


By the way, never skimp on the curly braces {}: for some reason Fx 1.0 
favors the code with lots of {}s, by a slight margin (or so my testing 
showed).






also, does it have to be an array? what if you just use a linked list of 
objects? it may work faster if you keep retrieving the whole list each 
time, not just a certain item

_boundedStack: {
   first: null,
   last: null,
   len: 0,
   max: 500,
   push: function(obj) {
     if (null == this.last) { this.last = obj; }
     else {
       this.last.next = obj;
       this.last = obj;
     }
     this.len++;
     if (null == first) { first = obj; }
     else if (this.len >= this.max) {
         this.first = this.first.next;
         this.len--;
     }
   }
}

obj should be fairly easy to implement, i think..
to get the length of your stack, just grab the len variable
to get the list, get the first element then .next until .next == null


disclaimer: i didn't test either implementation, may i messed it up =)

~Fry-kun


More information about the Project_owners mailing list