A Queue is a linear data structure that follows the First-In-First out principle . this means that the first element added to the queue will be the first one to be removed .

Structure and Operations

1. Enqueue : Adding an element to the rear of the queue .
2. Dequeue : Removing an element from the front of the queue .
3. Peek/Front : Viewing the front element without removing it .
4. isEmpty: Checking if the Queue is empty.
5. Size: Getting the number of elements in the queue .

Types of Queue

• Simple Queue
• Circular Queue
• Priority Queue
• Dequeue

Benefits of using Queue

1. Order Preservation : maintains the order of element ensuring that the first element added in the first one processed .
2. Resource Management : useful in managing resources like cpu scheduling , printer spolling and task scheduling .

Use Cases

1. Task Scheduling : In operating system, queues are used to manage tasks that need to be executed in order .
2. Print Queue : Managing print jobs in a printer , ensuring documents are printed in the order they were submitted .

Queue is structure that is going to follow some rule for insertion , deletion , and modification . Insertion will happent from one end and deletion will happent from another end .

Condition :

1. The queue is EMPTY (rear==-1 && front ==-1)

If (rear==-1 && front ==-1)

• front==-1
  • This means
    • There is no first element in the queue .
    • The queue currently contains zero elements
• rear==-1
  • This means
    • There is no last elements in the queue .
    • No enqueue operations have happened .

2.Queue has exactly 1 element (front == rear)

if(front==rear)

3.when Queue is Full (rear == n – 1)

if(rear==n-1)

Program1: Implementation of Queue using Arrays

package com.test.rkdigital.school.queue;

public class SimpleQueue 
{
	private int[] arr;  //Array to store queue elements 
	private int front;  // points to front element 
	private int rear;   // points to last element 
	private int capacity;  // max size of queue 
	
	
	public SimpleQueue(int size) {
		capacity=size;
		arr=new int[size];
		front=0;
		rear=-1;
	}
	
	//Add element to queue 
	public void enqueue(int value) {
		if(rear == capacity-1) {
			System.out.println("Queue is full");
			return;
		}
		arr[++rear]=value;
		System.out.println(value +"Enqued");
	}
	
	// Removed element from queue 
	public int dequeue() {
		if(front>rear) {
			System.out.println("Queue is empty");
			return -1;
		}
		int value=arr[front++];
		return value;
	}
	
	//Peek front element 
	public int peek() {
		if(front>rear) {
			System.out.println("Queue is empty");
			return -1;
		}
		return arr[front];
	}
	
	//Display full Queue 
	public void display() {
		if(front>rear) {
			System.out.println("Queue is empty");
			return;
		}
		System.out.println("Queue");
		for (int i = front; i <=rear; i++) {
			System.out.println(arr[i]+"");
		}
		System.out.println();
	}
	//Main to test 
	public static void main(String[] args) {
		SimpleQueue queue=new SimpleQueue(5);
		
		queue.enqueue(10);
		queue.enqueue(20);
		queue.enqueue(30);
		
		queue.display();
		System.out.println("Dequed:"+queue.dequeue());
		System.out.println("Front now :"+queue.peek());
		
		queue.display();
		
	}

}

Program2: Implementation of Queue using LinkedList

class LinearQueue {
    
    // Node structure
    private static class Node {
        int data;
        Node next;

        Node(int value) {
            this.data = value;
            this.next = null;
        }
    }

    private Node front;   // Head of queue
    private Node rear;    // Tail of queue
    private int size;     // Tracks number of elements

    public LinearQueue() {
        front = rear = null;
        size = 0;
    }

    // Check if queue is empty
    public boolean isEmpty() {
        return front == null;
    }

    // Add (enqueue)
    public void enqueue(int value) {
        Node newNode = new Node(value);
        if (rear == null) {          // Queue empty
            front = rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
        size++;
    }

    // Remove (dequeue)
    public int dequeue() {
        if (isEmpty()) {
            System.out.println("Queue Underflow - empty queue");
            return -1;
        }

        int val = front.data;
        front = front.next;

        if (front == null) {        // After removing last node
            rear = null;
        }
        size--;
        return val;
    }

    // Peek front element
    public int peek() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return -1;
        }
        return front.data;
    }

    // Return size
    public int size() {
        return size;
    }

    // Main to test
    public static void main(String[] args) {
        LinearQueue q = new LinearQueue();

        q.enqueue(40);
        q.enqueue(50);
        q.enqueue(60);

        System.out.println("Front: " + q.peek());     
        System.out.println("Dequeue: " + q.dequeue()); 
  

        q.enqueue(40);
        System.out.println("Front: " + q.peek());     
        System.out.println("Size: " + q.size());      
    }
}

Advantages of Queue Implementation Using LinkedList Over Array

Dynamic Size — No Fixed Capacity

• In an array queue, you must define a fixed size at the beginning.
• In a linked list queue, memory grows dynamically as elements are added.
• There is no overflow unless the system itself runs out of memory.

Enqueue is Always O(1) Without Wasting Space

• In array-based linear queues, rear eventually hits the end, and free spaces at the front cannot be reused unless shifting is done.
• LinkedList does not require shifting or circular logic.
• Every enqueue simply adds a new node at the rear in O(1) time.

Dequeue is Always O(1)

• Removing the front node in a LinkedList is O(1) because front simply moves to the next node.
• In arrays, dequeue may cost O(n) if shifting is used.

No Wasted or Unused Memory

• Array queues often create unused spaces when elements are dequeued from the front.
• Linked Lists naturally reuse memory because they allocate nodes only when needed.