Group Group Group Group Group Group Group Group Group

Chapter 13 (Iterator) - Queue Implementation

Books Design Patterns by Tutorials
#1

In the implementation for the dequeue method, there is a check made for the total elements in the array and the percentage? What is this used for?

public mutating func dequeue() -> T? {
    guard head < array.count,
          let element = array[head] else {
      return nil
    }

    array[head] = nil
    head += 1

    let percentage = Double(head)/Double(array.count) // What is this doing?
    if array.count > 50, // What's different between having 40 or 60 elements?
       percentage > 0.25 { // Is this necessary? We already have an element
      array.removeFirst()
      head = 0
    }

    return element
  }
#2

Everything is explained in the GitHub repository swift-algorithm-club/Queue

If we never remove those empty spots at the front then the array will keep growing as we enqueue and dequeue elements. To periodically trim down the array, we do the following:

    if array.count > 50 && percentage > 0.25 {
      array.removeFirst(head)
      head = 0
    }

This calculates the percentage of empty spots at the beginning as a ratio of the total array size. If more than 25% of the array is unused, we chop off that wasted space. However, if the array is small we do not resize it all the time, so there must be at least 50 elements in the array before we try to trim it.

1 Like
#3

Thank you so much @mokhet, that makes more sense now, seems to be related to memory optimizations but unrelated to the task at hand.