Queue Algorithm
The Queue Using Array Algorithm is an implementation of the queue data structure using an array as its underlying storage. A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle, where elements are inserted at the rear end and removed from the front end. In this algorithm, two pointers, front and rear, are used to keep track of the first and last elements in the queue, respectively. When an element is enqueued, it is added at the rear end of the array, and the rear pointer is incremented. When an element is dequeued, it is removed from the front end, and the front pointer is incremented. The algorithm also includes a check for overflow and underflow conditions to ensure that the queue operates within the bounds of the array.
One of the main advantages of implementing a queue using an array is its simplicity and ease of understanding. The algorithm provides clear rules for enqueueing and dequeueing elements and is easy to implement in most programming languages. However, there are some drawbacks to this approach. The primary disadvantage is the issue of array resizing, as a fixed-sized array may lead to overflow if the queue grows beyond its capacity. To overcome this limitation, a circular queue can be employed, where the front and rear pointers wrap around the array, effectively reusing the freed spaces from dequeued elements. Another issue is inefficient memory utilization, as dequeued elements leave empty spaces in the array that are not utilized. Despite these drawbacks, the Queue Using Array Algorithm serves as a useful and straightforward introduction to the concept of queues and their implementation.
/**
* This file is part of Scalacaster project, https://github.com/vkostyukov/scalacaster
* and written by Vladimir Kostyukov, http://vkostyukov.ru
*
* Queue http://en.wikipedia.org/wiki/Queue_(abstract_data_type)
*
* -Notes-
*
* This queue also known as Banker's Queue. There is also Physics Queue. Interested in the topic -
* read the Okasaki`s book.
*
* Enqueue - O(1)
* Dequeue - O(1)
* Front - O(1)
* Rear - O(1)
*/
class Queue[+A](in: List[A] = Nil, out: List[A] = Nil) {
/**
* Check whether this queue is empty or not.
*/
def isEmpty: Boolean = in.isEmpty && out.isEmpty
/**
* Dequeues the first element from this queue.
*
* Time - O(1)
* Space - O(1)
*/
def dequeue: (A, Queue[A]) = out match {
case hd :: tl => (hd, new Queue(in, tl))
case Nil => in.reverse match {
case hd :: tl => (hd, new Queue(Nil, tl))
case Nil => throw new NoSuchElementException("Empty queue.")
}
}
/**
* Enqueues given element 'x' into the end of this queue.
*
* Time - O(1)
* Space - O(1)
*/
def enqueue[B >: A](x: B): Queue[B] = new Queue(x :: in, out)
/**
* Returns the first element of this queue.
*
* Time - O(1)
* Space - O(1)
*/
def front: A = dequeue match { case (a, _) => a }
/**
* Returns the rear of this queue.
*
* Time - O(1)
* Space - O(1)
*/
def rear: Queue[A] = dequeue match { case (_, q) => q }
override def toString = (out ::: in.reverse).mkString("Queue(",",",")")
}
object Queue {
/**
* Creates a new empty queue.
*
* Time - O(1)
* Space - O(1)
*/
def empty[A]: Queue[A] = new Queue()
/**
* Creates a new queue fromm given 'xs' sequence.
*
* Time - O(n)
* Space - O(1)
*/
def apply[A](xs: A*) =
xs.foldLeft(Queue.empty[A]) { case (acc, x) => acc.enqueue(x) }
}
