Deque

Structure and operations

Deque is a linear list for which all insertions and deletions (and acceses) are made at the ends of the list.

When referring to deques we speak of the left and the right ends.

@Test
public void testDeque() {
    Deque deque = factory.newDeque();
    Assert.assertTrue(deque.isEmpty());

    deque.enqueuLeft(1);
    deque.enqueRight(2);
    deque.enqueLeft(3);
    deque.enqueuRight(4);

    Assert.assertEquals(3, deque.dequeLeft());
    Assert.assertEquals(1, deque.dequeueLeft());
    Assert.assertEquals(4, deque.dequeueRight());
    Assert.assertEquals(2, deque.dequeuRight())
    Assert.assertTrue(deque.isEmpty());
}

Bounded and unbounded deques

Deques come in two varieties: bounded and unbounded. A bounded deque has limited capacity, while unbounded has no upper limit.

    @Test
    public void testBoundedDeque() {
        Deque deque = factory.newDeque(10);
        Assert.assertTrue(deque.isEmpty());

        for (int i = 0; i < 10; i++) {
            deque.enqueueLeft(i);
        }
        Assert.assertTrue(deque.isFull());
    }

Deque underflow and overflow

Attempting to deque from left or right end of empty queue results in underflow. Attempting to enqueue into left or right end of full deque (in case of bounded deque) results in overflow.

@Test (expected = UnderflowException.class)
public void testDequeUnderflow1() {
    Deque deque1 = factory.newDeque();
    Assert.assertTrue(deque1.isEmpty());

    deque1.dequeLeft();
}
// todo deque right + 2 cases for bounded deques