JavaScript Data Structures - Stacks, Queues and Deques
Written by Ian Elliot   
Thursday, 10 February 2022
Article Index
JavaScript Data Structures - Stacks, Queues and Deques
The FIFO Stack or Queue

The FIFO stack or Queue

The close relative of the LIFO stack is the FIFO - First In First Out stack - also known as the Queue because it mimics the behaviour of a queue in the real world. That is you store an item on the back of the queue and retrieve it from the front. 

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 the items are retrieved in the order that they were stored.

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(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 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. Speed dating - the art of the JavaScript Date object
  5. Doing JavaScript Date Calculations
  6. A Time Interval Object
  7. Collection Object
  8. Stacks, Queue & Deque
  9. The Linked List
  10. A Lisp-like list
  11. The Binary Tree
  12. Bit manipulation
  13. Typed Arrays I
  14. Typed Arrays II
  15. Master JavaScript Regular Expressions
    * First Draft

 jemsicon

 

 

 

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

 

Banner
 


JavaScript Jems - Objects Are Anonymous Singletons

JavaScript should not be judged as if it was a poor version of the other popular languages - it isn't a Java or a C++ clone. It does things its own way.  In particular, every object can be regard [ ... ]



JavaScript Canvas - Typed Arrays

Working with lower level data is very much part of graphics. This extract from Ian Elliot's book on JavaScript Graphics looks at how to use typed arrays to access graphic data.


Other Articles

 

raspberry pi books

 

Comments




or email your comment to: comments@i-programmer.info

 

<ASIN:1871962579>

<ASIN:1871962560>

<ASIN:0596517742>

<ASIN:0596806752>

 



Last Updated ( Thursday, 10 February 2022 )