5. Connecting the dots — Big O and Queue Data Structure

In previous articles, I wrote about various linear data structures such as

1. Arrays
2. Linked Lists and
3. Stacks

Now lets us look into another linear data structure called “Queue data structure”. Queues are very similar to like Stacks which is similar to Linked list. In queues, objects enter from one and are removed from the other and this is called first-in-first-out (FIFO) principle.

An example for Queue data structure is people standing in line to use the ATM machine

When an object gets added in the queue at the end or last it is called enqueue and when it gets removed from the front or first it is called dequeue.

Linked List and Queue Data Structure

Let us create a node and a constructor like we did with linked list. In this case it will be identical to linked list except, the constructor will have first and last when creating a newNode instead of head and tail.

Creating a Queue with a single node

Enqueue / Insert an item at the end of the queue

Enqueuing an item

When we add an item to the end is also same as push() in Linked List which is Big O (1) or constant time.

Adding 10 at the end of the Queue and the output of the same using enqueue( )

Dequeue / remove an item from the front of the queue

This is very similar to the shift() that we used in linked list. In dequeue operation, we see

1. If the queue is empty we return it as undefined.
2. If there is only one node, we remove it and then set first and last item to be null.
3. We use temp variable to keep track of the item to be removed.

Dequeuing of an item from the beginning

When we enqueue from one end and dequeue from the other end from a linked list then both the operations take time complexity of Big O (1). On the other hand, if you use an array and use shift() to dequeue then it will be Big O(n).

Please find the entire code snippet below

With that we covered all the linear data structures in JavaScript.

If you like this article, please follow me and give a 👏 . Thanks for reading this article.

Resources:

MDN , Grokking Algorithms, Big O cheatsheet , algorithm , wikipedia.