5.4. Types of Queues

A Queue is a linear data structure that follows the FIFO (First In, First Out) principle. The first element added is the first to be removed.

A Queue is a way of organizing data that allows elements to be added and removed in a specific order. The FIFO principle means that the first item added to the queue will also be the first one to be removed. This is similar to a line of people where the person who has been waiting the longest (the first person in line) gets served first.

Imagine a queue at a coffee shop. The first customer to arrive at the counter is the first one served, just as the first element in a queue is the first to be removed from the data structure.

Real-life Example: People standing in a queue at a ticket counter.

When standing in line to buy a ticket, the order in which you arrived at the line determines when you get to purchase your ticket. This real-world scenario exemplifies how a queue operates, ensuring fairness by allowing those who arrived first to receive service first.

Think of a queue as a group of people lined up at a bus stop. The first person in line boards the bus first, followed by the next. This orderly process ensures that everyone is treated fairly, and it mimics the working of a queue in computer science.

Operations: • enqueue(): Add an element to the rear. • dequeue(): Remove an element from the front. • front(): View the front element. • isEmpty(): Check if the queue is empty.

A queue has several key operations. First, 'enqueue' is how you add an item to the queue. This is done at the rear. Second, 'dequeue' removes the item from the front of the queue, reflecting the FIFO principle. The 'front' operation allows you to see what item will be dequeued next without removing it. Finally, 'isEmpty' checks whether any items are currently in the queue.

Using our coffee shop example, 'enqueue' is what happens when a new customer joins the line, 'dequeue' is when the cashier serves the first customer and lets them go, 'front' is looking at who is next to be served without pushing them out of line, and 'isEmpty' checks if the line has any customers left.

Types of Queues: • Simple Queue: Basic FIFO structure. • Circular Queue: Rear connects back to the front to reuse space. • Priority Queue: Elements are removed based on priority, not just order.

There are several variations of queues that serve different purposes. A Simple Queue is the most basic version where elements are added to the back and taken from the front. A Circular Queue is more advanced; when the end of the queue is reached, the next operation can continue from the front, maximizing space usage. Finally, a Priority Queue allows elements to be removed based not on their order in the queue, but on a predefined priority, meaning some elements can be processed faster than others regardless of when they entered the queue.

Using our earlier example, a Simple Queue is like the standard line at a ticket booth. A Circular Queue is like a line at an amusement park where after riding a ride, guests can loop back to the front and get in line for another turn. Lastly, a Priority Queue can be compared to a fast-track lane at the airport where some passengers are allowed to board the plane ahead of others regardless of their arrival time.

Example (Queue Operations in Pseudocode): enqueue(10) enqueue(20) dequeue() // removes 10 front() // returns 20

Here's a quick look at how some queue operations would look in a simple pseudocode format. When we 'enqueue(10)' and 'enqueue(20)', we add 10 and 20 to the queue respectively. Using 'dequeue()', the queue removes the first element, which is 10 in this case. Then, with 'front()', you can check what the next element to be removed is, which would be 20. This illustrates how data is added and removed in a queue.

Think of it as checking off people as they get served. You first write down the person who arrives (enqueued), when they are served you cross them off (dequeued), and finally, you can check who is next in line (front) to be served.

--