Queues
A queue is a fundamental abstract data structure that operates on a FIFO principle.
FIFO
First-In, First-Out principle.
This means that the first element added to the queue is the first one to be removed.
A queue is like a line at a coffee shop: customers join at the back and wait until they are next to the counter to make an order.
Key Characteristics of a Queue
- FIFO order: Elements are added at the rear and removed from the front.
- Linear structure: Elements are arranged in a linear order, with restricted access to the front and rear.
- Dynamic size: Queues can grow or shrink depending on the implementation (linked list) or have a fixed size (array).
A queue stores a set of elements in a particular order and allows access only to the first item inserted.
Queues are useful for:
- Print Queues: Documents are printed in the order they are sent to the printer.
- Task Scheduling: Operating systems use queues to manage processes and tasks.
- Data Streaming: Buffers use queues to handle data packets in network communication.
- Simulations: Model real-world scenarios like supermarket checkouts or customer service lines.
Types of Queues in Arrays
When we speak about the array implementation of a queue, there are two types of queues:
- Linear Queue
- Elements are added at the rear and removed from the front.
- It can lead to wasted space as the front moves forward.
- Circular Queue
- The rear wraps around to the front when the end of the array is reached.
- Efficiently utilises space by reusing empty slots.
- Do not assume that a linear queue will automatically reuse empty space in the array.
- Without a circular implementation, the queue can become "full" even if there are empty slots at the front.
Core Operations of a Queue
- enqueue(): Adds an element to the rear of the queue.
- dequeue(): Removes and returns the element at the front of the queue.
- isEmpty(): Checks if the queue is empty, returns true or false.
- Do not assume that dequeue removes elements from the end of the queue.
- Remember, it always removes from the front.
- A queue stores elements in order and only allows access to the first item inserted.
- Elements can be numbers, Booleans, characters, objects, or arrays.
In case of circular queue implementation in an array, enqueue and dequeue work a bit differently:
- Enqueue: Increment rear index; wrap around if end is reached.
- Dequeue: Increment front index; wrap around if end is reached.
Constructing Algorithms Using Queue Access Methods
Similarly to stack, usually, there are 3 general steps you need to take care of:
- Initialise the Queue: Start by creating an empty queue.
- Process Elements: Use enqueue to add elements and dequeue to process them.
- Check Conditions: Use isEmpty to determine when to stop processing.
- When designing algorithms with queues, focus on the order of operations.
- Ensure that elements are processed in the correct sequence to maintain the FIFO structure.
Simulating a Print Queue
Imagine a scenario where documents are sent to a printer.
The printer processes documents in the order they arrive.
- Initialise the Queue: Create an empty queue to hold documents.
- Add Documents: Use enqueue to add documents as they arrive.
- Process Documents: Use dequeue to send documents to the printer.
- Check for Completion: Use isEmpty to determine when all documents have been printed.
// Given empty queue in Q
// Limit document number to 5
loop I from 1 to 5
NEW_DOCUMENT = getDocument() // arbitary function that gets new document
Q.enqueue(NEW_DOCUMENT)
end loop
loop while NOT Q.isEmpty()
DOC = Q.dequeue() // get document
Printer.print(DOC) // // arbitary function that gets prints document
end loopThis algorithm ensures that documents are printed in the order they are received, demonstrating the FIFO nature of queues.
- How do queues differ from stacks in terms of their access patterns and applications?
- What are the advantages and disadvantages of using a linked list to implement a queue compared to an array?
- How might you modify an enqueue algorithm to prioritise certain elements?
