Master Queues: Linear, Circular, Priority & Deque

Master Queue Data Structures

From basic FIFO queues to advanced priority queues and deques. Learn implementations, applications, and master interview questions with comprehensive examples.

Complete Queue Implementation in Python

# Linear Queue Implementation
class LinearQueue:
    def __init__(self, capacity):
        self.queue = [None] * capacity
        self.capacity = capacity
        self.front = self.rear = -1
    
    def enqueue(self, item):
        if self.rear == self.capacity - 1:
            raise Exception("Queue Overflow")
        if self.front == -1:
            self.front = 0
        self.rear += 1
        self.queue[self.rear] = item
        return f"Enqueued: {item}"
    
    def dequeue(self):
        if self.front == -1:
            raise Exception("Queue Underflow")
        item = self.queue[self.front]
        if self.front == self.rear:
            self.front = self.rear = -1
        else:
            self.front += 1
        return f"Dequeued: {item}"

# Circular Queue Implementation
class CircularQueue:
    def __init__(self, capacity):
        self.queue = [None] * capacity
        self.capacity = capacity
        self.front = self.rear = -1
    
    def enqueue(self, item):
        if (self.rear + 1) % self.capacity == self.front:
            raise Exception("Circular Queue Overflow")
        if self.front == -1:
            self.front = 0
        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = item
    
    def dequeue(self):
        if self.front == -1:
            raise Exception("Circular Queue Underflow")
        item = self.queue[self.front]
        if self.front == self.rear:
            self.front = self.rear = -1
        else:
            self.front = (self.front + 1) % self.capacity
        return item

# Priority Queue using heapq
import heapq

class PriorityQueue:
    def __init__(self):
        self.heap = []
    
    def push(self, item, priority):
        heapq.heappush(self.heap, (priority, item))
    
    def pop(self):
        if not self.heap:
            raise Exception("Priority Queue Empty")
        return heapq.heappop(self.heap)[1]
    
    def peek(self):
        return self.heap[0][1] if self.heap else None

# Deque Implementation
class Deque:
    def __init__(self, capacity):
        self.queue = [None] * capacity
        self.front = self.rear = -1
        self.capacity = capacity
    
    def insert_front(self, item):
        if self.is_full():
            raise Exception("Deque Full")
        if self.front == -1:
            self.front = self.rear = 0
        elif self.front == 0:
            self.front = self.capacity - 1
        else:
            self.front -= 1
        self.queue[self.front] = item

1. Linear Queue

Introduction to Queue (FIFO Concept)
Real-world Queue Examples
Enqueue Operation – Step by Step
Dequeue Operation – Implementation
Front & Rear Pointers Management
Queue Overflow Conditions
Queue Underflow Handling
Limitations of Linear Queue
Memory Wastage Issue
Time Complexity Analysis
Space Complexity Analysis
Array-based Implementation

2. Circular Queue

Need for Circular Queue
Circular Queue Concept
Memory Reuse Advantage
Enqueue in Circular Queue
Dequeue in Circular Queue
Front & Rear Movement Logic
Modulo Arithmetic Usage
Full Condition Detection
Empty Condition Detection
Advantages over Linear Queue
Array-Based Implementation
Pointer-Based Implementation

3. Priority Queue

Introduction to Priority Queue
Min-Heap vs Max-Heap Concepts
Heap Data Structure Basics
Insertion in Priority Queue
Heapify Up Algorithm
Deletion (Extract Min/Max)
Heapify Down Algorithm
Priority Queue Applications
CPU Scheduling Algorithms
Dijkstra’s Algorithm Usage
Task Management Systems
Implementation Using Heap

4. Deque (Double Ended Queue)

Concept of Deque
Insert Front Operation
Insert Rear Operation
Delete Front Operation
Delete Rear Operation
Applications of Deque
Sliding Window Problems
Palindrome Checking
Task Scheduling Systems
Array Implementation
Linked List Implementation
Real-time Applications

FIFO Mastery

Understand First-In-First-Out principle deeply

Memory Efficient

Learn circular queues to optimize memory usage

Priority Handling

Master priority queues for advanced scenarios

Double-Ended

Work with deques for flexible data handling

Four Types of Queues

📊

Linear Queue

Simple FIFO structure with fixed front and rear movement. Straightforward but limited by memory wastage.

Simple FIFO

🔄

Circular Queue

Memory-efficient circular structure that reuses empty spaces. Ideal for fixed-size buffers.

Memory Efficient

⭐

Priority Queue

Elements processed based on priority rather than insertion order. Uses heap data structure.

Priority Based

↔️

Deque

Double-ended queue allowing insertion and deletion from both ends. Highly flexible structure.

Double Ended

Real-World Applications

⚡ CPU Scheduling

Operating systems use priority queues to schedule processes based on priority levels and execution time.

🔄 Breadth-First Search

Graph algorithms use queues to explore nodes level by level, ensuring shortest path discovery.

📡 Message Queues

Distributed systems and microservices use queues for asynchronous communication and task handling.

🎮 Print Spooling

Print servers manage multiple print jobs using queues, handling them in FIFO order.

🔍 Sliding Window

Deques efficiently solve sliding window problems for array/string processing in O(n) time.

🎯 Task Management

Applications use priority queues to manage tasks with different urgency levels.

Time & Space Complexity

Queue Type	Enqueue	Dequeue	Peek	Space	Best Use Case
Linear Queue	O(1)	O(1)	O(1)	O(n)	Simple FIFO needs, fixed size
Circular Queue	O(1)	O(1)	O(1)	O(n)	Fixed buffers, memory efficiency
Priority Queue	O(log n)	O(log n)	O(1)	O(n)	Priority-based processing
Deque	O(1) both ends	O(1) both ends	O(1)	O(n)	Flexible front/back operations

