4.2.2 Queues Flashcards
(14 cards)
Define Queues.
A first in first out (FIFO) data structure.
The first item added/pushed on to the queue is the first to be removed/popped off.
How is the order kept in the queue?
There is a pointer at the front of the queue that indicates the element at the front of the queue.
And there is a pointer at the rear of the queue that indicates the back of the queue.
What are the main operations of the queue?
- enqueue
- dequeue
- is_empty()
- is_full()
What does the operation ‘enqueue’ perform?
It adds items to the back of the queue. Entering the queue.
What does the operation ‘dequeue’ perform?
It removes items from the front o the queue. Departing the queue.
What does the operation ‘is_empty()’ perform?
Checks whether the queue is empty.
What does the operation ‘is_full()’ perform?
Checks whether the queue is at maximum capacity.
What are the 3 types of queues?
- linear queues
- circular queues
- priority queues
How is a linear queue represented?
A linear queue can be visualized as a line of data in a straight line.
How is data added to a linear queue?
Since it is a straight line, there is no attempt to re-use the space at the start of the array (that has been freed up as items are dequeued as they are performed).
Thus the queue will be ‘full’ when the last position in the array is used, no matter how many items are on the queue.
So will have to keep adding spaces if more items are needed to be added - dynamic data structure.
How is a circular queue represented?
It can be visualized as a ring of data. And it is a static data structure.
in terms of programming:
rear = (rear +1) % size of queue
How is data added to a circular queue?
First the queue is checked if it is already full with is_full().
Then compare the value of the rear pointer with the maximum size of the array.
If equal then rear pointer becomes zero.
Otherwise add 1 to the rear pointer.
And insert the new item in position indicated by the rear pointer.
Why is circular queue static?
As items are dequeued, space is freed up at the start of the array.
Circular queue reuses the empty slots removed from the start of the queue and the start pointer moves along, and enqueues so the end pointer also changes to where was the start of the array.
How is a priority queue represented?
It is similar to a linear queue except items have priority.
Items with higher priority are moved to the front of the queue and lower priority to the back of the queue.
e.g in school, teachers have higher priority than students.
