Javascript Data Structures - Stacks, Queue and Deque
Javascript Data Structures - Stacks, Queue and Deque
Written by Mike James   
Thursday, 24 March 2016
Article Index
Javascript Data Structures - Stacks, Queue and Deque
The 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.

 

Chapter List 

  1. A collection object

  2. JavaScript Data Structures - the String Object

  3. JavaScript Data Structures - the Array object

  4. Speed dating - the art of the JavaScript Date object

  5. Javascript data structures - Stacks

  6. JavaScript Data Structures - The Linked List

  7. JavaScript data structures - a Lisp-like list

  8. Stacks, Queue and Deque

  9. Javascript data structures - The Binary Tree

  10. JavaScript Data Structures - Typed Arrays I

  11. JavaScript Data Structures - Typed Arrays II

 

 

Banner

 

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.

 

jemsicon

  

The FIFO stack or Queue

The close relative of the LIFO stack is the FIFO - First In First Out stack - also known as the Queue because it mimics the behaviour of a queue in the real world. That is you store an item on the back of the queue and retrieve it from the front. 

Once again the Array object provides methods that enable us to create a Queue directly. The unshift method adds an item to the front of the Array. To create a queue we have to remove items from the end of the Array and this we can do using the pop method again.

That is to treat an Array as a queue all we have to do is

var Q=new Array();
Q.unshift("A);
Q.unshift("B");
Q.unshift("C");

alert(Q.pop());
alert(Q.pop());
alert(Q.pop());

If you try this out you will see the data retrieved in the order "A", "B" and "C". That is a queue or a FIFO stack doesn't change the order of the data the items are retrieved in the order that they were stored.

A queue is useful when ever you have data to deal with and not enough time to deal with it all. You simply add the data you can't deal with to the queue and deal when it when you can. The queue ensures that it is dealt with in the order it arrived. Another name for a queue is a buffer.

If you want to create a queue object you can follow the basic idea used for the LIFO stack:

function Queue()
{
this.stac=new Array();
 this.dequeue=function(){
  return this.stac.pop();
}

this.enqueue=function(item){
  this.stac.unshift(item);
}
}

var Q=new Queue();
Q.enqueue("A");
Q.enqueue("B");
Q.enqueue("C");

alert(Q.dequeue());
alert(Q.dequeue());
alert(Q.dequeue());

The methods enqueue and dequeue aren't standard names but they are often used. Another controversy is over whether you join the head or start of the queue ot the tail or end of the queue. It all depends on how you think about it and as long as you get the basic FIFO action it all works.

As in the case of a stack trying to remove something from an empty queue returns undefined. You can also queue complex objects and augment the queue with additional methods to return the number of items in the queue and even the nth item in the queue.

There are more complex types of queue that you can implement but these are less commonly encountered.

For example, the priority queue works int he same way but when you enqueue an item you can also specify its priority. When items are dequeued they are returned in priority order rather than the order that they arrived in.  You can implement a priority queue either by keeping the array sorted in priority order or simply search for the value to be returned in an unsorted list.

You can also use more complex data structures to implement a priority queue such as the heap - see a future article for details.

 

<ASIN:0596805527>

<ASIN:0596517742>

<ASIN:1593275404>

<ASIN:1118026691>



Last Updated ( Friday, 23 September 2016 )
 
 

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