| Define a queue | An abstract data type that holds an ordered, linear sequence of items whereby iems are added from the back and removed from the front |
| What are the two main operators of a queue | Enqueue (Add): an item is added at the rear
Dequeue (Remove): an item is removed from the front |
| Where is data added to a queue? | rear |
| Where is data removed from a queue? | front |
| How many pointers are needed for a queue and where do they point? | 2
front and rear |
| Whats unique about how a linear queue works? | Linear Queue: Elements join the queue at one end and leave the queue at the other end |
| Whats unique about how a circular queue works? | // When the array element with the largest possible index has been used, the next element to join the queue reuses the vacated location at the beginning of the array //
Last element is connected to the first element
When the last elemental position has been used the queue circles back and uses the first position |
| Whats unique about how a priority queue works? | Each element of a priority queue has an associated priority. |
| Whats unique about how a shuffle queue works? | The front of the queue array is fixed as the first slot. Each time an element is removed, other elements move one position forward to fill the vacated slot. |
| Program how an item is removed from a circular queue | if (!Empty())
{
string r = QueueArray[front];
QueueArray[front] = "";
front = (front + 1) % capacity;
count--;
return r;
}
else
{
throw new InvalidOperationException("Invalid operation. The queue is empty.");
}
Removing at item removes the first item. You don’t search for it |
| Program how an item is added from a circular queue | s = readline()
if (!Full())
{
rear = (rear + 1) % capacity;
QueueArray[rear] = s;
count++;
} |
| Program how a queue is tested if its empty | if (Empty())
{
return count == 0;
}
hmmm?
for each item on q
if item = null
nullCounter++;
if nullCounter = count
the queue is emtpy |
| Program how a queue is tested for a fullness | for each item on q
if item != null
fullCounter++;
if fullCounter = count
the queue is full |
