-
Notifications
You must be signed in to change notification settings - Fork 0
Queue
Arkady Seletsky edited this page Jul 22, 2017
·
8 revisions
A queue is a linear list for which all insertions are made at one end of the list; all deletions (and accesses) are made from the other end.
With queues we speak of the front and the rear of the queue, also known as head and tail. Items are enqueued to the rear of the queue, and are dequeued from the front position.
Queues feature the so called first-in-first-out "FIFO" behaviour. This is demonstrated by the following snapshot.
@Test
public void testQueue() {
Queue queue = factory.newQueue();
Assert.assertTrue(queue.isEmpty);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
Assert.assertEquals(1, queue.dequeue());
Assert.assertEquals(2, queue.dequeue());
Assert.assertEquals(3, queue.dequeue())
Assert.assertTrue(queue.isEmpty)
}
Queues come in two varieties: bounded and unbounded. Bounded queues have limited capacity (an int), unbounded have no upper limit.
@Test
public void testBoundedQueue() {
Queue queue = factory.newQueue(10);
Assert.assertTrue(queue.isEmpty);
for (int i = 0; i < 10; i++) {
queue.enqueue(i);
}
Assert.assertTrue(queue.isFull());
}
Attempting to dequeue from empty queue results in underflow. Attempting to enqueue to full queue (bounded variety) results in queue overflow.
@Test (expected = UnderflowException.class)
public void testQueueUnderflow1() {
Queue queue1 = factory.newQueue();
Assert.assertTrue(queue1.isEmpty);
queue1.dequeue();
}
@Test (expected = UnderflowException.class)
public void testQueueUnderflow2() {
Queue queue2 = factory.newQueue(10);
Assert.assertTrue(queue2.isEmpty);
queue2.dequeue();
}
@Test (expected = OverflowException.class)
public void testQueueOverflow() {
Queue queue3 = factory.newQueue(10);
Assert.assertTrue(queue3.isEmpty());
for (int i = 0; i < 10; i++) {
queue3.enqueue(i);
}
Assert.assertTrue(queue3.isFull());
queue3.enqueue(10);
}