FIFO Approach in data structure
FIFO stands for First In First Out, in which we will enter the data elements into the data structure; the data element added at last in any data structure will be removed out last and the element added first will be removed first. Here, we treat the data elements with a fair chance; the element which has entered first will get the opportunity to leave first. The other name we call First Come First Serve is implemented using the data structure named a queue.
The best example to understand the FIFO principle is when we stand in a queue and want to take a movie ticket, and there are a lot of people standing before us, and we have no other choice left instead of waiting for our chance. If we observe the above example, we can easily see that we will get the chance after the people standing before us and will be treated as first come, first serve.
- The FIFO principle has great importance in the various processes scheduling algorithm, which the operating system does to finalize the schedule of several processes one after another.
- One of the algorithms that CPU uses is FCFS, first come, first serve to give a fair chance to every process, and it is implemented by using the queue data structure.
- In one of the primitive algorithms of scheduling, we will use the round-robin algorithm, and the circular queue has its great importance; by using the circular queue, we will be able to preempt the process and give a fair chance to every process using a circular queue. This algorithm is employed by process and network schedulers in computing.
- It is also used in computer-controlled Traffic Signal Systems.
- It is also used in CPU scheduling and memory management
- The data structure, based on the FIFO principle, is the queue.
- In the queue data structure, we will perform the two main operations: first, Enqueue operation for inserting the data elements into the queue, and another is Dequeue operation for removing the data elements from the queue.
- In stack, we will mainly use two operations push for pushing the data elements into the stack, and another is pop for removing the elements from the stack.
- The queue contains two ends, i.e., the front, and another is the rear
- Many programs are based on the concept of the FIFO principle.
- A queue is one of the important linear data structures extensively used in various computer applications, and also it is based on the FIFO ( First In First Out ) principle. It follows a particular order of data execution for which operations are performed. In this data structure, data enters from one end, i.e., the REAR end, and the next data enters the queue after the previous one. Deletion operation is performed from another end, i.e., FRONT
- As compared with stacks, stacks are also a linear data structure. Although, it is based on LIFO (Last In First Out) principle, which implies that data enters one by one from one end into the stack till it reaches its end limit, and it popped out the data element from the stack from that end itself.
- In a stack, only one pointer is needed for performing all operations, which is top, whereas, in the queue, there are two pointers needed, rear and front, for performing all operations.
The approach, as mentioned earlier, is known as the First-In-First-Out approach or FIFO.
Applications of FIFO Approach
The applications of FIFO are as follows:
1) Data Structures
The queue is a linear data structure based on the FIFO approach, in which data elements enter into the queue using the rear end, and from the front end, deletion of elements occurs.
FIFO approach is mostly used in network bridges, switches, and routers.
It is further categorized as linear queue
Linear Queue
A linear queue is a linear data structure based on FIFO (First in First Out) principle, in which data enters from the rear end and is deleted from the front end. A linear queue is said to be the simple queue, and whenever we need to talk about the queue, it is by default set that we are considering a linear queue. We will discuss these ends in more detail further.
Other examples like->
- People are waiting for the bus. The first person standing in the queue will be the first to get on the bus.
- Cars lined at a toll bridge. The first car to reach the bridge will be the first to leave.
Operations of linear Queue
There are certain basic operations has performed in the linear queue are as follows->
- Enqueue
- For the addition of data elements in the queue, this operation is used.
- By applying this operation, data is entered in the queue according to the sequence after one another. Enqueue will be continued till the queue reaches its end limit.
- After it reaches the endpoint, the data cannot add to the queue, and then such condition is said to be an Overflow condition.
- En-queue operation is done from the rear end.
- Dequeue
- This operation is used to delete a data element from the queue.
- Using Dequeue operation, that data element is deleted, which is enqueued first in the queue, or the elements are popped in the same order in which they are pushed.
- This process will delete the data elements from the queue until the whole queue becomes empty. Once all the elements are deleted, then the deletion operation is unable to execute, and then such condition is said to be an Underflow condition.
- It is done from the front end.
- Peek
This operation is used to find out the very first queue element, which is to be served first without dequeuing it.
Two Ends of Linear Queue
- Front end – It refers to the initial or starting position of the queue. The front end is mainly used to delete the data element from the queue or perform a dequeue operation.
- Rear-end – refers to the last or back position of the queue. The rear end is mainly used to insert the queue data elements or perform the en-queue operation.
Methods of Implementation of Linear queue
There are various methods of implementation of the queue:
- Queue implementation using an array
- Queue implementation using stack
- Queue implementation using linked list
Implementation of Linear queue using an Array
Here we discuss the implementation of queue using an array->
Queues can easily be implemented by using linear arrays. As stated earlier, the queue has front and rear pointers from which deletion and insertion of data elements can be done.
Steps
- Initially, we need to create an array of size ‘n’ whether statically or dynamically, depending on the user.
- Declare two pointers named FRONT and REAR.
- Initialize REAR = -1 and FRONT = 0.
- Create three functions named Enqueue for adding data elements in the Queue, Dequeue for deletion of a data element from the queue, and peek for finding out the first element from the queue without dequeuing it.
Algorithm of Enqueue operation
Step 1- Check if REAR == FRONT.
Step 2- If the above statement holds, then such a condition is said to be an Overflow, and further insertion of data elements is not possible.
Step 3- If it holds false, then
- set REAR = REAR + 1 and
- add the data element in queue at rear position.
- Queue[REAR] = data.
Algorithm of Dequeue operation
Step 1- Check if FRONT = REAR + 1
Step 2- If the above statement holds, then
- such condition is said to be Underflow condition.
- Return -1.
Step 3- If it holds false, then
- popped out the value from the queue present at the front position
- data = Queue[FRONT].
- Return data.
Step 4- After then Set FRONT = FRONT + 1, it points next data element.
Algorithm of Peek operation
Step 1- Check if FRONT = REAR + 1.
Step 2- If the above statement holds, display the message; the queue is empty.
Step 3- If it holds false,
- return the data element from the queue present at the front position.
- data = Queue[FRONT].
- Return data.
FIFO Approach implementation in C Programming language by queue using array
The Output of the above program is:
FIFO Approach implementation in C++ Programming language by queue using Array
The Output of the above program is:
FIFO Approach implementation in Java Programming language using queue
The Output of the above program is:
Queue is Empty 20 <-- 30 <-- 40 <-- 50 <-- Queue is full 20 <-- 30 <-- 40 <-- 50 <-- after two node deletion 40 <-- 50 <-- Front Element is: 40
FIFO Approach implementation in Python Programming language using queue
The Output of the above program is:
Elements of queue - [ 0, 1, 2, 3, 4 ] removed element - 0 [ 1, 2, 3, 4 ] Peek value of queue - 1 Size of queue - 4
FIFO Approach implementation in C# Programming language using queue
The Output of the above program is:
Elements of queue - [ 0, 1, 2, 3, 4 ] removed element - 0 [ 1, 2, 3, 4 ] Peek value of queue - 1 Size of queue - 4
FIFO Approach implementation in JavaScript Programming language using queue
The Output of the above program is:
Elements of queue - [ 0, 1, 2, 3, 4 ] removed element - 0 [ 1, 2, 3, 4 ] Peek value of queue - 1 Size of queue - 4
FIFO Approach implementation in C Programming language by queue using stack
The Output of the above program is:
Queue is empty !! Queue is full !! 20 30 40 50
FIFO Approach implementation in C++ Programming language by queue using stack
The Output of the above program is:
Queue is empty !! Queue is full !! 20 3 40 50
Circular Queue
Implementation of FIFO Approach using a circular queue
A circular queue is also one of the important types of a queue. It is similar to the linear queue but has some variations. The end position of a circular queue is connected back to the start position, forming the circular-like structure and making a circle. A circular queue is also based on the First In First Out (FIFO) principle. It is also known as ‘Ring Buffer’.
As we have seen previously, in a linear queue, further insertion of data elements is not possible when REAR reaches the end, and FRONT also reaches to end. The queue is still empty, but it shows that the queue is full, so to overcome the above problem concept of circular is introduced. In the circular queue, this problem will not arise. We will further discuss it in more detail in the below section.
The data structure, which is based on the FIFO principle, is a stack. We mainly perform two operations on it, push and pop. Push operation is used to push the data element into the stack, and pop operation is used to pop out the data elements from the stack.
There are certain basic operations has performed in the linear queue are as follows->
- Enqueue
- This operation is used to insert a data element in the queue.
- A data element is always added from the rear position in a circular queue.
- Dequeue
- This operation is used to remove a data element from the queue.
- In a circular queue, deletion of a data element is always done from the front position.
Two ends of Circular Queue
In a circular queue, there is a circle like structure; hence there are no two ends distinguished but still, to differentiate the insertion and deletion criteria of data elements, we refer to these two ends:
- Front end- is used to delete the data elements from the queue.
- The rear end is used to insert the data elements in the queue.
Implementation of Circular Queue using an array
A circular queue can easily be implemented using arrays. It works on the circular increment process. As stated earlier, it has two pointers, front and rear. From the rear end, insertion of data elements is possible. If the rear pointer reaches the end, it again increments back to the initial position of the queue so that further insertions can also be possible; hence this implies an increment process.
From the front end, deletion of data elements is possible. If the front pointer reaches the end, it returns to the queue’s initial position to make further deletions possible.
Using modulo division with the queue size, the circular increment is performed.
Steps
- Initially, we need to create an array of size ‘n’ whether statically or dynamically, depending on the user.
- Then declare two pointers named FRONT and REAR.
- Initialize REAR = -1 and FRONT = -1.
- Create two functions named Enqueue for adding data elements in the Queue and Dequeue for deleting data elements from the queue.
Implementation of Circular Queue
Algorithm of Enqueue operation
Step 1- Check if FRONT == 0 && REAR == (n-1) || REAR == (FRONT – 1) % (n-1).
Step 2- If the above statement holds, then such condition is said to be an Overflow, and further insertion of data elements is not possible.
Step 3- Else if FRONT == -1 then,
- set REAR = 0, FRONT = 0 and
- Add the data element in queue at rear position.
- Queue[REAR] = data.
Step 4- Else if REAR == (n-1) && FRONT != 0
- set REAR = 0 and
- Add the data element in queue at rear position.
- Queue[REAR] = data.
Step 5- Else
- set REAR = REAR + 1
- Add the data element in queue at rear position.
- Queue[REAR] = data.
Algorithm of Dequeue operation
Step 1- Check if FRONT == -1
Step 2- If the above statement holds, then
- such condition is said to be an Underflow condition.
- Return -1.
Step 3- If it holds false, then
- popped out value from the queue present at the front position
- data = Queue[FRONT].
- Return data.
Step 4- After then Set FRONT = FRONT + 1, it points next data element.
Step 5- If FRONT == REAR then, set FRONT = -1 and REAR = -1.
Step 6- Else if FRONT == n-1 then, set FRONT = 0.
FIFO Approach implementation in C Programming language by Circular queue
The Output of the above program is:
Enqueue value 20 successfully !! Enqueue value 30 successfully !! Enqueue value 40 successfully !! Enqueue value 60 successfully !! Enqueue value 70 successfully !! Queue is full !! Deleting value: 20 Deleting value: 30 Deleting value: 40 Deleting value: 60
FIFO Approach implementation in C++ Programming language by Circular queue using Structure
The Output of the above program is:
Enqueue value 7 successfully !! Enqueue value 11 successfully !! Enqueue value 4 successfully !! Enqueue value 6 successfully !! Enqueue value 7 successfully !! Queue is full !! Deleting value: 7 Deleting value: 11 Deleting value: 4 Deleting value: 6
FIFO Approach implementation in Java Programming language by Circular Queue using Array
The Output of the above program is:
Elements in Circular Queue are : 14 22 13 8 Deleted value = 14 Deleted value = 22 Elements in Circular Queue are : 13 8 Elements in Circular Queue are : 13 8 9 20 5 Queue is Full !!
FIFO Approach implementation in Python Programming language by Circular queue using Array
The Output of the above program is:
Elements in Circular Queue are : 4 22 3 -6 Deleted value = 4 Deleted value = 22 Elements in Circular Queue are : 3 -6 Elements in Circular Queue are : 3 -6 19 2 15 Queue is Full !!
FIFO Approach implementation in C Programming language by Circular Queue using Linked List
The Output of the above program is:
Enqueue value is: 20 Enqueue value is: 30 Enqueue value is: 40 Deleting value: 20 Deleting value: 30 Deleting value: 40 Queue is empty !! Enqueue value is: 60 Enqueue value is: 50 Enqueue value is: 70 Queue is full !!
FIFO Approach implementation in C++ Programming language by Circular queue using Linked List
The Output of the above program is:
Enqueue value is: 20 Enqueue value is: 30 Enqueue value is: 40 Deleting value: 20 Deleting value: 30 Deleting value: 40 Queue is empty !! Enqueue value is: 60 Enqueue value is: 50 Enqueue value is: 70 Queue is full !!
FIFO Approach implementation in Java Programming language by Circular Queue using Linked List
The Output of the above program is:
Elements in Circular Queue are : 10 2 16 Deleted value = 10 Deleted value = 2 Elements in Circular Queue are : 16 Elements in Circular Queue are : 16 19 7
FIFO Approach implementation in Python Programming language by Circular Queue using Linked List
The Output of the above program is:
Elements in Circular Queue are : 10 2 16 Deleted value = 10 Deleted value = 2 Elements in Circular Queue are : 16 Elements in Circular Queue are : 16 19 7
Advantages of Circular Queue over Linear queue
- Linear Queue consumes more memory as compared to circular queue.
- A circular queue uses an efficient way for memory utilization.
- In a circular queue, new data can be inserted again at a particular position after deleting previous data on that position.
- In a linear queue, if the rear pointer reaches last and the front pointer deletes all data from the queue, it remains to show the message of Overflow, which is the main drawback of the linear queue.
- An overflow message is shown in a circular queue when the queue is full.
- Easy to perform dequeue operation and enqueue operation.