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.

JavaScript Data Structures 

Contents

1. The Associative Array
2. The String Object
3. The Array object
4. Speed dating - the art of the JavaScript Date object
5. Doing JavaScript Date Calculations
6. A Time Interval Object
7. Collection Object
8. Stacks, Queue & Deque
9. The Linked List
10. A Lisp-like list
11. The Binary Tree
12. Bit manipulation
13. Typed Arrays I
14. Typed Arrays II
15. Master JavaScript Regular Expressions
    * First Draft

JavaScript has a really useful Array object that can be used to create some of the most basic data structures - 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 pushed A, B and then C byt you got back C, B and then A.

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(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 already stored i.e. array[0], array[1] and array[2] then 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. You could test for this error in the Stack object and throw an exception or some other error if the user attempts to pop an empty stack. 

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 "non-stack" operations 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.