DEV Community

loading...

Queue: Linkedlist as storage

ivywalobwa profile image Ivy-Walobwa ・2 min read

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
}

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;
    }

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;
        }
    }

peek

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

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

Discussion (0)

pic
Editor guide