Queue Data Structure: Understanding FIFO
Understand the Queue data structure and its FIFO principle. Learn Enqueue, Dequeue, Front, and Rear operations with simple examples, C implementation, and real-world applications.
In the previous article, we learned about Stacks and their applications. A Stack follows the LIFO (Last In, First Out) principle.
Now let’s explore another important linear data structure: Queue.
A Queue follows a different principle called FIFO (First In, First Out).
1. What Is a Queue?
A Queue is a linear data structure in which elements are inserted from one end and removed from the other.
Think about standing in a line at a ticket counter.
- The person who arrives first gets the ticket first.
- New people join at the end of the line.
- Nobody is served before the people who arrived earlier.
A Queue works in exactly the same way.
<AsyncImage query=”simple computer science FIFO queue diagram five numbered boxes front dequeue rear enqueue clean blue white educational illustration” aspectRatio=”16:9″ width=”100%” />
FIFO stands for First In, First Out. It means the element inserted first is the first one to be removed.
For example, consider a Queue containing:
10 20 30 40
Here, 10 entered first, so it will be removed first.
2. Understanding Front and Rear
A Queue has two important ends:
- Front: The position from which elements are removed.
- Rear: The position at which new elements are inserted.
Consider:
FRONT REAR
↓ ↓
[10] [20] [30] [40]
The next element to be removed is 10, while a new element will be added after 40.
3. Basic Operations of a Queue
A Queue mainly supports the following operations:
| Operation | Purpose |
|---|---|
| Enqueue | Adds an element at the rear |
| Dequeue | Removes an element from the front |
| Peek | Returns the front element without removing it |
| isEmpty | Checks whether the Queue is empty |
| isFull | Checks whether the Queue is full |
Let’s understand the two main operations.
Enqueue (Insertion)
Enqueue means adding a new element to the rear of the Queue.
Initially:
[10] [20] [30]
Now, perform:
Enqueue(40)
The element 40 is added at the rear.
[10] [20] [30] [40]
Dequeue (Deletion)
Dequeue means removing an element from the front of the Queue.
Initially:
[10] [20] [30] [40]
↑
FRONT
Now, perform:
Dequeue()
The first element, 10, is removed.
[20] [30] [40]
↑
FRONT
Notice that 20 is now the first element and will be removed in the next Dequeue operation.
Important: In a Queue, insertion happens at the rear, while deletion happens at the front.
4. Implementing a Queue Using an Array in C
We can implement a Queue using an array and two variables:
frontkeeps track of the first element.rearkeeps track of the last element.
Let’s implement a simple Queue with a maximum capacity of 5 elements.
C Implementation:
#include <stdio.h>
#define SIZE 5
int queue[SIZE];
int front = 0;
int rear = -1;
void enqueue(int value) {
if (rear == SIZE - 1) {
printf("Queue is full\n");
return;
}
queue[++rear] = value;
printf("%d inserted\n", value);
}
void dequeue() {
if (front > rear) {
printf("Queue is empty\n");
return;
}
printf("%d removed\n", queue[front++]);
}
void peek() {
if (front > rear) {
printf("Queue is empty\n");
return;
}
printf("Front element: %d\n", queue[front]);
}
void display() {
if (front > rear) {
printf("Queue is empty\n");
return;
}
for (int i = front; i <= rear; i++) {
printf("%d ", queue[i]);
}
printf("\n");
}
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
display();
dequeue();
display();
peek();
return 0;
}
Output:
10 inserted
20 inserted
30 inserted
10 20 30
10 removed
20 30
Front element: 20
Understanding the Code
Let’s understand a few important statements:
1. Initial values
int front = 0;
int rear = -1;
Initially, the Queue is empty.
front = 0represents the starting position.rear = -1indicates that no element has been inserted yet.
2. Insertion
queue[++rear] = value;
First, rear increases by one. Then the new value is stored at that position.
3. Deletion
queue[front++];
The current front element is accessed, and then front moves to the next position.
The element is logically removed from the Queue, even though its old value may still remain in the array.
5. Limitations of a Simple Array Queue
There is one problem with the simple array implementation.
Consider an array with a capacity of 5:
[10] [20] [30] [40] [50]
Now, remove two elements using Dequeue.
[ ] [ ] [30] [40] [50]
↑
REAR
The first two positions are now free, but rear is already at the last position of the array.
If we try to insert another element, the program reports that the Queue is full.
This happens because our simple implementation does not reuse the empty positions at the beginning of the array.
This limitation can waste available space.
We can solve this problem using a Circular Queue, where the rear can move back to the beginning of the array when space is available.
We’ll explore this in the next article.
6. Applications of Queues
Queues are used in many practical situations:
- Printer Scheduling: Documents are generally printed in the order they are submitted.
- CPU Scheduling: Operating systems use different scheduling methods to manage processes waiting for CPU time.
- Customer Service Systems: Requests can be handled in the order they arrive.
- Breadth-First Search (BFS): A graph traversal algorithm that uses a Queue to visit nearby vertices first.
- Network Communication: Queues help manage packets waiting to be processed or transmitted.
7. Stack vs Queue
Both Stack and Queue are linear data structures, but they follow different principles.
| Feature | Stack | Queue |
|---|---|---|
| Principle | LIFO | FIFO |
| Insertion | Top | Rear |
| Deletion | Top | Front |
| Insertion operation | Push | Enqueue |
| Deletion operation | Pop | Dequeue |
| Example | Stack of plates | People in a line |
A Queue is a linear data structure that follows FIFO (First In, First Out). Elements are inserted at the rear and removed from the front.
We can implement a Queue using arrays or linked lists. However, a simple array implementation has a limitation: it cannot reuse the empty positions created at the beginning of the array.
In the next article, we’ll explore Circular Queues, Deques, and Priority Queues, which introduce different ways of managing elements in a Queue.
Further reading: OpenDSA – Queues · GeeksforGeeks – Queue Data Structure
Originally published at farhanpaal.com — https://farhanpaal.com/articles/queue-data-structure-understanding-fifo/
Keep a copy
Read offline as a printout or PDF.
farhanpaal.com