DS — Queue implementation in JS

Everyone working with programming probably heard about Queue, Stack, etc… at least once in his life, right? Some of you may be familiar with these concepts already, some may be not. Sometimes for some data structure, to understand concept is one thing, to actually implement it in practice (aka. in a specific language) is completely another challenge.

Today I will discuss about Queue and how to implement it in JavaScript easily — and effectively.

So what is Queue?

In plain English, queue is

Image Credit : https://headinablender.files.wordpress.com/2013/06/queue.jpg

Yup, exactly as you see. In Data structures language, Queue is dynamic set in which:

• Element is inserted (ENQUEUE) to the end of the Queue (tail).
• Element is deleted/removed (DEQUEUE) from the beginning of the Queue (head).

And the Delete operation is based on FIFO (First-In, First-Out) — like in real queue, the longest stayed person (aka the first on arrived to queue) got to go first.

In general, basic Queue structure needs to support two main operations:

• EnQueue
• DeQueue

Let’s talk a bit about why Queue is considered an effective data structure. Consider job scheduling case for example: You create a queue of jobs that need to be done in consecutive order. Every time you finish a job, you move on to the next one but getting the first one in the queue. Every time a new job assigned to you, it will be added to the end of the queue, waiting for its turn.

This ensures that no job will need to wait for too long to be executed or be forgotten.

Job Scheduling — EnQueue() and DeQueue()

OK, that should give you a clear idea about Queue. Now we will move on to how to implement it effectively in JS.

Analysis

The simplest way to implement Queue in JS is to keep an array as its storage, and every DeQueue() call, we will use array.shift() to remove and return the first element. Simple and straight-forward as that. However, this proves not to be efficient and 100% correct way especially in large queue, because:

• shift() takes O(n) running time (n is the size of the queue). While our target running time for DeQueue() should be O(1).
• Most operations in Array Prototype in JS has O(n) running time.
• Array is indexed collection, keeping all data allocated in memory consecutively. In case of large queue, every change will require moving large chunk of memory to keep array accessible using indices.

So now comes the question, how do we do it better than using Array? My answer is to use Object instead. After all, everything in JS is considered as Object :)!

Code Implementation

1. Set up basic structure of Queue

function Queue(){
    var storage = {}, //Object represents storage
        head = 0, //index of top
        tail= 0;  //index of bottom of queue
....
}   

2. EnQueue() logic implementation

enQueue: function(item){
     storage[tail] = item;
      tail++; //prepare tail index for next element
    }

3. DeQueue() logic implementation

deQueue: function(){
     var size = tail - head; //Check if Queue is empty
      
      if (size <= 0) return undefined;
      
      var item = storage[head];
      delete storage[head]; //Remove the top from Queue
      
      head++; //Move saved top index to next top.
      
      //Reset the counter if needed
      if (head === tail){
        head = 0;
        tail = 0;
      }
      return item;
}

Note here that I reset the counter once the queue is empty to ensure the head and tail index will not go unnecessarily too large.

Full code implement Demo can be found here

Complexity

As you can see, accessing Object’s property takes O(1) time, hence EnQueue() and DeQueue() each will takes O(1) constant running time. Hence the size of the Queue will not affect performance of its methods.

Summary

So unlike Stack which follows LIFO (Last In — First Out) logic, Queue is an effective dynamic set that follows FIFO logic. It has 2 basic methods:

• EnQueue(item) — add new element item to queue at the tail.
• DeQueue() — remove oldest element from the head of the queue.

Queue is very useful data structure in implementing solution for where order if elements matter (job scheduling, etc…).

I hope my explanation is clear and helpful, especially for anyone who is new to Data Structures and wish to understand it. Not that scary, after all, isn’t it?

Now, how about implementing Queue using Stack? :)

If you like this post and want to read more, feel free to check out my articles.

If you’d like to catch up with me sometimes, follow me on Twitter | Facebook or simply visit my portfolio website.

Maya Shavin (@MayaShavin) | Twitter