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

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.

 


JavaScript Data Structures 

Cover

Contents

  1. The String Object
  2. The Array object
  3. Typed Arrays I
  4. Typed Arrays II
  5. Speed dating - the art of the JavaScript Date object
  6. Doing JavaScript Date Calculations
  7. A Time Interval Object
  8. Collection Object
  9. Stacks, Queue & Deque
  10. The Linked List
  11. a Lisp-like list
  12. The Binary Tree
  13. Bit manipulation
  14. Active Logic, Truthy and Falsey 

 

 jemsicon

 

 

 

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
 


Getting Started With jQuery - Advanced Ajax Characters & Encoding

One of the biggest problems you encounter in using Ajax is the dreaded character encoding. No matter what data format you select, the data is actually transmitted as text. But it isn't as simple as th [ ... ]



Speed dating - The Art of the JavaScript Date Object

JavaScript's way of working with dates is simple but perhaps this is part of the problem. The Date object is so simple that it can be difficult to work out how to do things like date arithmetic. Find  [ ... ]


Other Articles

 

 
 

 

blog comments powered by Disqus

 

<ASIN:0596806752>

<ASIN:0321812182>

<ASIN:1491901888>

<ASIN:144934013X>

<ASIN:193398869X>

<ASIN:1449373216>



Last Updated ( Friday, 23 September 2016 )
 
 

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