Queue Implementation in Scala

1. Introduction

A Queue is an abstract data type that stores elements in a First-In-First-Out (FIFO) manner. This means that the first element added to the queue will be the first one to be removed. Common operations on a queue include enqueue, which adds an element to the back of the queue, and dequeue, which removes the front element.

2. Implementation Steps

1. Use Scala's built-in mutable.Queue for the base structure.

2. Implement the enqueue method to add an element to the end of the queue.

3. Implement the dequeue method to remove and return the front element of the queue.

4. Implement a front method to get the front element without removing it.

5. Write the client code to test the Queue implementation.

3. Implementation in Scala

import scala.collection.mutable
class Queue[A] {
  private val queue = new mutable.Queue[A]
  // Add an element to the end of the queue
  def enqueue(element: A): Unit = {
    queue.enqueue(element)
  }
  // Remove and return the front element of the queue
  def dequeue(): Option[A] = {
    if(queue.isEmpty) None else Some(queue.dequeue())
  }
  // Get the front element without removing it
  def front(): Option[A] = {
    if(queue.isEmpty) None else Some(queue.front)
  }
}

Client Code:

val q = new Queue[Int]
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
println(q.front())    // Expected: Some(10)
println(q.dequeue())  // Expected: Some(10)
println(q.front())    // Expected: Some(20)

Output:

Some(10)
Some(10)
Some(20)

Explanation:

1. import scala.collection.mutable: We're importing Scala's mutable collections which includes the built-in Queue.

2. class Queue[A]: This defines a generic Queue class.

3. queue = new mutable.Queue[A]: Initializes the underlying queue structure.

4. enqueue(element: A): This method is responsible for adding an element to the end of the queue.

5. dequeue(): This method removes and returns the front element of the queue. If the queue is empty, it returns None.

6. front(): This is a method to fetch the front element without removing it. Returns None if the queue is empty.

The implemented Queue is a basic representation and utilizes Scala's built-in Queue to manage the underlying operations efficiently.