Queues Flashcards
quintessentially british
What is a queue an example of?
An ordered list
What are the ordering criteria for the elements within a queue?
Time of Arrival (First in - First Out / FIFO)
Priority of the associated event / data
What are the items of interest in a FIFO queue?
First Item ( head / front)
Last Item ( tail / back)
enQueue
adds an element to the queue
Serve
returns the ‘first’ item from the queue and removes it from the queue
only way to remove data from a queue
getHead
returns the first element, leaving the queue unchanged
queueLength
the current number of data items in the data structure
isFull
returns try if the queue buffer is full
isEmpty
returns true if there are no elements in the queue
How can underflow occur in queues?
trying to “serve” an empty queue
How can overflow occur in queues?
trying to “enQueue” data into a full queue
How would we catch the underflow and over flow exceptions?
Use our own exceptions
An array based queue implementation can be simple if
adding an array to the queue involves incrementing the tail
removing an element involves incrementing the head variable
What is Cyclic Buffering?
stores data in a fixed-size buffer that is connected end-to-end
What does the Remainder / Modulus Operator do regarding Cyclic Buffering?
ensures that the indices of the buffer wrap around when they reach the end of the array
Using the % operator, how is a new array index value given each time an index is incremented
head++% or ++tail%
What is this code showing?
import java.lang.RuntimeException;
…
class QueueBoundaryException extends RuntimeExeception {
QueueBoundaryException (String message){
super(message);
} // end consturctor
} // end class
catches exceptions in any application / program encounters them when using the queue
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
remove the data item currently at the head of the queue
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
Array Based Implementation for a Queue
What is the added complexity associated with Priority Queues?
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
What is a limitation of arrays regarding insertion / deletion ?
To delete or, change the elements of an array you need to traverse throughout the array which increases the time complexity
