[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 

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 

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 

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;
     if (null == first) { first = obj; }
     else if (this.len >= this.max) {
         this.first = this.first.next;

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 =)


More information about the Project_owners mailing list