Run results for: Circular Queue vs Linked List Queue v2

Run details:

User agent: Mozilla/5.0 (Linux; Android 11; SM-G991N) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/97.0.4692.70 Mobile Safari/537.36

Browser: Chrome Mobile 97

Operating system: Android

Device Platform: Mobile

Date tested: 2 years ago

Test name	Executions per second
CircularQueue	7.0 Ops/sec
LinkedListQueue	6.6 Ops/sec

Script Preparation code:

var CircularQueue = class CircularQueue {
  constructor(growth) {
    this.growth = growth
    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.ceil(length * this.growth))));
    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;
  }

  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];
  }
}

var LinkedListQueue = class LinkedListQueue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  push(el) {
    const newNode = {
      next: null,
      value: el
    };
    if (this.tail) {
      this.tail.next = newNode;
    } else {
      this.head = newNode;
    }
    this.tail = newNode;
    this.size += 1;
  }

  pop() {
    const result = this.head?.value;
    this.head = this.head?.next;
    if (!this.head) {
      this.tail = null;
    }
    this.size = Math.max(0, this.size - 1);
    return result;
  }

  front() {
    return this.head?.value;
  }

  debug() {
    const arr = [];
    let node = this.head;
    while (node) {
      arr.push(node.value);
      node = node.next;
    }
    console.log(arr.join(", "));
  }
}

const N = 1000000
const operations = new Array(N)
for (let n = 0; n < N; ++n) {
  operations[n] = (n ** 2 + 3 * n) % 2
}

function test(q) {
  for (const op of operations) {
    if (op) {
      q.push(Math.random())
    } else {
      q.pop()
    }
  }
}

Tests:

CircularQueue (rate = 1)
test(new CircularQueue(1))
LinkedListQueue
test(new LinkedListQueue())
CircularQueue (rate = 0.5)
test(new CircularQueue(0.5))
CircularQueue (rate = 0.25)
test(new CircularQueue(0.25))

Run results for: Circular Queue vs Linked List Queue v2

CircularQueue (rate = 1)

LinkedListQueue

CircularQueue (rate = 0.5)

CircularQueue (rate = 0.25)