Data Structure - Queue

Queue is a datastructure commonly used in procressing work in defined order. Queues are First-in-First-out (FIFO), meaning that elements first stored in the queue are also the first elements to be removed from the queue. This is different to a First-in-Last-out datastrcture (Stack).

Queues can be implemented with both an internal array or a list. When using an internal array, the elements in the array needs to be rearranged when an element in the queue is removed. A Linked list implementation of a queue updates the reference of the element in the queue.

Queue Array Implementation

Image shows an example of an array implementation of a queue:

// Array implementation of a queue
const Queue = (maxSize = 6) => {
    let tail = 0;   // reference to the "tail" of queue
    let head = 0;   // reference to the "head" of queue
    const store = [];
    size = () => store.length;
    peek = () => store[head];
    max = () => maxSize;    
    enqueue = (value) => {
        if (store.length <= maxSize) {
            store[tail++] = value;
            return true;
        }
        return false;
    }
    dequeue = () => {
        if (head > -1) {
            let headValue = store[head];
            store.splice(0, 1);
            tail--;
            return headValue;
        }
    }
    print = () => console.log(store);
    return { max, size, enqueue, dequeue, peek, print }
}

(() => {
    const queue = Queue(2);
    queue.enqueue(1); // true
    queue.enqueue(2); // true
    queue.enqueue(3); // true
    queue.enqueue(4); // false
    queue.print();  // [1, 2, 3]

    queue.dequeue();   // 1
    queue.dequeue();   // 2
    queue.peek();      // 3
    queue.enqueue(5);  // true
    queue.print();  // [3,5]
})();

Queue Linked List Implementation

Queues can be represented by a linked list implementation. The implementation maintains two pointers:

1. head - Item that dequeues first
2. tail - Item that updates reference to the newly added item.

These pointers in the linked list implementation keeps reference of the item to dequeue and the item to enqueue onto, there is no need to maintain/ reorganize existing elements in the queue. The operation of updating the references has a time and space complexity of O(1) when we ignore the need to traverse through the queue.

// Linked list implementation of a queue
const newNode = (data, next = undefined) => {
    return {
        data, next
    }
}
const Queue = () => {
    let head;
    let tail;
    let size = 0;
    peek = () => head;
    enqueue = (data) => {
        if (!head) {
            head = newNode(data);
            tail = head;
        }
        else {
            let node = head;
            while (node && node.next) {
                node = node.next;
            }
            node.next = newNode(data);
            tail = node.next;
        }
    }
    dequeue = () => {
        if (head == null) {
            return null; // queue empty
        }
        let temp = head;
        head = temp.next; // move head reference to point to next in line.
        if (!head) {
            tail = null; // if head is null, tail is also null
        }
        return temp;
    }
    print = () => console.log(JSON.stringify(head));
    return { size, enqueue, dequeue, peek, print }
}

(() => {
    const queue = Queue();
    queue.enqueue(1); // true
    queue.enqueue(2); // true
    queue.enqueue(3); // true
    queue.print();  // [1, 2, 3]

    queue.dequeue();   // 1
    queue.dequeue();   // 2
    console.log(queue.peek());  // 3
    queue.enqueue(4);  // true
    queue.print();  // [3,5]
})();