Chapter: Queue Data Structure
1. Concept and Definition
A queue is a linear data structure that stores elements in a specific order called FIFO
(First-In-First-Out). The element that is inserted first will be the first one to be removed.
Elements are added at one end (rear) and removed from the other end (front).
Real-World Analogies
Think of a queue like:
• Queue at a ticket counter: The first person in line is served first
• Printer queue: Documents are printed in the order they were sent
• Waiting line at a restaurant: First customer to arrive is seated first
• CPU task scheduling: Processes are executed in the order they arrive
Visual Representation
ENQUEUE (Insert) DEQUEUE (Remove)
↓ ↓
┌─────────┬─────────┬─────────┬─────────┐
┌─────────┬─────────┬─────────┬─────────┐
│ 10 │ 20 │ 30 │ 40 │ │ 10 │ 20 │ 30 │ 40
│
└─────────┴─────────┴─────────┴─────────┘
└─────────┴─────────┴─────────┴─────────┘
↑ ↑ ↑ ↑
FRONT REAR FRONT
REAR
(Remove here) (Add here) (Removed: 10) (Add
here)
Elements flow: FRONT ←←←←←←←←←←←←←←←←←←←←← REAR
First In (10) ────────────────────────────→ First Out (10)
Key Characteristics
Property Description
Access Points Two ends: FRONT and REAR
Insertion Only at REAR (Enqueue)
Deletion Only from FRONT (Dequeue)
Order FIFO (First-In-First-Out)
Types of Queues
Type Description
Simple Queue Basic FIFO queue with front and rear pointers
Circular Queue Rear connects back to front, efficient space usage
Priority Queue Elements dequeued based on priority, not arrival order
Double-Ended Insert/delete from both ends (Deque)
2. Queue Operations
Overview of All Operations
Operation Description Time Space
Enqueue Add element at rear O(1) O(1)
Dequeue Remove element from front O(1) O(1)
Peek/Front View front element O(1) O(1)
IsEmpty Check if queue is empty O(1) O(1)
IsFull Check if queue is full O(1) O(1)
Count Get number of elements O(1) O(1)
Display Show all elements O(n) O(1)
3. Each Operation Explained with Numerical Examples
3.1 ENQUEUE Operation
Definition:
Adds a new element to the rear (back) of the queue.
Algorithm:
ENQUEUE(queue, element):
1. Check if queue is full
2. If full, display "Queue Overflow" and exit
3. If queue is empty (first element):
a. Set front = 0
4. Increment rear by 1
5. Place element at position rear
6. End
C# Implementation:
public void Enqueue(int item)
{
// Step 1: Check if queue is full
if (IsFull())
{
[Link]("Queue Overflow! Cannot enqueue " + item);
return;
}
// Step 2: If first element, set front to 0
if (front == -1)
{
front = 0;
}
// Step 3: Increment rear and add element
rear = rear + 1;
items[rear] = item;
[Link]("Enqueued: " + item);
}
Trace Example:
Operation: Enqueue(10)
Before: front = -1, rear = -1
Step 1: front = 0 (first element)
Step 2: rear = -1 + 1 = 0
Step 3: items[0] = 10
After: front = 0, rear = 0, items = [10, _, _]
Operation: Enqueue(20)
Before: front = 0, rear = 0
Step 1: rear = 0 + 1 = 1
Step 2: items[1] = 20
After: front = 0, rear = 1, items = [10, 20, _]
Operation: Enqueue(30)
Before: front = 0, rear = 1
Step 1: rear = 1 + 1 = 2
Step 2: items[2] = 30
After: front = 0, rear = 2, items = [10, 20, 30]
3.2 DEQUEUE Operation
Definition:
Removes and returns the element from the front of the queue.
Algorithm:
DEQUEUE(queue):
1. Check if queue is empty
2. If empty, display "Queue Underflow" and exit
3. Store element at front position
4. If front equals rear (last element):
a. Reset front = -1 and rear = -1
5. Else:
a. Increment front by 1
6. Return the stored element
7. End
Numerical Example:
Initial Queue: After Dequeue(): After Dequeue(): After
Dequeue():
front=0, rear=2 front=1, rear=2 front=2, rear=2 front=-1,
rear=-1
Returns: 10 Returns: 20 Returns:
30
┌─────┬─────┬─────┐ ┌─────┬─────┬─────┐ ┌─────┬─────┬─────┐
┌─────┬─────┬─────┐
│ 10 │ 20 │ 30 │ │ │ 20 │ 30 │ │ │ │ 30 │ │ │
│ │
└─────┴─────┴─────┘ └─────┴─────┴─────┘ └─────┴─────┴─────┘
└─────┴─────┴─────┘
[0] [1] [2] [0] [1] [2] [0] [1] [2] [0] [1]
[2]
↑ ↑ ↑ ↑ ↑
front rear front rear front/rear EMPTY
C# Implementation:
public int Dequeue()
{
// Step 1: Check if queue is empty
if (IsEmpty())
{
[Link]("Queue Underflow! Queue is empty");
return -1;
}
// Step 2: Store the front element
int item = items[front];
// Step 3: Check if this is the last element
if (front == rear)
{
// Reset queue to empty state
front = -1;
rear = -1;
}
else
{
// Move front forward
front = front + 1;
}
[Link]("Dequeued: " + item);
return item;
}
Trace Example:
Queue: [10, 20, 30], front = 0, rear = 2
Operation: Dequeue()
Before: front = 0, rear = 2
Step 1: item = items[0] = 10
Step 2: front != rear, so front = 0 + 1 = 1
Return: 10
After: front = 1, rear = 2, items = [_, 20, 30]
Operation: Dequeue()
Before: front = 1, rear = 2
Step 1: item = items[1] = 20
Step 2: front != rear, so front = 1 + 1 = 2
Return: 20
After: front = 2, rear = 2, items = [_, _, 30]
Operation: Dequeue()
Before: front = 2, rear = 2
Step 1: item = items[2] = 30
Step 2: front == rear, so front = -1, rear = -1 (reset)
Return: 30
After: front = -1, rear = -1, items = [_, _, _] (empty)
3.3 PEEK (Front) Operation
Definition:
Returns the front element without removing it from the queue.
Algorithm:
PEEK(queue):
1. Check if queue is empty
2. If empty, display "Queue is empty" and exit
3. Return element at front position (without removing)
4. End
Numerical Example:
Queue State: After PEEK():
front = 0, rear = 2 front = 0, rear = 2 (unchanged)
Returns: 10
┌─────┬─────┬─────┐ ┌─────┬─────┬─────┐
│ 10 │ 20 │ 30 │ │ 10 │ 20 │ 30 │
└─────┴─────┴─────┘ └─────┴─────┴─────┘
↑ ↑ ↑ ↑
front rear front rear
(still here)
Note: Unlike Dequeue(), the element remains in the queue
C# Implementation:
public int Peek()
{
// Step 1: Check if queue is empty
if (IsEmpty())
{
[Link]("Queue is empty! Nothing to peek");
return -1;
}
// Step 2: Return front element (do NOT modify front)
return items[front];
}
Comparison: Peek vs Dequeue:
Queue: [10, 20, 30], front = 0, rear = 2
After Peek():
Returns: 10
Queue remains: [10, 20, 30], front = 0, rear = 2
After Dequeue():
Returns: 10
Queue becomes: [20, 30], front = 1, rear = 2
3.4 IsEmpty Operation
Definition:
Checks whether the queue contains any elements.
Algorithm:
IsEmpty(queue):
1. If front equals -1, return TRUE
2. Otherwise, return FALSE
3. End
Numerical Example:
Case 1: Empty Queue Case 2: Non-Empty Queue
front = -1, rear = -1 front = 0, rear = 2
┌─────┬─────┬─────┐ ┌─────┬─────┬─────┐
│ │ │ │ │ 10 │ 20 │ 30 │
└─────┴─────┴─────┘ └─────┴─────┴─────┘
↑ ↑
front rear
IsEmpty() = TRUE IsEmpty() = FALSE
C# Implementation:
public bool IsEmpty()
{
// Return true if front is -1 (no elements)
return front == -1;
}
3.5 IsFull Operation
Definition:
Checks whether the queue has reached its maximum capacity.
Algorithm:
IsFull(queue):
1. If rear equals (capacity - 1), return TRUE
2. Otherwise, return FALSE
3. End
Numerical Example:
Capacity = 3
Case 1: Full Queue Case 2: Not Full Queue
front = 0, rear = 2 front = 0, rear = 1
┌─────┬─────┬─────┐ ┌─────┬─────┬─────┐
│ 10 │ 20 │ 30 │ │ 10 │ 20 │ │
└─────┴─────┴─────┘ └─────┴─────┴─────┘
[0] [1] [2] [0] [1] [2]
↑ ↑ ↑ ↑
front rear front rear
rear (2) == capacity-1 (2) rear (1) != capacity-1 (2)
IsFull() = TRUE IsFull() = FALSE
C# Implementation:
public bool IsFull()
{
// Return true if rear has reached last index
return rear == capacity - 1;
}
3.6 Count Operation
Definition:
Returns the number of elements currently in the queue.
Algorithm:
Count(queue):
1. If queue is empty, return 0
2. Otherwise, return (rear - front + 1)
3. End
Numerical Example:
Case 1: Case 2: Case 3:
front=-1, rear=-1 front=0, rear=1 front=1, rear=2
┌─────┬─────┬─────┐ ┌─────┬─────┬─────┐ ┌─────┬─────┬─────┐
│ │ │ │ │ 10 │ 20 │ │ │ │ 20 │ 30 │
└─────┴─────┴─────┘ └─────┴─────┴─────┘ └─────┴─────┴─────┘
↑ ↑ ↑ ↑
front rear front rear
Count = 0 (empty) Count = 1-0+1 = 2 Count = 2-1+1 = 2
C# Implementation:
public int Count()
{
if (IsEmpty())
{
return 0;
}
return rear - front + 1;
}
3.7 Display Operation
Definition:
Shows all elements in the queue from front to rear.
Algorithm:
Display(queue):
1. Check if queue is empty
2. If empty, display "Queue is empty" and exit
3. For i = front to rear:
a. Print items[i]
4. End
Numerical Example:
Queue: front = 0, rear = 2
┌─────┬─────┬─────┐
│ 10 │ 20 │ 30 │
└─────┴─────┴─────┘
[0] [1] [2]
↑ ↑
front rear
Display traversal:
i = 0: Print items[0] = 10
i = 1: Print items[1] = 20
i = 2: Print items[2] = 30
Output: "Queue (front to rear): 10 20 30"
C# Implementation:
public void Display()
{
// Step 1: Check if empty
if (IsEmpty())
{
[Link]("Queue is empty");
return;
}
// Step 2: Print from front to rear
[Link]("Queue (front to rear): ");
for (int i = front; i <= rear; i++)
{
[Link](items[i] + " ");
}
[Link]();
}
4. Complete Queue Implementation
4.1 Array-Based Queue (Full Code)
using System;
public class Queue
{
// Private members
private int[] items; // Array to store elements
private int front; // Index of front element
private int rear; // Index of rear element
private int capacity; // Maximum size of queue
// Constructor
public Queue(int size)
{
capacity = size;
items = new int[capacity];
front = -1; // -1 indicates empty queue
rear = -1;
}
// ENQUEUE: Add element at rear
public void Enqueue(int item)
{
if (IsFull())
{
[Link]("Queue Overflow!");
return;
}
if (front == -1) front = 0;
rear = rear + 1;
items[rear] = item;
[Link]("Enqueued: " + item);
}
// DEQUEUE: Remove and return front element
public int Dequeue()
{
if (IsEmpty())
{
[Link]("Queue Underflow!");
return -1;
}
int item = items[front];
if (front == rear)
{
front = -1;
rear = -1;
}
else
{
front = front + 1;
}
[Link]("Dequeued: " + item);
return item;
}
// PEEK: View front element
public int Peek()
{
if (IsEmpty())
{
[Link]("Queue is empty!");
return -1;
}
return items[front];
}
// IsEmpty: Check if queue has no elements
public bool IsEmpty()
{
return front == -1;
}
// IsFull: Check if queue is at capacity
public bool IsFull()
{
return rear == capacity - 1;
}
// Count: Get number of elements
public int Count()
{
if (IsEmpty()) return 0;
return rear - front + 1;
}
// Display: Show all elements
public void Display()
{
if (IsEmpty())
{
[Link]("Queue is empty");
return;
}
[Link]("Queue (front to rear): ");
for (int i = front; i <= rear; i++)
{
[Link](items[i] + " ");
}
[Link]();
}
}
4.2 Linked List-Based Queue (Full Code)
using System;
// Node class for linked list
public class Node
{
public int Data; // Stores the value
public Node Next; // Points to next node
public Node(int data)
{
Data = data;
Next = null;
}
}
// Queue using Linked List
public class LinkedQueue
{
private Node front; // Points to front node
private Node rear; // Points to rear node
private int count; // Number of elements
// Constructor
public LinkedQueue()
{
front = null;
rear = null;
count = 0;
}
// ENQUEUE: Add element at rear
public void Enqueue(int item)
{
Node newNode = new Node(item);
if (IsEmpty())
{
// First element
front = newNode;
rear = newNode;
}
else
{
// Add at rear
[Link] = newNode;
rear = newNode;
}
count++;
[Link]("Enqueued: " + item);
}
// DEQUEUE: Remove and return front element
public int Dequeue()
{
if (IsEmpty())
{
[Link]("Queue Underflow!");
return -1;
}
int item = [Link];
front = [Link];
// If queue becomes empty
if (front == null)
{
rear = null;
}
count--;
[Link]("Dequeued: " + item);
return item;
}
// PEEK: View front element
public int Peek()
{
if (IsEmpty())
{
[Link]("Queue is empty!");
return -1;
}
return [Link];
}
// IsEmpty
public bool IsEmpty()
{
return front == null;
}
// Count
public int Count()
{
return count;
}
// Display
public void Display()
{
if (IsEmpty())
{
[Link]("Queue is empty");
return;
}
[Link]("Queue (front to rear): ");
Node current = front;
while (current != null)
{
[Link]([Link] + " ");
current = [Link];
}
[Link]();
}
}
Visual Representation of Linked Queue:
After Enqueue(10), Enqueue(20), Enqueue(30):
front rear
↓ ↓
┌──────┬───┐ ┌──────┬───┐ ┌──────┬──────┐
│ 10 │ ●─┼───→│ 20 │ ●─┼───→│ 30 │ null │
└──────┴───┘ └──────┴───┘ └──────┴──────┘
After Dequeue():
Returns: 10
front rear
↓ ↓
┌──────┬───┐ ┌──────┬──────┐
│ 20 │ ●─┼───→│ 30 │ null │
└──────┴───┘ └──────┴──────┘
5. Circular Queue
5.1 Concept
A circular queue overcomes the limitation of simple queue where space is wasted after
dequeue operations. In circular queue, the rear wraps around to the beginning when it
reaches the end.
Problem with Simple Queue:
After multiple Enqueue and Dequeue operations:
┌─────┬─────┬─────┬─────┬─────┐
│ │ │ 30 │ 40 │ 50 │
└─────┴─────┴─────┴─────┴─────┘
[0] [1] [2] [3] [4]
↑ ↑
front rear
Positions [0] and [1] are wasted even though they are empty!
IsFull() returns TRUE because rear == capacity-1
Solution: Circular Queue - rear wraps to position [0]
Circular Queue Visualization:
┌─────┐
│ 0 │
┌──┴─────┴──┐
│ │
┌──┤ 4 ├──┐
│ │ │ │
│ 1│ │3 │
│ │ 2 │ │
└──┴───────────┴──┘
Rear connects back to Front
Next position = (current + 1) % capacity
5.2 Circular Queue Implementation
using System;
public class CircularQueue
{
private int[] items;
private int front;
private int rear;
private int capacity;
private int count;
public CircularQueue(int size)
{
capacity = size;
items = new int[capacity];
front = -1;
rear = -1;
count = 0;
}
// ENQUEUE with circular wrap-around
public void Enqueue(int item)
{
if (IsFull())
{
[Link]("Queue Overflow!");
return;
}
if (front == -1) front = 0;
// Circular increment: wrap around using modulo
rear = (rear + 1) % capacity;
items[rear] = item;
count++;
[Link]("Enqueued: " + item);
}
// DEQUEUE with circular wrap-around
public int Dequeue()
{
if (IsEmpty())
{
[Link]("Queue Underflow!");
return -1;
}
int item = items[front];
if (front == rear)
{
// Last element
front = -1;
rear = -1;
}
else
{
// Circular increment
front = (front + 1) % capacity;
}
count--;
[Link]("Dequeued: " + item);
return item;
}
public bool IsEmpty() { return front == -1; }
public bool IsFull() { return count == capacity; }
public int Count() { return count; }
public void Display()
{
if (IsEmpty())
{
[Link]("Queue is empty");
return;
}
[Link]("Circular Queue: ");
int i = front;
int printed = 0;
while (printed < count)
{
[Link](items[i] + " ");
i = (i + 1) % capacity;
printed++;
}
[Link]();
}
}
5.3 Circular Queue Numerical Example
Capacity = 5
Step 1: Enqueue(10), Enqueue(20), Enqueue(30), Enqueue(40), Enqueue(50)
┌─────┬─────┬─────┬─────┬─────┐
│ 10 │ 20 │ 30 │ 40 │ 50 │
└─────┴─────┴─────┴─────┴─────┘
[0] [1] [2] [3] [4]
↑ ↑
front rear
count = 5, IsFull = TRUE
Step 2: Dequeue() twice - removes 10 and 20
┌─────┬─────┬─────┬─────┬─────┐
│ │ │ 30 │ 40 │ 50 │
└─────┴─────┴─────┴─────┴─────┘
[0] [1] [2] [3] [4]
↑ ↑
front rear
count = 3, IsFull = FALSE
Step 3: Enqueue(60) - wraps around to position [0]
rear = (4 + 1) % 5 = 0
┌─────┬─────┬─────┬─────┬─────┐
│ 60 │ │ 30 │ 40 │ 50 │
└─────┴─────┴─────┴─────┴─────┘
[0] [1] [2] [3] [4]
↑ ↑
rear front
count = 4
Step 4: Enqueue(70) - continues at position [1]
rear = (0 + 1) % 5 = 1
┌─────┬─────┬─────┬─────┬─────┐
│ 60 │ 70 │ 30 │ 40 │ 50 │
└─────┴─────┴─────┴─────┴─────┘
[0] [1] [2] [3] [4]
↑ ↑
rear front
count = 5, IsFull = TRUE
6. Queue Applications
6.1 Common Applications
Application Description
CPU Scheduling Processes wait in queue for CPU time (Round Robin)
Printer Spooling Print jobs queued in order of submission
BFS Algorithm Breadth-First Search uses queue for traversal
Call Center Customers served in order they called
Buffer/Streaming Data buffered in queue for streaming media
Keyboard Buffer Keystrokes stored in order pressed
6.2 Example: Simulating a Print Queue
using System;
using [Link];
class PrinterQueue
{
static void Main()
{
Queue<string> printQueue = new Queue<string>();
// Add print jobs
[Link]("[Link]");
[Link]("[Link]");
[Link]("[Link]");
[Link]("[Link]");
[Link]("Print Queue: " + [Link] + " jobs");
// Process print jobs (FIFO order)
while ([Link] > 0)
{
string job = [Link]();
[Link]("Printing: " + job);
}
[Link]("All jobs completed!");
}
}
// Output:
// Print Queue: 4 jobs
// Printing: [Link]
// Printing: [Link]
// Printing: [Link]
// Printing: [Link]
// All jobs completed!
6.3 Example: Level Order Traversal of Binary Tree
// Using queue to traverse a binary tree level by level
public class TreeNode
{
public int Data;
public TreeNode Left, Right;
public TreeNode(int data)
{
Data = data;
Left = Right = null;
}
}
public static void LevelOrderTraversal(TreeNode root)
{
if (root == null) return;
Queue<TreeNode> queue = new Queue<TreeNode>();
[Link](root);
[Link]("Level Order: ");
while ([Link] > 0)
{
TreeNode current = [Link]();
[Link]([Link] + " ");
// Add children to queue
if ([Link] != null)
[Link]([Link]);
if ([Link] != null)
[Link]([Link]);
}
}
// Tree: 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
//
// Output: Level Order: 1 2 3 4 5 6 7
7. Complete Demo Program
using System;
using [Link];
class Program
{
static void Main()
{
[Link]("=== QUEUE DEMONSTRATION ===");
[Link]();
// 1. Basic Operations Demo
[Link]("--- Basic Queue Operations ---");
Queue<int> queue = new Queue<int>();
// Enqueue operations
[Link](10);
[Link]("Enqueued: 10");
[Link](20);
[Link]("Enqueued: 20");
[Link](30);
[Link]("Enqueued: 30");
[Link](40);
[Link]("Enqueued: 40");
[Link]("Queue: [" + [Link](", ", queue) + "]");
[Link]("Count: " + [Link]);
// Peek
[Link]("Peek (front): " + [Link]());
// Dequeue
[Link]("Dequeue: " + [Link]());
[Link]("Dequeue: " + [Link]());
[Link]("Queue after dequeues: [" +
[Link](", ", queue) + "]");
// 2. Custom Queue Demo
[Link]();
[Link]("--- Custom Array Queue ---");
ArrayQueue customQueue = new ArrayQueue(5);
[Link](100);
[Link](200);
[Link](300);
[Link]();
[Link]("Peek: " + [Link]());
[Link]();
[Link]();
// 3. Circular Queue Demo
[Link]();
[Link]("--- Circular Queue Demo ---");
CircularQueueDemo();
}
static void CircularQueueDemo()
{
CircularQueue cq = new CircularQueue(4);
[Link](1);
[Link](2);
[Link](3);
[Link](4);
[Link](); // 1 2 3 4
[Link](); // Remove 1
[Link](); // Remove 2
[Link](); // 3 4
[Link](5); // Wraps to position 0
[Link](6); // Wraps to position 1
[Link](); // 3 4 5 6
}
}
8. Program Output
=== QUEUE DEMONSTRATION ===
--- Basic Queue Operations ---
Enqueued: 10
Enqueued: 20
Enqueued: 30
Enqueued: 40
Queue: [10, 20, 30, 40]
Count: 4
Peek (front): 10
Dequeue: 10
Dequeue: 20
Queue after dequeues: [30, 40]
--- Custom Array Queue ---
Enqueued: 100
Enqueued: 200
Enqueued: 300
Queue (front to rear): 100 200 300
Peek: 100
Dequeued: 100
Queue (front to rear): 200 300
--- Circular Queue Demo ---
Enqueued: 1
Enqueued: 2
Enqueued: 3
Enqueued: 4
Circular Queue: 1 2 3 4
Dequeued: 1
Dequeued: 2
Circular Queue: 3 4
Enqueued: 5
Enqueued: 6
Circular Queue: 3 4 5 6
9. Stack vs Queue Comparison
Feature Stack Queue
Order LIFO (Last-In-First-Out) FIFO (First-In-First-Out)
Insert Push (at top) Enqueue (at rear)
Delete Pop (from top) Dequeue (from front)
Access Point One end (top) Two ends (front, rear)
View Peek (top element) Front (front element)
Use Case Undo, recursion, parsing Scheduling, BFS, buffers
10. Summary Table
Topic Key Points
Definition FIFO structure - First In, First Out
Enqueue Add at rear, O(1), increment rear then insert
Dequeue Remove from front, O(1), return then increment front
Peek View front without removing, O(1)
IsEmpty Check if front == -1
IsFull Check if rear == capacity - 1
Circular Queue Uses modulo for wrap-around, no wasted space
Applications CPU scheduling, BFS, printer queue, buffers
— End of Chapter —