Randomized Queue Implemetation Idea

Wafer Li ... 2016-10-14 Coursera
  • Coursera
  • Algorithm
小于 1 分钟

# How to check full & empty?

# How to resize?

  1. Create a new array
  2. Iterate the item in the origin array
  3. Assign the new array to the old one

# How to iterate?

  1. Initialization: begin at head
  2. Next: iterator = (iterator + 1) % array.length
  3. HasNext: iterator != last + 1

# How to add?

  1. Check if is full, if so, double its size
  2. last = (last + 1) % array.length
  3. Place the item into the new last index position

# How to remove?

  1. Generate a random integer within the range [0, Size)
  2. Turn it to the index randomInt + head
  3. Swap the item of that index with the head
  4. Dequeue