Queue

/**
 * Interview Question:
 * Implement a Queue data structure.
 *
 * Requirements:
 * - Follow FIFO order: first item enqueued is the first item dequeued
 * - Support enqueue, dequeue, front, back, isEmpty, and length operations
 * - Return undefined when dequeue/front/back is called on an empty queue
 * - Keep enqueue and dequeue operations O(1)
 *
 * Approach:
 * Use a singly linked list with two pointers:
 * - head points to the front of the queue, where items are removed
 * - tail points to the back of the queue, where items are added
 *
 * Important edge cases:
 * - Enqueue into an empty queue: both head and tail should point to the new node
 * - Dequeue the last remaining item: clear both head and tail
 */

// Internal linked-list node used by Queue.
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

export default class Queue {
  constructor() {
    this.head = null; // front of queue
    this.tail = null; // back of queue
    this.size = 0;
  }

  /**
   * Adds an item to the back of the queue.
   * @param {*} item The item to be pushed onto the queue.
   * @return {number} The new length of the queue.
   */
  enqueue(item) {
    const newNode = new Node(item);

    // Empty queue: the new node is both the front and back.
    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      // Non-empty queue: append after tail, then move tail forward.
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this.size++;
    return this.size;
  }

  /**
   * Removes an item from the front of the queue.
   * @return {*} The item at the front of the queue if it is not empty, `undefined` otherwise.
   */
  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }

    const removedValue = this.head.value;

    // Move the front pointer forward; old head becomes unreachable.
    this.head = this.head.next;
    this.size--;

    // If queue becomes empty, also clear tail.
    if (this.isEmpty()) {
      this.tail = null;
    }

    return removedValue;
  }

  /**
   * Determines if the queue is empty.
   * @return {boolean} `true` if the queue has no items, `false` otherwise.
   */
  isEmpty() {
    return this.size === 0;
  }

  /**
   * Returns the item at the front of the queue without removing it from the queue.
   * @return {*} The item at the front of the queue if it is not empty, `undefined` otherwise.
   */
  front() {
    return this.head ? this.head.value : undefined;
  }

  /**
   * Returns the item at the back of the queue without removing it from the queue.
   * @return {*} The item at the back of the queue if it is not empty, `undefined` otherwise.
   */
  back() {
    return this.tail ? this.tail.value : undefined;
  }

  /**
   * Returns the number of items in the queue.
   * @return {number} The number of items in the queue.
   */
  length() {
    return this.size;
  }
}