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


Just JavaScript - In The Beginning Was The Object

JavaScript is a very subtle and sophisticated language and it deserves to be treated in its own right and not as a poor copy of other object-oriented language. In this first chapter of Just JavaScript [ ... ]



Javascript Jems - Lambda expressions

JavaScript has lambda expressions in all but name. Find out how they work and how to use them.


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.