DEV Community

Ivy-Walobwa
Ivy-Walobwa

Posted on

Queue: Linkedlist as storage

Queue

Unlike stack, a queue works on First in First Out(FIFO) principle. Two main operations are done on a queue; enqueue and dequeue.

Queue

To enqueue involves adding item to the back of queue while to dequeue involves removing front item in queue.

Linkedlist as storage

Implementing a queue using linkedlist;
1.The head of list is the head(front) of queue
2.The insertLast method is used to enqueue
3.The removeFirst method is used to dequeue

Implemetation

1.Create node and queue class

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

class Queue {
    constructor() {
        this.head = null;
        this.tail = null;
    }
//add methods
}
Enter fullscreen mode Exit fullscreen mode

Our queue has a head(front) and tail(back) item.

2.Add methods to our queue class to perform enqueue, dequeue and peek

Enqueue

//add item to queue
    enqueue(data) {
        let node = new Node(data);
        //if empty, set new node as head and tail
        if (this.tail == null) {
            this.head = node;
            this.tail = node;
            return;
        }
        //add node as last item in queue
        this.tail.next = node;
        //set node as tail
        this.tail = node;
    }
Enter fullscreen mode Exit fullscreen mode

Dequeue

//remove item from queue
    dequeue() {
        //if empty, do nothing
        if (this.head == null) {
            return;
        }
        //remove curent head and set head to next item in queue
        this.head = this.head.next;

        // set tail to null if queue is emptied
        if (this.head == null) {
            this.tail = null;
        }
    }
Enter fullscreen mode Exit fullscreen mode

peek

 //return first item in queue
    peek() {
        if (this.head == null) {
            return "Queue is empty";
        }
        return this.head.data;
    }
Enter fullscreen mode Exit fullscreen mode

I'll be implementing a queue with arrays next, stay tuned.
Happy Coding! 👯

Top comments (0)