Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Where is FIFO Used?
2.1.
Data Structures
2.2.
Disc Scheduling
2.3.
Networking and communication
3.
FIFO approach is used in Data Structures
3.1.
Linear Queue
3.1.1.
Examples:
3.2.
Linear Queue Operations
3.2.1.
Enqueue
3.2.2.
Dequeue
3.2.3.
Peek
3.2.4.
Two End-Points of a Linear Queue
4.
Implementation of Linear Queue
4.1.
Implementation in C++
4.2.
Implementation in Python
4.3.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
What is queue data structure?
5.2.
What is Queue Operations Complexity Analysis?
5.3.
What are different types of Queue?
5.4.
    What are certain use cases of the FIFO Programming approach?
6.
Conclusion
Last Updated: Mar 27, 2024

FIFO (First-In-First-Out) approach in Programming

Author Akshit Mehra
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will discuss the FIFO (First-in-First-Out)) the approach in Programming Paradigm. The acronym FIFO stands for first in, first out. It is a data structure processing approach in which the oldest element is treated first, and the newest element is handled last.

In this case, the following factors must be considered:

 

                                                          Figure: First-In-First-Out Approach example

  1. People arrive at the ticket booth, grab their tickets, and go.
  2. People form a line (Queue) in order to reach the Ticket Counter in a timely way.
  3. The individual who enters the line first will be the first to receive a ticket and exit the line.
  4. The following person in line will receive the ticket after the one in front of him.
  5. As a result, the individual who enters the Queue last will receive the last tickets.

 

As a result, the first person in line receives the ticket first, and the last person in line receives the ticket last.

This is referred to as the FIFO (First-In-First-Out) strategy.

Where is FIFO Used?

Below are certain cases where the FIFO approach is used:

Data Structures

Certain data structures, such as Queue and various Queue variations, adopt a FIFO method for data processing.

Disc Scheduling

The FIFO can be used by disc controllers as a disc scheduling mechanism to decide the order in which disc I/O requests are serviced.

Networking and communication

In computer networks, FIFOs are used to keep data packets on route to their next destination in communication network bridges, switches, and routers.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

FIFO approach is used in Data Structures

The Queue is a linear data structure based on the first-in, first-out (FIFO) technique, in which data pieces are added to the Queue from the back end and deleted from the front End. The first-in, first-out (FIFO) technique is commonly employed in network bridges, switches, and routers. It's also referred to as a linear queue.

Linear Queue

A linear queue is a data structure based on the FIFO (First in, First Out) principle, in which data is inserted from the back End and removed from the front End. A linear queue is referred to as the "simple queue," and whenever we discuss queues, we are referring to a linear queue by default. We'll go through these points in greater depth later.

Examples:

  1. People are awaiting the arrival of the bus. The individual who is first in line will be the first to board the bus.
  2. A toll bridge had a long line of cars. The automobile that arrives first at the bridge will be the first to leave.

Linear Queue Operations

Following are mentioned the significant operations in a Linear Queue data structure:

Enqueue

  1. This operation is used to add new data items to the Queue.
  2. Using this action, data is inserted into the Queue in the order in which it was received. The Queue will be continued until it reaches its maximum capacity.
  3. When data cannot be added to the Queue after it reaches the endpoint, this is an Overflow situation.
  4. From the rear end, the en-queue process is carried out.

Dequeue

  1. To delete a data element from the Queue, perform this operation.
  2. That data element is deleted, which is enqueued first in the Queue, or the items are popped in the same order as they were put, using the Dequeue method.
  3. This procedure will remove data components from the Queue until it is empty. When all of the items have been deleted, the deletion procedure is unable to complete, which is referred to as an Underflow situation.
  4. It is carried out on the front End.

Peek

This operation is used to find out the very first queue element, which will be served first without dequeuing it.

Two End-Points of a Linear Queue

  1. Front-End: The initial or starting position of the Queue is referred to as the front End. The front end is mostly used to delete data elements from queues or dequeue them.
  2. Rear-End: The last or last position in the Queue is referred to as rear-end. The rear-end is primarily responsible for inserting queue data items and performing en-queue operations.

Implementation of Linear Queue

