Understanding the Problem: Why We Need FIFO

Understanding the Problem: Why We Need FIFO

Before we learn a new data structure, it helps to first understand the kind of problem it solves. So let us look at some real situations that programmers face, and see why we need a special tool to handle them.

Why order matters

Many programs need to store some data and then come back to use it later. But often it is not enough to just *keep* the data — we also need to remember the order in which it was added. The order in which we put things in decides the order in which we should take them out.

You may already know about a stack. A stack works in Last In, First Out (LIFO) order. That means the last item you put in is the first item you take out — like a pile of plates, where you take the top plate first.

But many real problems need the *opposite* behavior. They need the item that came in first to be handled first. This is called:

• FIFO — First In, First Out
• It is also known as LILO — Last In, Last Out (same idea, said the other way)

> FIFO in one line: the first data item you add is the first one to be processed. Think of people standing in a line at a shop — whoever arrives first gets served first, and newcomers join at the back.

Let us look at three everyday systems that all depend on this FIFO order.

Example 1: Music players

Almost every modern music player lets you add many songs to a list, and then plays them one after another. The rule is simple: the song you added first should play first.

Imagine you add songs in this order:

1. cool song 1
2. cool song 2
3. cool song 3
4. cool song 4

When you press play, the player must play cool song 1 first, then cool song 2, then cool song 3, then cool song 4 — the same order you added them in. To make this work, the program needs to:

• store all the songs somewhere, and
• play them back in the order they were inserted.

This is exactly FIFO behavior. The first song added is the first one played, and the last song added is the last one played.

Example 2: Call center

Now think about a customer care phone line. Many people call in at different times, and there may not be enough agents to answer everyone at once. So what is the fair way to handle them?

The fair rule is: whoever called first should be answered first. Almost every automated call center works this way. The software keeps each caller's information in a store, and when a customer service agent becomes free, the software hands over the call that has been waiting the longest — the one that arrived first.

If four people call (Call, Call, Call, Call), they get connected to an agent one by one, in the same order they called, until all customers are served. Again, this is FIFO in action.

Example 3: Disk scheduling

Here is one more example from inside the computer itself. Suppose you copy several files — file 1, file 2, file 3, file 4 — from one place to another.

An older hard disk can only do one read or write operation at a time. It cannot copy several files at the very same moment. (Newer hardware can do more at once, but we use the older style here because it shows FIFO clearly.)

So the disk keeps an internal list of all the write requests and handles them in the order they arrived:

1. Write file 1
2. Write file 2
3. Write file 3
4. Write file 4

It finishes the first request before starting the next. Once all four are done, all writes are complete. The order of processing is FIFO, just like the music list and the call center.

What comes next

These three are just a small sample. Many other problems in software can only be solved correctly by processing data in First In, First Out order. In every case, we need a place to store items and a guarantee that the oldest item comes out first.

In this course, we will learn about a data structure built exactly for this job — a queue. A queue is the tool that makes all of these FIFO systems possible.