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 Associative Array
  2. The String Object*
  3. The Array object
  4. Typed Arrays I*
  5. Typed Arrays II*
  6. Speed dating - the art of the JavaScript Date object
  7. Doing JavaScript Date Calculations*
  8. A Time Interval Object*
  9. Collection Object
  10. Stacks, Queue & Deque
  11. The Linked List*
  12. A Lisp-like list*
  13. The Binary Tree
  14. Bit manipulation*
  15. Active Logic, Truthy and Falsey *
  16. Master JavaScript Regular Expressions*

 

 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
 


Master JavaScript Regular Expressions

Regular expressions can seem complex but the biggest reason for this is that most programmers don't take them seriously enough. Spend just a little time finding out how they work and you can do amazin [ ... ]



jQuery 3 - Consuming Promises

Promises are a way of organizing asynchronous calls that is better than using callbacks. The callbacks are still there but they are come with a degree of organization. Previously jQuery was criticized [ ... ]


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.