📘 Unit IV: Queue
Complete Exam & Teaching Notes | BCA / BIT / MCA / BSc.CSIT
Full Theory + Terminology + Algorithms + Variations + Applications + Java Programs + Q&A
Unit Objectives:
- Discuss queue terminology and operations.
- Gain proficiency in implementing queue insertion and deletion algorithms.
- Recognize queue variations and their applications, such as circular queues and priority queues.
4.1 Introduction to Queue
What is a Queue?
A queue is a linear data structure that follows the FIFO (First In, First Out) principle — the element inserted first is the first one to be removed.
Real-world examples:
- Bank line — first person to arrive is first served.
- Printer queue — documents printed in order sent.
- CPU scheduling — processes executed in arrival order.
- Traffic at a toll booth — first car in is first car through.
A queue has two ends:
- REAR (Back): Where new elements are inserted (enqueue).
- FRONT: Where elements are removed (dequeue).
Queue vs Stack
STACK (LIFO): QUEUE (FIFO):
TOP → | 30 | ← insert/delete FRONT→[10][20][30]←REAR
| 20 | at same end dequeue enqueue
| 10 |
| Feature | Stack | Queue |
|---|---|---|
| Principle | LIFO | FIFO |
| Insertion | At TOP | At REAR |
| Deletion | From TOP | From FRONT |
| Pointers | One (TOP) | Two (FRONT, REAR) |
Queue as ADT
ADT Queue {
Data: FRONT, REAR pointers + element array
Operations:
enqueue(item) : Insert at REAR
dequeue() : Remove from FRONT
peek() : View FRONT without removing
isEmpty() : True if no elements
isFull() : True if at max capacity
size() : Count of elements
Errors:
Overflow : enqueue on full queue
Underflow : dequeue on empty queue
}
4.2 Queue Terminology
| Term | Definition |
|---|---|
| FRONT | Index of first element; dequeue happens here |
| REAR | Index of last element; enqueue happens here |
| ENQUEUE | Insert a new element at REAR |
| DEQUEUE | Remove and return element from FRONT |
| PEEK | View FRONT element without removing |
| OVERFLOW | Error: ENQUEUE on full queue (REAR == MAX-1) |
| UNDERFLOW | Error: DEQUEUE on empty queue (FRONT == -1) |
| isEmpty | FRONT == -1 — queue has no elements |
| isFull | REAR == MAX-1 — queue at maximum capacity |
| FIFO | First In First Out — fundamental queue property |
| MAX_SIZE | Maximum elements a queue can hold |
| Circular Queue | REAR wraps to index 0 to reuse freed slots |
| Priority Queue | Elements served by priority, not arrival order |
4.3 Algorithm for Insertion in Queue (ENQUEUE)
State: front = -1, rear = -1 (empty). Full when rear == MAX-1.
Algorithm ENQUEUE(queue, front, rear, MAX, item):
Step 1: IF rear = MAX - 1 THEN
Print "QUEUE OVERFLOW"
Return
END IF
Step 2: IF front = -1 THEN
SET front = 0 [First element]
END IF
Step 3: SET rear = rear + 1
Step 4: SET queue[rear] = item
Step 5: Return
Java Implementation
public class SimpleQueue {
int[] queue;
int front, rear, max;
SimpleQueue(int size) {
queue = new int[size];
max = size; front = -1; rear = -1;
}
void enqueue(int item) {
if (rear == max - 1) {
System.out.println("Queue Overflow! Cannot enqueue " + item);
return;
}
if (front == -1) front = 0;
rear++;
queue[rear] = item;
System.out.println("Enqueued: " + item +
" | FRONT=" + front + " REAR=" + rear);
}
}
Time Complexity: O(1)
Enqueue Trace (MAX=5)
Initial: front=-1, rear=-1, [ _ _ _ _ _ ]
enqueue(10): front=0, rear=0, [10 _ _ _ _ ]
enqueue(20): front=0, rear=1, [10 20 _ _ _ ]
enqueue(30): front=0, rear=2, [10 20 30 _ _ ]
enqueue(40): front=0, rear=3, [10 20 30 40 _ ]
enqueue(50): front=0, rear=4, [10 20 30 40 50]
enqueue(60): OVERFLOW! rear == MAX-1 == 4
4.4 Algorithm for Deletion in Queue (DEQUEUE)
Algorithm DEQUEUE(queue, front, rear):
Step 1: IF front = -1 THEN
Print "QUEUE UNDERFLOW"
Return NULL
END IF
Step 2: SET item = queue[front]
Step 3: IF front = rear THEN
SET front = -1 [Queue became empty]
SET rear = -1
ELSE
SET front = front + 1 [Move FRONT forward]
END IF
Step 4: Return item
Java Implementation
int dequeue() {
if (front == -1) {
System.out.println("Queue Underflow! Queue is empty");
return -1;
}
int item = queue[front];
if (front == rear) { front = -1; rear = -1; }
else front++;
System.out.println("Dequeued: " + item +
" | FRONT=" + front + " REAR=" + rear);
return item;
}
Time Complexity: O(1)
Dequeue Trace
Start: front=0, rear=4, [10 20 30 40 50]
dequeue(): item=10, front=1, rear=4, [ _ 20 30 40 50]
dequeue(): item=20, front=2, rear=4, [ _ _ 30 40 50]
dequeue(): item=30, front=3, rear=4, [ _ _ _ 40 50]
dequeue(): item=40, front=4, rear=4, [ _ _ _ _ 50]
dequeue(): item=50, front=-1,rear=-1 [ _ _ _ _ _] EMPTY
dequeue(): UNDERFLOW!
Complete Queue Program in Java
public class SimpleQueue {
int[] queue;
int front, rear, max;
SimpleQueue(int size) {
queue = new int[size];
max = size; front = -1; rear = -1;
}
void enqueue(int item) {
if (rear == max - 1) { System.out.println("Overflow!"); return; }
if (front == -1) front = 0;
queue[++rear] = item;
System.out.println("Enqueued: " + item + " [F=" + front + " R=" + rear + "]");
}
int dequeue() {
if (front == -1) { System.out.println("Underflow!"); return -1; }
int item = queue[front];
if (front == rear) { front = -1; rear = -1; }
else front++;
System.out.println("Dequeued: " + item + " [F=" + front + " R=" + rear + "]");
return item;
}
int peek() { return (front == -1) ? -1 : queue[front]; }
boolean isEmpty() { return front == -1; }
boolean isFull() { return rear == max - 1; }
int size() { return (front == -1) ? 0 : rear - front + 1; }
void display() {
if (front == -1) { System.out.println("Queue is empty"); return; }
System.out.print("Queue [FRONT->REAR]: ");
for (int i = front; i <= rear; i++) System.out.print(queue[i] + " ");
System.out.println();
}
public static void main(String[] args) {
SimpleQueue q = new SimpleQueue(5);
q.enqueue(10); q.enqueue(20); q.enqueue(30);
q.enqueue(40); q.enqueue(50);
q.enqueue(60); // Overflow
q.display();
q.dequeue(); q.dequeue();
q.display();
System.out.println("Peek: " + q.peek());
System.out.println("Size: " + q.size());
}
}
Output:
Enqueued: 10 [F=0 R=0]
Enqueued: 20 [F=0 R=1]
Enqueued: 30 [F=0 R=2]
Enqueued: 40 [F=0 R=3]
Enqueued: 50 [F=0 R=4]
Overflow!
Queue [FRONT->REAR]: 10 20 30 40 50
Dequeued: 10 [F=1 R=4]
Dequeued: 20 [F=2 R=4]
Queue [FRONT->REAR]: 30 40 50
Peek: 30
Size: 3
4.5 Limitation of Simple Queue
The Core Problem — False Overflow / Memory Wastage
Even when empty slots exist at the front (freed by dequeue), we CANNOT use them. REAR can only move forward, never backward.
MAX = 5. After enqueue(10..50) then dequeue() x3:
Index: [0] [1] [2] [3] [4]
Status: [ X ][ X ][ X ][40 ][50 ] X = wasted
↑ ↑
front rear
enqueue(60) → OVERFLOW! ← BUT slots 0,1,2 are FREE!
Limitations Summary
| Limitation | Description |
|---|---|
| False Overflow | Overflow reported even when front slots are empty |
| Memory Wastage | Slots freed by dequeue() are NEVER reused |
| Fixed Capacity | Cannot grow beyond MAX size |
| Inefficiency | As FRONT moves forward, usable memory shrinks forever |
Solution: Circular Queue
Use rear = (rear + 1) % MAX so that REAR wraps back to index 0 after reaching MAX-1, allowing all freed slots to be reused.
4.6 Variations in a Queue
4.6.1 Circular Queue
A circular queue connects the last position back to the first using modulo arithmetic, enabling efficient reuse of all array slots.
Circular Queue Visualization (MAX=5):
[0]
/ \
[4] [1]
\ /
[3]--[2]
rear wraps: after index 4, next index = (4+1)%5 = 0
Key Formulas:
Move REAR: rear = (rear + 1) % MAX
Move FRONT: front = (front + 1) % MAX
Full: count == MAX
Empty: count == 0
Circular Queue — ENQUEUE Algorithm
Algorithm CIRCULAR_ENQUEUE(queue, front, rear, MAX, count, item):
Step 1: IF count = MAX THEN
Print "CIRCULAR QUEUE OVERFLOW"
Return
END IF
Step 2: IF front = -1 THEN
SET front = 0
SET rear = 0
ELSE
SET rear = (rear + 1) % MAX
END IF
Step 3: SET queue[rear] = item
Step 4: SET count = count + 1
Step 5: Return
Circular Queue — DEQUEUE Algorithm
Algorithm CIRCULAR_DEQUEUE(queue, front, rear, MAX, count):
Step 1: IF count = 0 THEN
Print "CIRCULAR QUEUE UNDERFLOW"
Return NULL
END IF
Step 2: SET item = queue[front]
Step 3: SET count = count - 1
Step 4: IF count = 0 THEN
SET front = -1
SET rear = -1
ELSE
SET front = (front + 1) % MAX
END IF
Step 5: Return item
Complete Circular Queue Program in Java
public class CircularQueue {
int[] queue;
int front, rear, max, count;
CircularQueue(int size) {
queue = new int[size];
max = size; front = -1; rear = -1; count = 0;
}
boolean isFull() { return count == max; }
boolean isEmpty() { return count == 0; }
void enqueue(int item) {
if (isFull()) {
System.out.println("Circular Queue Overflow! Cannot enqueue " + item);
return;
}
if (front == -1) { front = 0; rear = 0; }
else rear = (rear + 1) % max; // WRAP AROUND
queue[rear] = item;
count++;
System.out.println("Enqueued: " + item +
" | FRONT=" + front + " REAR=" + rear);
}
int dequeue() {
if (isEmpty()) {
System.out.println("Circular Queue Underflow!");
return -1;
}
int item = queue[front];
count--;
if (count == 0) { front = -1; rear = -1; }
else front = (front + 1) % max; // WRAP AROUND
System.out.println("Dequeued: " + item +
" | FRONT=" + front + " REAR=" + rear);
return item;
}
void display() {
if (isEmpty()) { System.out.println("CQ Empty"); return; }
System.out.print("Circular Queue: ");
int i = front;
for (int k = 0; k < count; k++) {
System.out.print(queue[i] + " ");
i = (i + 1) % max;
}
System.out.println("| Size=" + count + "/" + max);
}
public static void main(String[] args) {
CircularQueue cq = new CircularQueue(5);
System.out.println("=== Fill the queue ===");
cq.enqueue(10); cq.enqueue(20); cq.enqueue(30);
cq.enqueue(40); cq.enqueue(50);
cq.enqueue(60); // Overflow
cq.display();
System.out.println("\n=== Dequeue 3 ===");
cq.dequeue(); cq.dequeue(); cq.dequeue();
cq.display();
System.out.println("\n=== Enqueue 3 more (reuse freed slots!) ===");
cq.enqueue(60); // rear wraps to 0
cq.enqueue(70); // rear wraps to 1
cq.enqueue(80); // rear wraps to 2
cq.display();
System.out.println("\n=== Overflow again ===");
cq.enqueue(90);
}
}
Output:
=== Fill the queue ===
Enqueued: 10 | FRONT=0 REAR=0
Enqueued: 20 | FRONT=0 REAR=1
Enqueued: 30 | FRONT=0 REAR=2
Enqueued: 40 | FRONT=0 REAR=3
Enqueued: 50 | FRONT=0 REAR=4
Circular Queue Overflow! Cannot enqueue 60
Circular Queue: 10 20 30 40 50 | Size=5/5
=== Dequeue 3 ===
Dequeued: 10 | FRONT=1 REAR=4
Dequeued: 20 | FRONT=2 REAR=4
Dequeued: 30 | FRONT=3 REAR=4
Circular Queue: 40 50 | Size=2/5
=== Enqueue 3 more (reuse freed slots!) ===
Enqueued: 60 | FRONT=3 REAR=0 <- REAR WRAPPED TO 0!
Enqueued: 70 | FRONT=3 REAR=1 <- REAR WRAPPED TO 1!
Enqueued: 80 | FRONT=3 REAR=2 <- REAR WRAPPED TO 2!
Circular Queue: 40 50 60 70 80 | Size=5/5
=== Overflow again ===
Circular Queue Overflow! Cannot enqueue 90
Simple vs Circular Queue Comparison
| Feature | Simple Queue | Circular Queue |
|---|---|---|
| Memory usage | Wastes freed slots | Reuses ALL slots |
| False overflow | YES — major problem | NO |
| REAR movement | Linear (0 to MAX-1) | Circular: (rear+1)%MAX |
| FRONT movement | Linear (0 to MAX-1) | Circular: (front+1)%MAX |
| Efficiency | Low | High |
| Complexity | Simple | Slightly more complex |
4.6.2 Priority Queue
A priority queue is a special queue where each element has a priority value. Elements with higher priority are dequeued before lower priority ones, regardless of insertion order.
Real-World Analogies
| Scenario | Priority Rule |
|---|---|
| Hospital ER | Critical patients (p=1) before minor cases (p=4) |
| CPU Scheduling | OS processes before user apps |
| Airline Boarding | First class before economy class |
| Dijkstra Algorithm | Process node with smallest distance first |
Types of Priority Queue
| Type | Higher Priority Means | Served First |
|---|---|---|
| Ascending PQ | Lower priority number | Smallest number |
| Descending PQ | Higher priority number | Largest number |
Priority Queue — Java Implementation
public class PriorityQueueCustom {
static class Element {
int data, priority;
Element(int data, int priority) {
this.data = data; this.priority = priority;
}
}
Element[] queue;
int size, max;
PriorityQueueCustom(int capacity) {
queue = new Element[capacity];
max = capacity; size = 0;
}
boolean isEmpty() { return size == 0; }
boolean isFull() { return size == max; }
// ENQUEUE: Insert in sorted position by priority (ascending)
void enqueue(int data, int priority) {
if (isFull()) { System.out.println("PQ Overflow!"); return; }
int i = size - 1;
while (i >= 0 && queue[i].priority > priority) {
queue[i + 1] = queue[i]; // Shift right
i--;
}
queue[i + 1] = new Element(data, priority);
size++;
System.out.println("Enqueued: data=" + data + " priority=" + priority);
}
// DEQUEUE: Remove from front (highest priority = lowest number)
Element dequeue() {
if (isEmpty()) { System.out.println("PQ Underflow!"); return null; }
Element item = queue[0];
for (int i = 0; i < size - 1; i++) queue[i] = queue[i + 1];
size--;
System.out.println("Dequeued: data=" + item.data +
" priority=" + item.priority);
return item;
}
void display() {
if (isEmpty()) { System.out.println("PQ empty"); return; }
System.out.print("PQ [high->low priority]: ");
for (int i = 0; i < size; i++)
System.out.print("[" + queue[i].data + ",p=" +
queue[i].priority + "] ");
System.out.println();
}
public static void main(String[] args) {
PriorityQueueCustom pq = new PriorityQueueCustom(6);
System.out.println("=== Inserting elements ===");
pq.enqueue(30, 3); // Inserted 1st
pq.enqueue(10, 1); // Highest priority
pq.enqueue(50, 5); // Lowest priority
pq.enqueue(20, 2);
pq.enqueue(40, 4);
pq.display();
System.out.println("\n=== Dequeuing by priority ===");
pq.dequeue(); // 10 (priority 1)
pq.dequeue(); // 20 (priority 2)
pq.dequeue(); // 30 (priority 3)
pq.display();
}
}
Output:
=== Inserting elements ===
Enqueued: data=30 priority=3
Enqueued: data=10 priority=1
Enqueued: data=50 priority=5
Enqueued: data=20 priority=2
Enqueued: data=40 priority=4
PQ [high->low priority]: [10,p=1] [20,p=2] [30,p=3] [40,p=4] [50,p=5]
=== Dequeuing by priority ===
Dequeued: data=10 priority=1
Dequeued: data=20 priority=2
Dequeued: data=30 priority=3
PQ [high->low priority]: [40,p=4] [50,p=5]
Built-in Java PriorityQueue
import java.util.PriorityQueue;
import java.util.Comparator;
public class JavaPQ {
static class Task {
String name; int priority;
Task(String n, int p) { name = n; priority = p; }
public String toString() { return "[" + name + ", p=" + priority + "]"; }
}
public static void main(String[] args) {
PriorityQueue<Task> pq = new PriorityQueue<>(
Comparator.comparingInt(t -> t.priority)
);
pq.offer(new Task("Task C", 3));
pq.offer(new Task("Task A", 1)); // Highest priority
pq.offer(new Task("Task E", 5));
pq.offer(new Task("Task B", 2));
pq.offer(new Task("Task D", 4));
System.out.println("Processing by priority:");
while (!pq.isEmpty()) System.out.println(" " + pq.poll());
}
}
Output:
Processing by priority:
[Task A, p=1]
[Task B, p=2]
[Task C, p=3]
[Task D, p=4]
[Task E, p=5]
Priority Queue Complexity
| Operation | Array-based | Heap-based (Built-in) |
|---|---|---|
| Enqueue | O(n) | O(log n) |
| Dequeue | O(1) | O(log n) |
| Peek | O(1) | O(1) |
4.7 Applications of Queue
4.7.1 CPU Process Scheduling (FCFS)
Processes wait in a ready queue and are dispatched to the CPU in FIFO order.
import java.util.LinkedList;
import java.util.Queue;
public class FCFSScheduling {
static class Process {
String pid; int burstTime;
Process(String pid, int bt) { this.pid = pid; this.burstTime = bt; }
}
public static void main(String[] args) {
Queue<Process> ready = new LinkedList<>();
ready.offer(new Process("P1", 4));
ready.offer(new Process("P2", 2));
ready.offer(new Process("P3", 6));
ready.offer(new Process("P4", 3));
int time = 0;
System.out.println("FCFS CPU Scheduling:");
while (!ready.isEmpty()) {
Process p = ready.poll();
System.out.printf("Time %2d: Running %-4s burst=%d, ends at %d%n",
time, p.pid, p.burstTime, time + p.burstTime);
time += p.burstTime;
}
System.out.println("Completed at time: " + time);
}
}
Output:
FCFS CPU Scheduling:
Time 0: Running P1 burst=4, ends at 4
Time 4: Running P2 burst=2, ends at 6
Time 6: Running P3 burst=6, ends at 12
Time 12: Running P4 burst=3, ends at 15
Completed at time: 15
4.7.2 BFS Graph Traversal
Explores graph level by level using a queue — exactly FIFO behavior.
import java.util.*;
public class BFSGraph {
static void bfs(List<List<Integer>> adj, int start, int n) {
boolean[] visited = new boolean[n];
Queue<Integer> queue = new LinkedList<>();
visited[start] = true;
queue.offer(start);
System.out.print("BFS Traversal: ");
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
for (int nb : adj.get(node)) {
if (!visited[nb]) { visited[nb] = true; queue.offer(nb); }
}
}
System.out.println();
}
public static void main(String[] args) {
int n = 6;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
int[][] edges = {{0,1},{0,2},{1,3},{1,4},{2,5}};
for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
bfs(adj, 0, n);
// Output: BFS Traversal: 0 1 2 3 4 5
}
}
4.7.3 Printer Spooling
Documents wait in queue; printer processes FIFO.
import java.util.LinkedList;
import java.util.Queue;
public class PrinterSpool {
public static void main(String[] args) {
Queue<String> spool = new LinkedList<>();
spool.offer("Report.pdf (Alice)");
spool.offer("Invoice.docx (Bob)");
spool.offer("Photo.png (Charlie)");
spool.offer("Slides.pptx (Diana)");
System.out.println("Printer Spooling:");
int job = 1;
while (!spool.isEmpty())
System.out.println("Job " + job++ + ": " + spool.poll());
}
}
Output:
Printer Spooling:
Job 1: Report.pdf (Alice)
Job 2: Invoice.docx (Bob)
Job 3: Photo.png (Charlie)
Job 4: Slides.pptx (Diana)
4.7.4 Level Order Tree Traversal
import java.util.*;
public class LevelOrder {
static class Node { int data; Node left, right; Node(int d){data=d;} }
static void levelOrder(Node root) {
if (root == null) return;
Queue<Node> q = new LinkedList<>();
q.offer(root);
System.out.print("Level Order: ");
while (!q.isEmpty()) {
Node n = q.poll();
System.out.print(n.data + " ");
if (n.left != null) q.offer(n.left);
if (n.right != null) q.offer(n.right);
}
}
public static void main(String[] args) {
// 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
Node root = new Node(1);
root.left=new Node(2); root.right=new Node(3);
root.left.left=new Node(4); root.left.right=new Node(5);
root.right.left=new Node(6); root.right.right=new Node(7);
levelOrder(root);
// Output: Level Order: 1 2 3 4 5 6 7
}
}
4.7.5 Other Applications
| Application | Queue Role |
|---|---|
| Round Robin Scheduling | Circular queue gives each process a time slice |
| Keyboard Buffer | Keystrokes queued in order typed |
| Network Packet Routing | Packets queued at routers, processed FIFO |
| Call Center Systems | Customer calls queued until agent free |
| Web Server Requests | HTTP requests queued and served in order |
| Semaphore Waiting | Processes waiting for resource queued |
Chapter Summary
UNIT IV: QUEUE — COMPLETE SUMMARY
=======================================================
Definition : Linear DS — FIFO (First In First Out)
FRONT : Points to first element (dequeue here)
REAR : Points to last element (enqueue here)
ENQUEUE : Insert at REAR | O(1)
DEQUEUE : Remove at FRONT | O(1)
Overflow : ENQUEUE on full (rear == MAX-1)
Underflow : DEQUEUE on empty (front == -1)
-------------------------------------------------------
Limitation of Simple Queue:
False Overflow : overflow even with free front slots
Memory Wastage : freed slots never reused
-------------------------------------------------------
Circular Queue:
rear = (rear+1)%MAX — wraps around, no waste
front = (front+1)%MAX
Full: count == MAX | Empty: count == 0
-------------------------------------------------------
Priority Queue:
Elements served by PRIORITY not arrival
Ascending PQ : lower number = higher priority
Enqueue O(n) | Dequeue O(1) (array-based)
-------------------------------------------------------
Applications:
1. CPU Scheduling (FCFS, Round Robin)
2. BFS Graph Traversal
3. Printer Spooling
4. Level Order Tree Traversal
5. Keyboard Buffer, Network Packets, Call Centers
-------------------------------------------------------
Complexity: Enqueue/Dequeue = O(1) (simple + circular)
PQ Enqueue=O(n), Dequeue=O(1) (array-based)
Space = O(n)
=======================================================
IMPORTANT QUESTIONS WITH ANSWERS
Section A: Short Answer (2-4 Marks)
Q1. Define queue and state its FIFO principle with a real example.
A queue is a linear data structure where insertions happen at the REAR and deletions happen at the FRONT, following the FIFO (First In, First Out) principle — the element inserted first is the first to be removed. Real example: people waiting in a bank line — the first person to arrive is the first to be served.
Q2. Define: ENQUEUE, DEQUEUE, OVERFLOW, UNDERFLOW.
ENQUEUE: Insert a new element at the REAR of the queue. Check for overflow first. DEQUEUE: Remove and return the element from the FRONT. Check for underflow first. OVERFLOW: Error when ENQUEUE is attempted on a full queue (REAR == MAX-1). UNDERFLOW: Error when DEQUEUE is attempted on an empty queue (FRONT == -1).
Q3. What are the limitations of a simple linear queue?
- False Overflow: Even when empty slots exist at the front (freed by dequeue), the queue reports overflow when REAR reaches MAX-1.
- Memory Wastage: Positions freed by dequeue() are permanently lost and can never be reused.
- Inefficiency: As FRONT moves forward, total usable memory shrinks permanently. Example: After 3 dequeues on a size-5 queue, indices 0,1,2 are free but inaccessible.
Q4. What is a circular queue? How does it solve memory wastage?
A circular queue uses modulo arithmetic to wrap REAR back to index 0 after reaching MAX-1: rear = (rear+1) % MAX. This allows all previously freed positions to be reused. After dequeuing elements from the front, new elements can occupy those freed slots when REAR wraps around. Result: no false overflow, no memory wastage.
Q5. What is a priority queue? Give two real examples.
A priority queue is a special queue where each element has a priority value. Elements are dequeued by priority, not arrival order. If priorities are equal, FIFO applies. Examples:
- Hospital ER: Critical patients (priority 1) treated before minor cases (priority 4).
- CPU Scheduling: High-priority OS processes run before low-priority user apps.
Section B: Long Answer (6-10 Marks)
Q6. Write ENQUEUE and DEQUEUE algorithms. Trace for: enqueue(5), enqueue(10), enqueue(15), dequeue(), enqueue(20), enqueue(25), dequeue(), dequeue() on MAX=5 queue.
Algorithms: (see sections 4.3 and 4.4 above)
| Operation | front | rear | Queue | Note |
|---|---|---|---|---|
| Initial | -1 | -1 | [_ _ _ _ _] | Empty |
| enqueue(5) | 0 | 0 | [5 _ _ _ _] | |
| enqueue(10) | 0 | 1 | [5 10 _ _ _] | |
| enqueue(15) | 0 | 2 | [5 10 15 _ _] | |
| dequeue()→5 | 1 | 2 | [_ 10 15 _ _] | |
| enqueue(20) | 1 | 3 | [_ 10 15 20 _] | |
| enqueue(25) | 1 | 4 | [_ 10 15 20 25] | |
| dequeue()→10 | 2 | 4 | [_ _ 15 20 25] | |
| dequeue()→15 | 3 | 4 | [_ _ _ 20 25] |
Q7. Explain circular queue with algorithm. Trace enqueue(A), enqueue(B), enqueue(C), dequeue(), dequeue(), enqueue(D), enqueue(E), enqueue(F) on MAX=4.
Using A=10,B=20,C=30,D=40,E=50,F=60:
| Operation | front | rear | [0][1][2][3] | Note |
|---|---|---|---|---|
| Initial | -1 | -1 | [][][][] | |
| enqueue(A) | 0 | 0 | [A][][][_] | |
| enqueue(B) | 0 | 1 | [A][B][][] | |
| enqueue(C) | 0 | 2 | [A][B][C][_] | |
| dequeue()→A | 1 | 2 | [][B][C][] | |
| dequeue()→B | 2 | 2 | [][][C][_] | |
| enqueue(D) | 2 | 3 | [][][C][D] | |
| enqueue(E) | 2 | 0 | [E][_][C][D] | rear wraps to 0! |
| enqueue(F) | 2 | 1 | [E][F][C][D] | rear wraps to 1! |
E and F reuse slots 0 and 1 freed by dequeuing A and B — demonstrating zero memory waste.
Q8. Evaluate postfix expression using queue: What is level-order traversal? Explain BFS using a queue.
Level-order traversal visits a binary tree node-by-node, level-by-level, using a queue:
- Enqueue the root.
- While queue is not empty: dequeue a node, visit it, enqueue its left and right children.
- Since FIFO, all level-d nodes are processed before level-(d+1) nodes.
For tree with root=1, children=2,3, grandchildren=4,5,6,7: Queue progression: [1] → dequeue 1, enqueue 2,3 → [2,3] → dequeue 2, enqueue 4,5 → [3,4,5] → ... Output: 1 2 3 4 5 6 7 (level by level)
Practical Questions
Practical 1: Complete Queue with all operations
public class QueuePractical {
int[] queue; int front, rear, max;
QueuePractical(int size) {
queue = new int[size]; max = size; front = -1; rear = -1;
}
void enqueue(int item) {
if (rear == max-1) { System.out.println("OVERFLOW"); return; }
if (front == -1) front = 0;
queue[++rear] = item;
System.out.println("Enqueued: " + item);
}
int dequeue() {
if (front == -1) { System.out.println("UNDERFLOW"); return -1; }
int item = queue[front];
if (front == rear) { front = -1; rear = -1; }
else front++;
System.out.println("Dequeued: " + item);
return item;
}
void display() {
if (front == -1) { System.out.println("Queue Empty"); return; }
System.out.print("Queue: ");
for (int i = front; i <= rear; i++) System.out.print(queue[i] + " ");
System.out.println("[size=" + (rear-front+1) + "]");
}
public static void main(String[] args) {
QueuePractical q = new QueuePractical(4);
q.enqueue(100); q.enqueue(200);
q.enqueue(300); q.enqueue(400);
q.enqueue(500); // OVERFLOW
q.display();
q.dequeue(); q.dequeue();
q.display();
q.dequeue(); q.dequeue();
q.dequeue(); // UNDERFLOW
}
}
Output:
Enqueued: 100
Enqueued: 200
Enqueued: 300
Enqueued: 400
OVERFLOW
Queue: 100 200 300 400 [size=4]
Dequeued: 100
Dequeued: 200
Queue: 300 400 [size=2]
Dequeued: 300
Dequeued: 400
UNDERFLOW
Practical 2: Circular Queue with wrap-around demonstration
public class CQPractical {
int[] q; int front, rear, max, count;
CQPractical(int size) {
q = new int[size]; max = size; front=-1; rear=-1; count=0;
}
void enqueue(int item) {
if (count == max) { System.out.println("CQ Overflow!"); return; }
if (front == -1) { front=0; rear=0; } else rear = (rear+1)%max;
q[rear]=item; count++;
System.out.printf("Enqueued: %-4d front=%d rear=%d%n", item, front, rear);
}
void dequeue() {
if (count == 0) { System.out.println("CQ Underflow!"); return; }
System.out.printf("Dequeued: %-4d ", q[front]);
count--;
if (count == 0) { front=-1; rear=-1; }
else front = (front+1)%max;
System.out.printf("front=%d rear=%d%n", front, rear);
}
void display() {
System.out.print("CQ: ");
if (count == 0) { System.out.println("EMPTY"); return; }
int i = front;
for (int k=0; k<count; k++) { System.out.print(q[i]+" "); i=(i+1)%max; }
System.out.println("["+count+"/"+max+"]");
}
public static void main(String[] args) {
CQPractical cq = new CQPractical(4);
cq.enqueue(10); cq.enqueue(20); cq.enqueue(30); cq.enqueue(40);
cq.display();
cq.dequeue(); cq.dequeue();
cq.display();
cq.enqueue(50); // rear wraps to 0
cq.enqueue(60); // rear wraps to 1
cq.display();
cq.enqueue(70); // OVERFLOW
}
}
Practical 3: Emergency Room Priority Queue
import java.util.PriorityQueue;
import java.util.Comparator;
public class EmergencyRoom {
static class Patient {
String name; int severity;
Patient(String n, int s) { name=n; severity=s; }
String label() {
return severity==1?"CRITICAL":severity==2?"SERIOUS":
severity==3?"MODERATE":"MINOR";
}
}
public static void main(String[] args) {
PriorityQueue<Patient> er = new PriorityQueue<>(
Comparator.comparingInt(p -> p.severity)
);
er.offer(new Patient("Alice", 3));
er.offer(new Patient("Bob", 1)); // Critical
er.offer(new Patient("Carol", 4));
er.offer(new Patient("David", 2));
er.offer(new Patient("Eve", 1)); // Critical
System.out.println("Treating patients:");
int i=1;
while (!er.isEmpty()) {
Patient p = er.poll();
System.out.printf("#%d %-8s [%s]%n", i++, p.name, p.label());
}
}
}
Output:
Treating patients:
#1 Bob [CRITICAL]
#2 Eve [CRITICAL]
#3 David [SERIOUS]
#4 Alice [MODERATE]
#5 Carol [MINOR]
Practical 4: Round Robin Scheduling using Circular Queue
import java.util.LinkedList;
import java.util.Queue;
public class RoundRobin {
static class Process {
String pid; int remaining;
Process(String pid, int bt) { this.pid=pid; this.remaining=bt; }
}
public static void main(String[] args) {
Queue<Process> ready = new LinkedList<>();
ready.offer(new Process("P1", 8));
ready.offer(new Process("P2", 4));
ready.offer(new Process("P3", 6));
ready.offer(new Process("P4", 3));
int quantum = 3, time = 0;
System.out.println("Round Robin (Quantum=" + quantum + "):");
while (!ready.isEmpty()) {
Process p = ready.poll();
int exec = Math.min(p.remaining, quantum);
System.out.printf("Time %2d-%2d: %-4s runs %d units | left=%d%n",
time, time+exec, p.pid, exec, p.remaining-exec);
time += exec;
p.remaining -= exec;
if (p.remaining > 0) ready.offer(p);
else System.out.println(" " + p.pid + " DONE at " + time);
}
System.out.println("Total time: " + time);
}
}
Output:
Round Robin (Quantum=3):
Time 0- 3: P1 runs 3 units | left=5
Time 3- 6: P2 runs 3 units | left=1
Time 6- 9: P3 runs 3 units | left=3
Time 9-12: P4 runs 3 units | left=0
P4 DONE at 12
Time 12-15: P1 runs 3 units | left=2
Time 15-16: P2 runs 1 units | left=0
P2 DONE at 16
Time 16-19: P3 runs 3 units | left=0
P3 DONE at 19
Time 19-21: P1 runs 2 units | left=0
P1 DONE at 21
Total time: 21
Practical 5: Interleave first and second halves of queue
import java.util.*;
public class InterleaveQueue {
static void interleave(Queue<Integer> queue) {
int half = queue.size() / 2;
Stack<Integer> stack = new Stack<>();
// Push first half onto stack
for (int i = 0; i < half; i++) stack.push(queue.poll());
// Enqueue first half back
while (!stack.isEmpty()) queue.offer(stack.pop());
// Move first half to back
for (int i = 0; i < half; i++) queue.offer(queue.poll());
// Push first half to stack again
for (int i = 0; i < half; i++) stack.push(queue.poll());
// Interleave
while (!stack.isEmpty()) {
queue.offer(stack.pop());
queue.offer(queue.poll());
}
}
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= 8; i++) q.offer(i);
System.out.println("Original: " + q);
interleave(q);
System.out.println("Interleaved: " + q);
// Original: [1, 2, 3, 4, 5, 6, 7, 8]
// Interleaved: [1, 5, 2, 6, 3, 7, 4, 8]
}
}
Possible Exam Questions Table
| # | Question | Marks |
|---|---|---|
| 1 | Define queue and FIFO with example | 2 |
| 2 | List all queue terminology with definitions | 4 |
| 3 | Write ENQUEUE and DEQUEUE algorithms | 5 |
| 4 | Implement complete queue in Java | 8 |
| 5 | What is false overflow? What causes it? | 3 |
| 6 | Explain limitations of simple queue | 4 |
| 7 | What is circular queue? How does it solve memory wastage? | 5 |
| 8 | Write circular queue ENQUEUE/DEQUEUE algorithms | 6 |
| 9 | Trace circular queue operations with wrap-around | 8 |
| 10 | Define priority queue with two real-life examples | 4 |
| 11 | Compare simple, circular, and priority queue | 6 |
| 12 | Write Java program for circular queue | 10 |
| 13 | Write Java program for priority queue | 8 |
| 14 | Explain 3 applications of queue | 6 |
| 15 | Explain BFS using queue with diagram | 6 |
| 16 | Differentiate between queue and stack | 4 |
| 17 | Explain round-robin scheduling using circular queue | 5 |
End of Unit IV — Queue Complete Notes | All Programs in Java | Algorithms | Traces | Q&A Prepared for: BCA / BIT / MCA / BSc.CSIT | Subject: Data Structures and Algorithms