Queue

• Quick summary: a sequential collection where elements are added at one end and removed from the other end.
• Important facts:
  • Modeled after a real-life queue: first come, first served.
  • First in, first out (FIFO) data structure.
  • Similar to a linked list, the first (last added) node is called the tail, and the last (next to be removed) node is called the head.
  • Two fundamental operations are enqueuing and dequeuing:
    • To enqueue, insert at the tail of the linked list.
    • To dequeue, remove at the head of the linked list.
  • Usually implemented on top of linked lists because they're optimized for insertion and deletion, which are used to enqueue and dequeue elements.
• Pros:
  • Constant-time insertion and deletion.
• Cons:
  • Access and search are O(n).
• Notable uses:
  • CPU and disk scheduling, interrupt handling and buffering.
• Time complexity (worst case):
  • Access: O(n)
  • Search: O(n)
  • Insertion (enqueuing): O(1)
  • Deletion (dequeuing): O(1)
• See also:
  • Understanding the Queue Data Structure
  • Interview Problems: Queues

xxxxxxxxxx

console.log(queue);

class Queue {

  constructor() {

    this.queue = [];

  }

​

  enqueue(item) {

    return this.queue.unshift(item);

  }

​

  dequeue() {

    return this.queue.pop();

  }

​

  peek() {

    return this.queue[this.length - 1];

  }

​

  get length() {

    return this.queue.length;

  }

​

  isEmpty() {

    return this.queue.length === 0;

  }

}

​

const queue = new Queue();

queue.enqueue(1);

queue.enqueue(2);