Introduction to Queues in Scala

Hello there! Today, we will unveil Queues in coding, likening them to a line in a coffee shop or a queue of print requests. Queues in computer science are First-In, First-Out (FIFO) structures. Consider this example: you're at a theme park — the first person in line for the roller coaster gets on first. Today's lesson revolves around this straightforward yet powerful concept. So, let's dive in!

Let's explore the implementation of Queues in Scala using an Array[Int]. Here's how we define a Queue:

class QueueExample(capacity: Int) {
  private val queue: Array[Int] = new Array[Int](capacity)
  private var front: Int = 0
  private var rear: Int = -1
  private var currentSize: Int = 0

  def isFull: Boolean = {
    currentSize == capacity
  }
}

In the QueueExample class above, the isFull method checks if our queue has reached its maximum capacity.

Enqueue, a fancy term, denotes adding an item to the queue — the item lines up at the rear. Here's how it plays out in our Queue class:

def enqueue(item: Int): Unit = {
  if (!isFull) {
    rear = (rear + 1) % capacity
    queue(rear) = item
    currentSize += 1
  }
}

The enqueue method adds an item to the end of the queue if it is not full.

Just as Enqueue adds an element to our queue, Dequeue removes it. It extracts the element at the queue's front, reducing its size. However, we encounter an underflow condition if there are no elements to remove.

def dequeue(): Option[Int] = {
  if (isEmpty) None
  else {
    val item = queue(front)
    front = (front + 1) % capacity
    currentSize -= 1
    Some(item)
  }
}

def isEmpty: Boolean = {
  currentSize == 0
}

The dequeue method checks for emptiness before dispatching the item, returning None if the queue is empty.

The time complexity of enqueue and dequeue operations remains constant: O(1). However, the space complexity varies with the size of the queue, making it O(n).