Javascript data structures - Stacks
Wednesday, 08 December 2010
Article Index
Javascript data structures - Stacks
Queue and Deque

Stacks, queues and deques are the most basic of the slightly more advanced data structures you will meet. The good news is that they are very, very easy to implement in JavaScript.

 

This is one of a series of articles on implementing data structures in JavaScript.

See also:

 

 

Banner

 

JavaScript has a really useful Array object that can be used to create some of the most basic data structures - the stacks and queues. In this short article we take a look at how to create stacks and queues and describe some aspects of why they are useful.

The LIFO stack

It is always difficult to know which stack is the most basic but the LIFO or Last In First Out stack is perhaps the most commonly used. A simple array object already has the two basic methods needed to create a LIFO stack push and pop. The push method will add any object to the top of the stack and the pop method will remove it. To treat an array as a LIFO stack you simply create an instance and use push and pop.

For example:

var stack=new Array();
stack.push("A);
stack.push("B");
stack.push("C"
alert(stack.pop());
alert(stack.pop());
alert(stack.pop());

If you try this out you will see the alerts display "C", "B" and "A". This is the key property of a LIFO stack - it reverses the order of the data you store on it.

You can use any Array object as a LIFO stack and it is sometimes useful to treat an array as a stack for a while and then go back to working with it as an array. If you really want to create a stack object that can only be used as a stack then you have to encapsulate an Array and expose only the push and pop methods.

That is:

function Stack()
{
this.stac=new Array();
this.pop=function(){
  return this.stac.pop();
}
this.push=function(item){
  this.stac.push(item);
}
}

If you make the stac Array object private using a closure say then the only operations allowed on Stack are push and pop.

var stack=new Stack();
stack.push("A");
stack.push("B");
stack.push("C");
alert("Hello");
alert(stack.pop());
alert(stack.pop());
alert(stack.pop());

and again you will see the data retrieved in the order "C", "B", "A".

Notice that while we refer to the "top of the stack" push adds the object to the "end" of the array and pop removes the final element. That is if the array has three items push stores its object in array[3]. Also notice that if you try to pop a value that doesn't exist i.e. pop an empty stack the result is undefined.

A typical stack will often allow you to manipulate the stack pointer say or peek at the value on the top of the stack i.e. retrieve it without removing it but these are generally not necessary. Also notice that as you can push and pop any object onto the stack you can use it in very sophisticated ways. For example, if you need to store an object on the stack long with the time it was created you don't need to create a more complex Stack object because you can simply push a composite object:

push({MyData,Time});

Also notice that there is no need to worry about problems of enumeration - because you don't naturally ever need to enumerate a stack structure.

 

Banner

<ASIN:0596805527>

<ASIN:0470684143>

<ASIN:1934356670>



Last Updated ( Tuesday, 15 January 2013 )
 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.