randomized-queue.js

class RandomizedQueue {
    constructor(array = []) {
        this.array = array
        this.size = 0
    }

    isEmpty() {
        return this.size < 1
    }

    enqueue(value) {
        if (!value) {
            return null
        }
        this.size++
        this.array.push(value)
    }

    randomId() {
        return Math.random() * (this.size - 1) | 0
    }

    sample() {
        if (this.isEmpty()) {
            return null
        }
        return this.array[this.randomId()]
    }

    dequeue() {
        if (this.isEmpty()) {
            return null
        }
        if (this.size < 2) {
            return this.array.pop()
        }
        const id = this.randomId()
        const item = this.array[id]
        this.array[id] = this.array.pop()
        this.size--
        return item
    }

    *[Symbol.iterator]() {
        const copy = new RandomizedQueue([...this.array])
        while (!copy.isEmpty()) {
            yield copy.dequeue()
        }
    }
}

const rq = new RandomizedQueue()
rq.enqueue(1)
rq.enqueue(2)
rq.enqueue(3)
rq.enqueue(4)
rq.enqueue(5)
rq.enqueue(6)

console.log('removed items')
console.log(
    rq.dequeue(),
    rq.dequeue(),
    rq.dequeue()
)

console.log('iterator #1')
for (let item of rq) console.log(item)

console.log('iterator #2')
for (let item of rq) console.log(item)

console.log('iterator #3')
for (let item of rq) console.log(item)