Queues

Question 1

What is a queue an example of?

Answer 1

An ordered list

Question 2

What are the ordering criteria for the elements within a queue?

Answer 2

Time of Arrival (First in - First Out / FIFO)

Priority of the associated event / data

Question 3

What are the items of interest in a FIFO queue?

Answer 3

First Item ( head / front)

Last Item ( tail / back)

Question 4

enQueue

Answer 4

adds an element to the queue

Question 5

Serve

Answer 5

returns the ‘first’ item from the queue and removes it from the queue

only way to remove data from a queue

Question 6

getHead

Answer 6

returns the first element, leaving the queue unchanged

Question 7

queueLength

Answer 7

the current number of data items in the data structure

Question 8

isFull

Answer 8

returns try if the queue buffer is full

Question 9

isEmpty

Answer 9

returns true if there are no elements in the queue

Question 10

How can underflow occur in queues?

Answer 10

trying to “serve” an empty queue

Question 11

How can overflow occur in queues?

Answer 11

trying to “enQueue” data into a full queue

Question 12

How would we catch the underflow and over flow exceptions?

Answer 12

Use our own exceptions

Question 13

An array based queue implementation can be simple if

Answer 13

adding an array to the queue involves incrementing the tail

removing an element involves incrementing the head variable

Question 14

What is Cyclic Buffering?

Answer 14

stores data in a fixed-size buffer that is connected end-to-end

Question 15

What does the Remainder / Modulus Operator do regarding Cyclic Buffering?

Answer 15

ensures that the indices of the buffer wrap around when they reach the end of the array

Question 16

Using the % operator, how is a new array index value given each time an index is incremented

Answer 16

head++% or ++tail%

Question 17

What is this code showing?
import java.lang.RuntimeException;
…
class QueueBoundaryException extends RuntimeExeception {
QueueBoundaryException (String message){
super(message);
} // end consturctor
} // end class

Answer 17

catches exceptions in any application / program encounters them when using the queue

Question 18

What is this code showing?
public int serve() {
if (isEmpty())
throw new QueueNoundaryException (“ArrayQueue underflow”);
else {
int x = queueArray[head++];
return x;
} //end else
} // end serve

Answer 18

remove the data item currently at the head of the queue

Question 19

What is this code showing?
public class ArrayQueue implements IntQueue{
int buffer[ ];
int head, tail, count;

//constructor
public ArrayQueue (int maxqueuesize) {
	buffer = new int [maxqueuesize];
	head = 0;
	tail = -1;
	count = 0;
} // end constructor

Answer 19

Array Based Implementation for a Queue

Question 20

What is the added complexity associated with Priority Queues?

Answer 20

enQueue must ensure that the queue is maintained in priority order, meaning that the highest priority item should be at the head of the queue

Question 21

What is a limitation of arrays regarding insertion / deletion ?

Answer 21

To delete or, change the elements of an array you need to traverse throughout the array which increases the time complexity