Queue ADT – Data Structures & Algorithms | Simple Queue, Circular Queue & Circular Deque

Queue ADT — Data Structures & Algorithms


Queue ADT
Data Structures & Algorithms
8 Sections Covered · 3 Queue Types · 4 Implementations · Complexity Analysis




1 Queue ADT (Abstract Data Type)

1.1 Formal Definition
A Queue ADT is a linear abstract data type in which elements are inserted at one end (rear) and removed from
another end (front) following the FIFO (First In First Out) principle.


ADT Representation

Queue ADT = {
Data: Ordered collection of elements
Operations:
enqueue(x) → Insert element x at rear
dequeue() → Remove element from front
front() → Return front element
isEmpty() → Check if queue is empty
isFull() → Check if queue is full (array)
}




1.2 Characteristics
• FIFO ordering
• Restricted access (only front & rear)
• Dynamic or static implementation
• Widely used in scheduling systems


1.3 Real-Life Applications
• CPU Scheduling (FCFS(First-Come, First-Served)
• Printer Spooling
• Call Center Systems
• Breadth First Search (BFS)
• I/O Buffers



2 Types of Queue

2.1 Simple (Linear) Queue
▸ Insertion: Rear
▸ Deletion: Front

, Queue ADT — Data Structures & Algorithms
▸ Problem: Memory wastage — deleted front spaces cannot be reused


Example

Initial: [ _ _ _ _ _ ]
Insert: [10 20 30 _ _ ]
Delete: [ _ 20 30 _ _ ] ← front space wasted




2.2 Circular Queue
Circular Queue connects the last index back to the first index, allowing empty spaces to be reused.


Key Formulas
rear = (rear + 1) % SIZE
front = (front + 1) % SIZE

Full Condition: (rear + 1) % SIZE == front




Advantages
• No memory wastage
• Efficient space utilization
• Suitable for buffers


2.3 Double Ended Queue (Deque)
Deque allows insertion and deletion from both ends.


Type Insert Delete

Input Restricted Deque Only Rear Both Ends

Output Restricted Deque Both Ends Only Front




3 Array Implementation of Queue