Implementation Examples

Circular Queue in Java

// Circular Queue Implementation in Java
class CircularQueue {
    private int[] queue;
    private int front, rear, size, capacity;
    
    public CircularQueue(int capacity) {
        this.capacity = capacity;
        queue = new int[capacity];
        front = rear = -1;
        size = 0;
    }
    
    public boolean isFull() {
        return size == capacity;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public void enqueue(int item) {
        if (isFull()) {
            throw new RuntimeException("Queue is full");
        }
        if (isEmpty()) {
            front = 0;
        }
        rear = (rear + 1) % capacity;
        queue[rear] = item;
        size++;
    }
    
    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        int item = queue[front];
        if (front == rear) {
            front = rear = -1;
        } else {
            front = (front + 1) % capacity;
        }
        size--;
        return item;
    }
    
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return queue[front];
    }
    
    public void display() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return;
        }
        System.out.print("Circular Queue: ");
        int i = front;
        while (true) {
            System.out.print(queue[i] + " ");
            if (i == rear) break;
            i = (i + 1) % capacity;
        }
        System.out.println();
    }
}

Priority Queue in Python

# Priority Queue Implementation in Python
class PriorityQueue:
    def __init__(self):
        self.heap = []
        self.size = 0
    
    def _parent(self, i):
        return (i - 1) // 2
    
    def _left_child(self, i):
        return 2 * i + 1
    
    def _right_child(self, i):
        return 2 * i + 2
    
    def _heapify_up(self, i):
        while i > 0 and self.heap[self._parent(i)][0] > self.heap[i][0]:
            self.heap[self._parent(i)], self.heap[i] = self.heap[i], self.heap[self._parent(i)]
            i = self._parent(i)
    
    def _heapify_down(self, i):
        min_index = i
        left = self._left_child(i)
        right = self._right_child(i)
        
        if left < self.size and self.heap[left][0] < self.heap[min_index][0]:
            min_index = left
        if right < self.size and self.heap[right][0] < self.heap[min_index][0]:
            min_index = right
        
        if i != min_index:
            self.heap[i], self.heap[min_index] = self.heap[min_index], self.heap[i]
            self._heapify_down(min_index)
    
    def push(self, value, priority):
        self.heap.append((priority, value))
        self.size += 1
        self._heapify_up(self.size - 1)
    
    def pop(self):
        if self.is_empty():
            raise Exception("Priority Queue is empty")
        
        root = self.heap[0]
        self.heap[0] = self.heap[self.size - 1]
        self.heap.pop()
        self.size -= 1
        
        if not self.is_empty():
            self._heapify_down(0)
        
        return root[1]
    
    def peek(self):
        if self.is_empty():
            return None
        return self.heap[0][1]
    
    def is_empty(self):
        return self.size == 0

Deque in C++

// Deque Implementation in C++
#include 
using namespace std;

class Deque {
private:
    int* arr;
    int front, rear, capacity, size;
    
public:
    Deque(int cap) {
        capacity = cap;
        arr = new int[capacity];
        front = -1;
        rear = 0;
        size = 0;
    }
    
    bool isFull() {
        return size == capacity;
    }
    
    bool isEmpty() {
        return size == 0;
    }
    
    void insertFront(int item) {
        if (isFull()) {
            cout << "Deque is full" << endl;
            return;
        }
        
        if (isEmpty()) {
            front = rear = 0;
        } else if (front == 0) {
            front = capacity - 1;
        } else {
            front--;
        }
        
        arr[front] = item;
        size++;
    }
    
    void insertRear(int item) {
        if (isFull()) {
            cout << "Deque is full" << endl;
            return;
        }
        
        if (isEmpty()) {
            front = rear = 0;
        } else if (rear == capacity - 1) {
            rear = 0;
        } else {
            rear++;
        }
        
        arr[rear] = item;
        size++;
    }
    
    void deleteFront() {
        if (isEmpty()) {
            cout << "Deque is empty" << endl;
            return;
        }
        
        if (front == rear) {
            front = rear = -1;
        } else if (front == capacity - 1) {
            front = 0;
        } else {
            front++;
        }
        
        size--;
    }
    
    void deleteRear() {
        if (isEmpty()) {
            cout << "Deque is empty" << endl;
            return;
        }
        
        if (front == rear) {
            front = rear = -1;
        } else if (rear == 0) {
            rear = capacity - 1;
        } else {
            rear--;
        }
        
        size--;
    }
    
    int getFront() {
        if (isEmpty()) {
            return -1;
        }
        return arr[front];
    }
    
    int getRear() {
        if (isEmpty()) {
            return -1;
        }
        return arr[rear];
    }
    
    void display() {
        if (isEmpty()) {
            cout << "Deque is empty" << endl;
            return;
        }
        
        cout << "Deque elements: ";
        if (front <= rear) {
            for (int i = front; i <= rear; i++)
                cout << arr[i] << " ";
        } else {
            for (int i = front; i < capacity; i++)
                cout << arr[i] << " ";
            for (int i = 0; i <= rear; i++)
                cout << arr[i] << " ";
        }
        cout << endl;
    }
};

Master Queue Data Structures Today

Join thousands of developers who have aced coding interviews and built efficient systems with comprehensive queue knowledge. Essential for algorithms, system design, and performance optimization.

Start Learning Queues Now