Queue

Imagine you're standing in a line at a movie theater. The person who arrives first gets served first, while people who arrive later have to wait.

This is the basic idea behind a queue.

A queue follows the FIFO principle:

First In, First Out

In other words, the element that enters the queue first is the first element to leave.

How a Queue Works

Suppose we add three people to a queue:

John → Jason → Alex

John arrived first, so John will be served first.

We can visualize the queue like this:

Front                         Rear
  ↓                             ↓
┌──────┬───────┬──────┐
│ John │ Jason │ Alex │
└──────┴───────┴──────┘
   ↓
Leaves first

When John leaves:

Front              Rear
  ↓                  ↓
┌───────┬──────┐
│ Jason │ Alex │
└───────┴──────┘

Jason is now at the front.

Main Queue Operations

The most common queue operations are:

enqueue()
dequeue()
peek()

Enqueue adds an element to the rear of the queue.

Dequeue removes an element from the front.

Peek looks at the front element without removing it.

The idea is:

Enqueue → Add at the rear
Dequeue → Remove from the front
Peek    → View the front

Enqueue Operation

Suppose the queue is empty.

We add:

enqueue(10)
enqueue(20)
enqueue(30)

The queue becomes:

Front
 ↓
10 → 20 → 30
             ↑
            Rear

The first element added is at the front, while the latest element is at the rear.

Dequeue Operation

Now suppose we perform:

dequeue()

The element at the front is removed:

10 → 20 → 30
↑
Removed

The queue becomes:

Front
 ↓
20 → 30
      ↑
     Rear

So 10 leaves first because it entered first.

Peek Operation

If we want to see the front element without removing it, we use peek().

For example:

Queue<Integer> queue = new LinkedList<>();

queue.add(10);
queue.add(20);
queue.add(30);

System.out.println(queue.peek());

Output:

The queue remains:

10 → 20 → 30

Queue in Java

Java provides the Queue interface.

A common implementation is LinkedList:

import java.util.LinkedList;
import java.util.Queue;

class Main {
    public static void main(String[] args) {

        Queue<String> queue = new LinkedList<>();

        queue.add("John");
        queue.add("Jason");
        queue.add("Alex");

        System.out.println(queue);
    }
}

Output:

[John, Jason, Alex]

We can remove the first element:

String person = queue.remove();

System.out.println(person);

Output:

John

Now the queue contains:

[Jason, Alex]

`add()` vs `offer()`

Java provides two common ways to add elements to a queue:

queue.add(10);

and:

queue.offer(10);

Both add an element to the queue, but their behavior differs when the queue has a capacity limit.

For general queue usage, offer() is often preferred when you want a method that can indicate failure instead of throwing an exception.

Similarly, for removing elements, you may encounter:

remove()
poll()

and for viewing the front:

element()
peek()

The basic operations to remember are still:

offer → Add
poll  → Remove
peek  → View front

Checking Whether a Queue Is Empty

We can use:

queue.isEmpty()

For example:

if (queue.isEmpty()) {
    System.out.println("Queue is empty");
}

This is useful before trying to process elements from a queue.

Queue Using an Array

We can also implement a queue using an array.

A simple implementation looks like this:

class Queue {
    private int[] data;
    private int front;
    private int rear;

    Queue(int size) {
        data = new int[size];
        front = 0;
        rear = -1;
    }

    void enqueue(int value) {

        if (rear == data.length - 1) {
            System.out.println("Queue is full");
            return;
        }

        data[++rear] = value;
    }

    int dequeue() {

        if (front > rear) {
            System.out.println("Queue is empty");
            return -1;
        }

        return data[front++];
    }

    int peek() {

        if (front > rear) {
            System.out.println("Queue is empty");
            return -1;
        }

        return data[front];
    }
}

Here, front tells us where the next element will be removed, while rear tells us where a new element can be added.

The Problem with a Simple Array Queue

There's an important problem with the simple implementation above.

Suppose the queue has a capacity of 5:

10  20  30  40  50
↑               ↑
Front           Rear

Now we remove three elements:

40  50
↑    ↑
Front Rear

