Data Structure Queue

There are two important data structures used in Web development. Stack and Queue are most commonly used in the industry. My previous blog was about stack. I will dive in the queue and try to explain how to implement a queue structure in Javascript. Some programming languages have their own queue data type but JavaScript does not have its own stack data type. But javascript allowed us to implement queue data type from scratch.

What is queue ?

The queue is very similar data structure like stack. Add data in and remove data out. These are the only two operation what we need in queue and stack. There are differences between stack and queue putting in order. If you still did not learn about stack , I would like to recap quickly. Stack was relying to the logic last in first out (LIFO). That means whatever item was added last has to be removed first. The queue actually opposite than stack. It is relying the logic first item added in must removed first in the list. We can remember the logic as (FIFO) First In First Out to avoid confusion.

You can think about a queue like people on line for supermarket register to make payment. First person in the line has to be first person out. First piece of data in the queue must be the first thing to go out. It’s easy to remember a queue like this to make it clear in our head.

Creating Queues Using Arrays

It is very convenient to implement a queue in an array. As you know Java scripts has some methods to adding and removing items from an array. We can use push() and shift() or unshift and pop. If we use unshift we can add items in the beginning and with the pop() method we can remove the first item added to the array . If you see the below I implemented methods as I described above. You can also do this with push() and shift() combination. But as you know items have indices in array. If you have a thousand items in the array and adding in the beginning it would be a little hard to re-indexed all the items when you added a new item. But adding to the end of the array does not require all the items re-indexed in the array. Because of this logic I created an array with unshift() and pop() methods in the example. But both methods are logic based on queue data structure.

Implementation of Queue Class from Scratch for Singly Linked List

class Node {
    constructor(value){
        this.value = value;
        this.next = null;
    }
}

class Queue {
    constructor(){
        this.first = null;
        this.last =  null;
        this.size = 0;
    }

If you remember from my blog about stack; When we created Linked List we need two pointers which are called head and tail. We also initialized the length of the list. But When we created Stack or Queue instead of head and tail we changed our pointer as first, last and size like the same idea when we created a singly Linked list.

Enqueue and dequeue

We also have two new methods in the queue. Actually they are just different terms for queue. I will explain what those new methods are.

enqueue : You can think about enqueue as push() or unshift() method. It is a method for adding items in the list.

dequeue: You can also think about dequeue like pop() or shift() methods. It removes first thing out on queue data structure.

Enqueue Pseudocode

• This function accepts some value
• Create a new Node using that value passed to the function
• If there are no nodes in the queue, set this node to be the first and last property of the queue
• Otherwise, set the next property on the current last to be that node, and then set the last property of the queue to be that node

Dequeue Pseudocode

• If there is no first property, just return null
• Store the first property in a variable
• See if the first is the same as the last. If so, set the first and last to be null
• If there are more than 1 node, set the first property to be the next property of first
• Decrement the size by 1
• Return the value of the node dequeued

class Node {
    constructor(value){
        this.value = value;
        this.next = null;
    }
}

class Queue {
    constructor(){
        this.first = null;
        this.last =  null;
        this.size = 0;
    }
    enqueue(val){
        var newNode = new Node(val)
        if(!this.first){
            this.first = newNode;
            this.last = newNode;
        } else {
            this.last.next = newNode;
            this.last = newNode;
        }
        return ++this.size;

    }
    dequeue(){
    if(!this.first) return null;
    var temp = this.first;
    if(this.first === this.last){
        this.last = null;

    }
      this.first = this.first.next
      this.size --
      return temp.value;
    }
}

You can grow your list with a queue as much as you want. There is no limit! There is also no index or indices that make a problem for constant time for every operation. It is just adding and removing. Queue is very similar to stack but at the same time they have very different behaviors. They have the same operation adding something in and removing out but they are behaving differently in an order. Stack is relying on logic last item in first thing out (LIFO), queue is relying first thing in first thing out(FIFO).