Javascript Data Structures - Stacks, Queue and Deque
Banner
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

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 which is where the name of the data structure comes from. 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:

 jemsicon

 

Related Articles

JavaScript Data Structures - Typed Arrays I

JavaScript Data Structures - Typed Arrays II

 

To be informed about new articles on I Programmer, install the I Programmer Toolbar, subscribe to the RSS feed, follow us on, Twitter, FacebookGoogle+ or Linkedin,  or sign up for our weekly newsletter.

 

Banner
 


JavaScript Bit Manipulation

Bit manipulation in JavaScript is complicated by the way it attempts to be type free, but it can be done. We take a look at how to work with bits in a browser.



Getting Started With jQuery - Advanced Ajax jqXHR and Events

The jQuery approach to Ajax is built on the jqXHR object which wraps the XmlHttpRequest object that the browser provides. It isn't often that you need delve this deeply into jQuery Ajax, but when you  [ ... ]


Other Articles

 

blog comments powered by Disqus

 

<ASIN:0596806752>

<ASIN:0321812182>

<ASIN:1491901888>

<ASIN:144934013X>

<ASIN:193398869X>

<ASIN:1449373216>



Last Updated ( Thursday, 24 March 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.