The beginning of the array has empty spaces, but rear may already be at the end.

A new element can't be added even though there is unused space at the beginning.

This problem is solved using a circular queue.

Circular Queue

A circular queue treats the end of the array as connected to the beginning.

Instead of:

1 → 2 → 3 → 4 → 5 → End

we can think of it as:

1 → 2 → 3 → 4 → 5
↑                 ↓
└─────────────────┘

When the rear reaches the end, it can wrap around to the beginning if there is available space.

Circular queues are especially useful when implementing queues with fixed-size arrays.

Queue Using a Linked List

A queue can also be implemented using a linked list.

We usually maintain two references:

Front                     Rear
 ↓                          ↓
10 → 20 → 30 → null

When we add an element, we add it at the rear:

10 → 20 → 30 → 40 → null
                     ↑
                    Rear

When we remove an element, we remove it from the front:

20 → 30 → 40 → null
↑
Front

With both front and rear references, enqueue and dequeue can be performed efficiently.

Queue Time Complexity

For a properly implemented queue:

Operation	Time Complexity
Enqueue	`O(1)`
Dequeue	`O(1)`
Peek	`O(1)`
Is Empty	`O(1)`

The important point is that we don't need to search through the entire queue to add or remove an element.

Real-Life Example

A queue is everywhere in real life.

Imagine people waiting at a bank:

John → Jason → Alex → Michael

John arrived first.

So:

John → Served first
Jason → Served second
Alex → Served third
Michael → Served fourth

This follows:

First In → First Out

That's exactly how a queue works.

Queue in a Printer

Another common example is a printer queue.

Suppose three documents are sent to a printer:

Document A
Document B
Document C

The printer can process:

A → B → C

The first document submitted is normally processed first.

The queue might look like:

Front
 ↓
A → B → C
         ↑
        Rear

After printing A:

Front
 ↓
B → C

Queue in Operating Systems

Queues are also used in operating systems.

For example, processes waiting for CPU time can be managed using queues.

You might have:

Process A → Process B → Process C → Process D

The operating system can select processes according to the scheduling strategy being used.

One classic scheduling approach is First Come, First Served, which follows queue-like behavior.

Queue in Breadth-First Search

One of the most important DSA applications of a queue is Breadth-First Search, or BFS.

BFS explores a graph or tree level by level.

For example:

BFS visits:

A → B → C → D → E

A queue helps keep track of which node should be processed next.

The basic process is:

Put starting node in queue
        ↓
Remove front node
        ↓
Process it
        ↓
Add its neighbors
        ↓
Repeat

We'll explore BFS in detail when we reach graph algorithms.

Stack vs Queue

It's important to clearly understand the difference between a stack and a queue.

A stack follows:

LIFO
Last In, First Out

A queue follows:

FIFO
First In, First Out

Think of a stack of plates:

Last plate added
       ↓
Removed first

Think of people waiting in line:

First person arrives
       ↓
Served first

So:

Stack → LIFO
Queue → FIFO

The Main Idea

A queue is a data structure that follows the FIFO (First In, First Out) principle.

The main operations are:

Enqueue → Add an element at the rear
Dequeue → Remove an element from the front
Peek    → View the front element

For example:

Front                  Rear
  ↓                      ↓
10 → 20 → 30 → 40

If we perform dequeue(), 10 is removed first.

If we perform enqueue(50), 50 is added at the rear:

20 → 30 → 40 → 50

Queues are widely used in scheduling, printer systems, task processing, BFS, networking, and many other real-world applications.

The key idea is simple:

The first element that enters a queue is the first element that comes out.

How a Queue Works

Main Queue Operations

Enqueue Operation

Dequeue Operation

Peek Operation

Queue in Java

add() vs offer()

Checking Whether a Queue Is Empty

Queue Using an Array

The Problem with a Simple Array Queue

Circular Queue

Queue Using a Linked List

Queue Time Complexity

Real-Life Example

Queue in a Printer

Queue in Operating Systems

Queue in Breadth-First Search

Stack vs Queue

The Main Idea

`add()` vs `offer()`