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.
/*
* Copyright (c) 2017 Kotlin Algorithm Club
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in all
* copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
* SOFTWARE.
*/
package com.algorithmexamples.datastructures
import java.util.*
@Suppress("RedundantVisibilityModifier")
public class Queue<T> : Collection<T> {
private var head: Node<T>? = null
private var tail: Node<T>? = null
public override var size: Int = 0
private set
private class Node<T>(var value: T) {
var next: Node<T>? = null
}
public fun add(item: T) {
val new = Node(item)
val tail = this.tail
if (tail == null) {
head = new
this.tail = new
} else {
tail.next = new
this.tail = new
}
size++
}
public fun peek(): T {
if (size == 0) throw NoSuchElementException()
return head!!.value
}
public fun poll(): T {
if (size == 0) throw NoSuchElementException()
val old = head!!
head = old.next
size--
return old.value
}
public override fun isEmpty(): Boolean {
return size == 0
}
public override fun contains(element: T): Boolean {
for (obj in this) {
if (obj == element) return true
}
return false
}
public override fun containsAll(elements: Collection<T>): Boolean {
for (element in elements) {
if (!contains(element)) return false
}
return true
}
public override fun iterator(): Iterator<T> {
return object : Iterator<T> {
var node = head
override fun hasNext(): Boolean {
return node != null
}
override fun next(): T {
if (!hasNext()) throw NoSuchElementException()
val current = node!!
node = current.next
return current.value
}
}
}
}
