Simple CircularQueue implementation for JavaScript/TypeScript

CircularQueue.js

class CircularQueue {
  /**
   * @param {number} growthRate Rate of growth  when additional allocation is required. It must be larger than 1.
   */
  constructor(growthRate) {
    this.growthRate = growthRate
    this.data = new Array(4);
    this.head = 0;
    this.tail = 0;
    this.size = 0;
  }

  grow() {
    const length = this.data.length;
    this.data = this.data
      .slice(this.head, length)
      .concat(this.data.slice(0, this.head))
      .concat(new Array(Math.max(1, Math.floor(length * (this.growthRate - 1)))))
    this.head = 0;
    this.tail = length;
  }

  push(el) {
    this.data[this.tail] = el;
    this.tail = (this.tail + 1) % this.data.length;
    if (this.tail === this.head) {
      this.grow();
    }
    this.size += 1;
    return el
  }

  pop() {
    if (this.size <= 0) return undefined;
    const result = this.data[this.head];
    this.head = (this.head + 1) % this.data.length;
    this.size -= 1;
    return result;
  }

  front() {
    if (this.size <= 0) return undefined;
    return this.data[this.head];
  }
  
  [Symbol.iterator]() {
    const data = [...this.data]
    const tail = this.tail
    let currentIndex = this.head

    return {
      next() {
        if (currentIndex === tail) return { done: true }
        const oldIndex = currentIndex
        currentIndex = (currentIndex + 1) % data.length
        return {
          value: data[oldIndex],
          done: false,
        }
      },
      [Symbol.iterator]() {
        return this
      }
    }
  }
  
  isNotEmpty() {
    return this._size > 0
  }
}

Queue.ts

export class Queue<T> implements Iterable<T> {
  private data: T[] = new Array(4)
  private head: number = 0
  private tail: number = 0
  private _size: number = 0

  public readonly growthRate: number

  /**
   * @param growthRate Rate of growth  when additional allocation is required. It must be larger than 1.
   */
  constructor(growthRate: number = 2) {
    this.growthRate = growthRate
  }

  private grow(): void {
    const length = this.data.length
    this.data = this.data
      .slice(this.head, length)
      .concat(this.data.slice(0, this.head))
      .concat(new Array(Math.max(1, Math.floor(length * (this.growthRate - 1)))))
    this.head = 0
    this.tail = length
  }

  public push(el: T): T {
    this.data[this.tail] = el
    this.tail = (this.tail + 1) % this.data.length
    if (this.tail === this.head) {
      this.grow()
    }
    this._size += 1
    return el
  }

  public pop(): T | undefined {
    if (this._size <= 0) return undefined
    const result = this.data[this.head]
    this.head = (this.head + 1) % this.data.length
    this._size -= 1
    return result
  }

  public front(): T | undefined {
    if (this._size <= 0) return undefined
    return this.data[this.head]
  }

  public size(): number {
    return this._size
  }

  public [Symbol.iterator](): IterableIterator<T> {
    const data = [...this.data]
    const tail = this.tail
    let currentIndex = this.head

    return {
      next(): IteratorResult<T> {
        if (currentIndex === tail) return { value: undefined, done: true }
        const oldIndex = currentIndex
        currentIndex = (currentIndex + 1) % data.length
        return {
          value: data[oldIndex],
          done: false,
        }
      },
      [Symbol.iterator](): IterableIterator<T> {
        return this
      },
    }
  }

  public isNotEmpty(): this is NonEmptyQueue<T> {
    return this._size > 0
  }
}

interface NonEmptyQueue<T> extends Queue<T> {
  pop(): T
}

You can implement queue using linked list, but that's a little bit slower because of the allocations for each nodes.
(See https://www.measurethat.net/Benchmarks/Show/16655/1/circular-queue-vs-linked-list-queue-v2)

Changes

2026-01-14

Support followings

• @typescript-eslint/explicit-function-return-type
• TypeScript 5.8's erasableSyntaxOnly

2024-09-09

• Fix wrong size growth #see (Thank you tom288!)

2022-04-19

Now this queue supports iteration protocols.

const q = new CircularQueue<number>()
q.push(1)
q.push(2)
q.push(3)
for (const x of q) {
  console.log(x)
}

// print 1, 2, 3

Note that iterator ignores any changes to the queue after the iterator's creation. This ensure the concurrency safety.

Now this queue provides improved DX using isNotEmpty. This returns type assertion which ensures that return value of the pop is T, not T | undefined.

if (q.isNotEmpty()) {
  const value = q.pop() // you don't have to put ! here
}

This is really nice.

I believe this is wrong:

     .concat(new Array(Math.max(1, Math.floor(length * this.growthRate))));

As it means a growth rate of this.growthRate + 1 is used. This should be used instead:

     .concat(new Array(Math.max(1, Math.floor(length * (this.growthRate - 1)))));

@tom288

As it means a growth rate of this.growthRate + 1 is used. This should be used instead:

Yes you're right. Thank you sir! I'll edit asap.