Articles / DSA · Part 17

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.

Queue Data Structure: Understanding FIFO

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:

  • front keeps track of the first element.
  • rear keeps 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 = 0 represents the starting position.
  • rear = -1 indicates 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

Keep a copy

Read offline as a printout or PDF.

farhanpaal.com

Keep reading

Ask Farhan

Ask anything about Farhan