Below is the Implementation of the Linear Queue:

Implementation in C++

#include "bits/stdc++.h"
using namespace std;

void solve()
{  
    //Defining a queue
    queue<int>q;
    int n = 6;
    //Inserting elements in the queue
    for(int i = 1;i<=n;i+=1){
        q.push(i);
    }

    cout<<"Peek the Element: ";
    cout<<q.front()<<'\n';
   
    //Poping the element from the queue;
    q.pop();

    //Peeking the front element again;
    cout<<"Peek the Element: ";
    cout<<q.front()<<'\n';

    //Printing the rest of queue
    while(!q.empty()){
        cout<<q.front()<<" ";
        q.pop();
    }
}  
int main()
{
    solve();
    return 0;
}

Implementation in Python

#Defining a queue
queue = []


#Inserting Elements in the queue
for i in range(6):
    queue.append(i)


#Displaying the contents of a queue
print("Queue: ", queue)


#Peeking the Queue
front = queue[0]
print("The front of the queue: ", front)


#Popping the first element
dele_ = queue.pop(0)


#Popped Element
print("Popped Element: ", dele_)


#Peeking the Queue
front = queue[0]
print("The front of the queue: ", front)



#Size of the queue
print("Size of the Queue: ", len(queue)

 

Output:

Peek the Element: 1
Peek the Element: 2
2 3 4 5 6

Complexity Analysis

Below the the complexities of the above mentioned operations:

Enqueue (Insert):

Time complexity: O(1)

Explanation: As we maintain 2 pointers (Front and End), we simply insert at the End and increment the end pointer.

Dequeue (Delete)

Time Complexity: O(1)

Explanation: As we maintain 2 pointers (Front and End), we simply increment the FRONT pointer.

Peek:

Time Complexity: O(1)

Explanation: Here, we just print the element at the REAR Pointer, thus O(1)

Frequently Asked Questions

What is queue data structure?

A queue is a linear collection of items entered and removed according to the first-in-first-out (FIFO) principle. Enqueue is the process of adding an element to a queue, while Dequeue is the process of removing an element from a queue.

What is Queue Operations Complexity Analysis?

Below is the complexity analysis of the Queue operations:

  1. By moving the initial element off the front of the Queue, queues provide random access to their contents. You must repeat this process to access an arbitrary element in the Queue. As a result, access is O(n).
  2. Iterating until you discover a specific value in the Queue is required while searching for it. As a result, the search is O(n). 
  3. Queue insertion is O(1) in the case of an efficient queue implementation.
  4. The process of deleting items from a queue occurs at the front of the line. Queue deletion is O(1) in the case of an efficient queue implementation.

What are different types of Queue?

Below are mentioned certain types of queue:

  1. Simple Queue - is a linear data structure in which elements are deleted in the same order as they were inserted, i.e., the one placed first will be removed first.
  2. A circular Queue - is a linear data structure in which operations are carried out according to the FIFO (First In, First Out) principle, and the final place is connected to the first to form a circle. A circular queue reduces the space waste that occurs when using arrays in a standard queue implementation.
  3. Priority Queue: A priority queue is one in which each element has a priority value, and the priority value determines the deletion of the entries. In a max-priority queue, the element with the highest priority value is removed first. When using a min-priority queue, the element with the lowest priority value will be removed first.
  4. De-queue (Double-ended Queue) - permits insertion and deletion from both ends, allowing elements to be added or deleted from both the End and the front.

    What are certain use cases of the FIFO Programming approach?

Below are certain cases where the FIFO approach is used:

  1. Data Structures: Certain data structures, such as Queue and various Queue variations, adopt a FIFO method for data processing.
  2. Disc Scheduling: Disc controllers can use the FIFO as a disc scheduling mechanism to decide the order in which disc I/O requests are serviced.
  3. Networking and communication: In computer networks, FIFOs keep data packets on route to their next destination in communication network bridges, switches, and routers.

Conclusion

In this blog, we discussed FIFO (First-In-First-Out) approach in Programming We also discuss the programming approach along with its time and space complexity.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!

Previous article
Queue Data Structure and Implementation in Java
Next article
How to Remove a Specific Element from Queue
Live masterclass