[Project_owners] how to implement bounded stack in javascript?

Eric H. Jung grimholtz at yahoo.com
Sun Apr 16 18:17:33 EDT 2006


Thanks, but this seems to be another attempt at a bounded queue (not stack). I think I've solved
the bounded queue problem but am not able to solve the bounded stack... so I'm going to implement
the bounded queue. The user will be forced to view the data from eldest to newest instead of
newest to eldest.


--- Konstantin Svist <fry.kun at gmail.com> wrote:

> 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
> _______________________________________________
> Project_owners mailing list
> Project_owners at mozdev.org
> http://mozdev.org/mailman/listinfo/project_owners
> 



More information about the Project_owners mailing list