Queues
A queue is a fundamental abstract data structure that operates on a FIFO principle.
Definition
FIFO
First-In, First-Out principle.
This means that the first element added to the queue is the first one to be removed.
AnalogyA 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.
ExampleQueues 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.
