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

 

Banner

The FIFO stack or Queue

The close relative of the LIFO stack is the First In First Out stack - also known as the Queue because it mimics the behaviour of a queue in the real world.

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.

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("Hello");
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.

 

The Deque

The most sophisticated of the stack data structures is the deque or double ended queue. To see how this works imagine a deck of cards. You can take a card from the top or bottom of the deck and you can add a card to the top or bottom of a deck. In other words a deque really is a double ended queue in that you can join or leave the queue at the front or the back.

Once again the Array object has an additional method that you can use to implement a deque. The shift method completes the set of "queing" mutator methods and it removes and element from the front or start of the Array.

So we now have

  • pop and push - remove or add to the end of the Array

and

  • shift and unshift - remove or add to the start of the Array.

Creating a Deque object is now very easy:

function Deque()
{
this.stac=new Array();
this.popback=function(){
  return this.stac.pop();
}
this.pushback=function(item){
  this.stac.push(item);
}
this.popfront=function(){
  return this.stac.shift();
}
this.pushfront=function(item){
  this.stac.unshift(item);
}
}

There are no real standard labels for manipulating a deque. The method names used in this example are closest to C++ which used push_back, push_front etc. for a deque. To use it you simply call the methods you need according to where you want to add or remove items.

For example, what does the following code display:

var deque=new Deque();
deque.pushfront("A");
deque.pushfront("B");
deque.pushback("C");
alert(deque.popfront());
alert(deque.popback());

the answer is "B" followed by "C".

Deques aren't as common in simple algorithms and so you might never need to use on. They can be useful however in job scheduling algorithms where there are multiple jobs and agents. Each agent takes tasks from the front of their deque of tasks but if an agent has nothing to do they take tasks from the end of the deque belonging to another agent.

Also See:

 

 

If you would like to be informed about new articles on I Programmer you can either follow us on Twitter, on Facebook , on Digg or you can subscribe to our weekly newsletter.

 

 

Banner


Javascript data structures - the binary tree

Binary trees in JavaScript? Easy with the right storage mapping function. Find out how to code a binary tree right up to a depth first traversal.



Just JavaScript - Object Construction

Object creation is fundamental to all object-oriented languages, but in JavaScript is is left to the programmer to work out how best to do it and often the practice that you encounter isn't the best b [ ... ]


Other Articles

 

<ASIN:0137054890>

<ASIN:0596517742>

<ASIN:1590597273>



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.