Deque Algorithm
The Deque Test Algorithm is a diagnostic tool used to evaluate the performance of a particular Deque (Double-ended queue) implementation. Deques are a generalization of stacks and queues that allow elements to be added or removed from both ends, enabling efficient insertion and deletion operations. The algorithm focuses on testing the efficiency, correctness, and robustness of various operations such as adding, accessing, and removing elements from the Deque, ensuring that the implementation adheres to the expected standards and functional specifications.
To perform the Deque Test Algorithm, a series of test cases are designed to cover all possible scenarios and edge cases. Some of these tests may include checking the size of the Deque after inserting or removing elements, verifying if the correct elements are being added or removed from both ends, and ensuring that the Deque implementation can handle large datasets without compromising on performance. Additionally, the algorithm should also validate the implementation's behavior when faced with invalid inputs and boundary conditions, such as attempting to remove an element from an empty Deque or exceeding the maximum capacity. By thoroughly testing the Deque implementation using this algorithm, developers can identify potential issues and inefficiencies, enabling them to optimize the data structure for real-world applications.
package deque
/**
* Implementation of the Deque functionality which provides a double ended queue.
*
* This implementation of Deque is backed by a MutableList
*
* Created by Andy Bowes on 05/05/2016.
*/
class Deque<T>(){
var backingList : MutableList<T> = arrayListOf()
fun addFirst(element:T){
backingList.add(0,element)
}
fun getFirst():T?{
if (backingList.isEmpty()){
return null
}
val value = backingList.first()
removeFirst()
return value
}
fun removeFirst(){
if (backingList.isNotEmpty()) backingList.removeAt(0)
}
fun peekFirst(): T?{
return if (backingList.isNotEmpty()) backingList.first() else null
}
fun addLast(element:T){
backingList.add(element)
}
fun getLast():T?{
if (backingList.isEmpty()){
return null
}
val value = backingList.last()
removeLast()
return value
}
fun removeLast(){
if (backingList.isNotEmpty()) backingList.removeAt(backingList.size - 1)
}
fun peekLast():T?{
return if (backingList.isNotEmpty()) backingList.last() else null
}
}
