Question 49592 in Javascript Question posted in
A very good W3school tutorial can be found here.

My implementation of a queue in js doesn't seem to work correctly – Javascript

My Queue looks like this.

    class Queue{
    constructor(){
        this.head = this.tail = undefined   //empty
        this.length = 0
    }

    enqueue(item){
        const node = {value: item} //create a new node
        this.length++ //increase length since we are adding an element
        if (!this.tail){
            this.tail = this.head = {value: item}
        }

        this.tail.next = node //add the new node to the end of the queue 
        this.tail = node //move the tail to point to the new node last node.
    }

    deque(){  //we always deque from the head in queues
        if (!this.head){
            return undefined //if no head there is nothing to deque so undefined
        }

        this.length-- //decrease length since we are dequeuing

        const head = this.head //save current head in the variable

        this.head = this.head.next //move head to point to the next element

        head.next = undefined //remove the link to the dequeued element
        
        if (this.length === 0){
            this.tail = undefined
        }

        return head.value
    }

    peek(){
        return this.head?.value //just return the value of the head
    }


    }

Then I call following methods:

    let newQ = new Queue()

    newQ.enqueue('rawr')

    newQ.enqueue('meow')

    //queue looks like this rawr => meow because we add from the tail. 

    newQ.deque()

    //now it looks like this: meow (because rawr was first in and now it's first out)

    console.log(newQ.peek())//outputs rawr

Why is the output of my console.log "rawr" instead of "meow"???

I was expecting a meow instead of a rawr. When I implement the queue using stardard shift() and push() methods instead of linked lists, it works as expected. I need to implement this using linked lists because I want to get a better understanding of linked lists.

Tags:

2

Answers


  1. 0

    The main issue is that in enqueue, the if block does not have a return statement. As a consequence execution continues to set this.tail.next to node, so now you have a list with two nodes instead of one, and they both have the same value: "rawr". This explains that after dequeuing one item, the output of peek() is still "rawr".

    Secondly, there should be no need to create {value: item} twice.

    So change this:

            if (!this.tail){
            this.tail = this.head = {value: item};
        }

    to this:

            if (!this.tail){
            this.tail = this.head = node; // use `node`
            return; // All done!
        }

    Not a problem, but:

    • You don’t need to do head.next = undefined; because head is local variable and will not be accessed after deque has run to completion. In fact, you could actually save the value in a local variable instead of the node reference.
    • End statements with a semi-colon. Although the engine provides automatic semicolon insertion, it is better to not leave it to that algorithm, but take control over this yourself.
    • The word deque has a different meaning and pronunciation than dequeue. You want the second one.

    Corrected Snippet:

    class Queue{
    constructor(){
        this.head = this.tail = undefined;
        this.length = 0;
    }
    
    enqueue(item){
        const node = {value: item};
        this.length++;
        if (!this.tail){
            this.tail = this.head = node;
            return;
        }
        this.tail.next = node;
        this.tail = node;
    }

    dequeue() {
        if (!this.head) {
            return undefined; 
        }
        this.length--;
        const value = this.head.value;
        this.head = this.head.next;
        if (this.length === 0) {
            this.tail = undefined;
        }
        return value;
    }

    peek() {
        return this.head?.value;
    }
}

const newQ = new Queue();
newQ.enqueue('rawr');
newQ.enqueue('meow');
newQ.dequeue();
console.log(newQ.peek());
    Login or Signup to reply.
  2. 0

    When you make your initial tail, you are setting its .next to itself also. Your code this.tail.next = node should be in an else block of the above if block, and when you set this.tail = this.head = {value: item}, try setting that equal to node instead so you can set this.head indirectly the second time you call this method.

    enqueue(item){
    const node = {value: item} //create a new node
    this.length++ //increase length since we are adding an element
    if (!this.tail){
        this.tail = this.head = node
    } else {
        this.tail.next = node //add the new node to the end of the queue
    }
    this.tail = node //move the tail to point to the new node last node.
}
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search