Dequeue Test Algorithm
The Dequeue Test Algorithm is an effective method used to test the performance and functionality of a deque (double-ended queue) data structure. A deque is a versatile data structure that allows users to add or remove items from both ends (front and rear) with ease. It is a generalized version of a queue or a stack and can be implemented using arrays or linked lists. The Dequeue Test Algorithm aims to ensure that the deque operates correctly and efficiently, by thoroughly examining the various operations such as insertion, deletion, and retrieval of elements.
To perform the Dequeue Test Algorithm, a series of actions are executed on the deque data structure. The algorithm starts by initializing an empty deque and then proceeds to perform a series of operations such as adding elements to the front or rear, removing elements from the front or rear, and checking the deque's size and whether it is empty or not. The algorithm verifies the correctness of these operations by comparing the expected outcomes against the actual outcomes. Furthermore, the efficiency of the deque's implementation is assessed by measuring the time taken to execute each operation. By systematically testing the deque's functionality and performance, the Dequeue Test Algorithm ensures that the data structure is robust and reliable for various applications, ranging from real-time systems to software development tools.
/*
* 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 org.junit.Assert
import org.junit.Test
import java.util.*
class DequeueTest {
@Test
fun emptyTest() {
val dequeue = Dequeue<Int>()
Assert.assertEquals(0, dequeue.size)
Assert.assertTrue(dequeue.isEmpty())
}
@Test(expected= NoSuchElementException::class)
fun exceptionTest() {
val dequeue = Dequeue<Int>()
dequeue.peekFirst()
}
@Test
fun naiveTest() {
val dequeue = Dequeue<Int>()
for (i in 0..10) {
dequeue.add(i)
}
for (i in 0..5) {
Assert.assertEquals(i, dequeue.peekFirst())
Assert.assertEquals(i, dequeue.pollFirst())
}
for (i in 10..6) {
Assert.assertEquals(i, dequeue.peekLast())
Assert.assertEquals(i, dequeue.pollLast())
}
}
@Test
fun naiveIteratorTest() {
val dequeue = Dequeue<Int>()
for (i in 0..10) {
dequeue.add(i)
}
var k = 0
for (i in dequeue) {
Assert.assertEquals(i, k++)
}
}
@Test
fun naiveContainsTest() {
val dequeue = Dequeue<Int>()
for (i in 0..10) {
dequeue.add(i)
}
for (i in 0..10) {
Assert.assertTrue(dequeue.contains(i))
}
Assert.assertFalse(dequeue.contains(100))
Assert.assertFalse(dequeue.contains(101))
Assert.assertFalse(dequeue.contains(103))
}
}
