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

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 Algorithms, Competitive Programming, JavaScript, System Design, Machine 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 problems, interview 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!!