Dequeue Algorithm
The Dequeue Algorithm, also known as the double-ended queue algorithm, is a versatile data structure that allows elements to be added or removed from both its front and rear ends. It combines the properties of stacks and queues, making it a powerful and flexible tool in computer programming and data manipulation. Dequeues can be implemented using arrays, linked lists, or other data structures, and they support multiple operations such as insertion, deletion, and traversal.
In a dequeue, both insertion and deletion can occur at either end, providing greater flexibility compared to traditional stacks or queues. This flexibility allows for efficient solutions to various programming problems, such as those involving the manipulation of sequences, string processing, and certain graph algorithms. Depending on the specific implementation, dequeues can be categorized into two types: input-restricted and output-restricted. In an input-restricted dequeue, elements can only be added to one end but removed from both ends, whereas in an output-restricted dequeue, elements can be added to both ends but removed from only one end. The choice of the dequeue type depends on the requirements of the particular problem being solved.
/*
* 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 Dequeue<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 push(item: T) {
val new = Node(item)
new.next = head
head = new
size++
}
public fun peekFirst(): T {
if (size == 0) throw NoSuchElementException()
return head!!.value
}
public fun peekLast(): T {
if (size == 0) throw NoSuchElementException()
return tail!!.value
}
public fun pollFirst(): T {
if (size == 0) throw NoSuchElementException()
val old = head!!
head = old.next
return old.value
}
public fun pollLast(): T {
if (size == 0) throw NoSuchElementException()
var node = head!!
while (node.next != null && node.next != tail) {
node = node.next!!
}
val ret = node.next!!
node.next = null
tail = node
return ret.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
}
}
}
}
