Explore different types of queues: circular queues for efficient memory usage, priority queues for ordered processing, and deques for maximum flexibility. Master the implementations that power real-world systems.

Learning Objectives

Circular Queue

Optimize memory with wraparound

Priority Queue

Process elements by priority

Deque

Insert/remove from both ends

Implementation

Code efficient solutions

Queue Types Overview

Simple Queue

Basic FIFO queue with linear array

Circular Queue

Wraparound queue for memory efficiency

Priority Queue

Elements served by priority order

Deque

Double-ended queue flexibility

Simple Queue (Linear Queue)

A simple queue uses a linear array with front and rear pointers. Elements are added at the rear and removed from the front, following strict FIFO ordering.

Key Characteristics:

Simple to implement and understand

Fixed size (when using arrays)

Memory wastage after dequeue operations

O(1) enqueue and dequeue operations

Problem with Simple Queue

Once elements are dequeued, the space at the beginning cannot be reused, leading to "false full" condition even when array has empty spaces.

Issue: Array [_, _, _, A, B, C] appears "full" at rear but has empty spaces at front!

Simple Queue Implementation

class SimpleQueue {

constructor(size) {

this.arr = new Array(size);

this.front = -1;

this.rear = -1;

this.size = size;

}

Enqueue Operation:

if (rear === size-1) return "Queue Full";

if (front === -1) front = 0;

arr[++rear] = element;

Dequeue Operation:

if (front === -1) return "Queue Empty";

element = arr[front++];

if (front > rear) front = rear = -1;

Circular Queue (Ring Buffer)

A circular queue solves the memory wastage problem by connecting the rear back to the front, creating a circular arrangement. When the rear reaches the end, it wraps around to the beginning.

Advantages:

Maximum memory utilization

No memory wastage

Continuous operations possible

Perfect for buffering applications

Key Formula:

next_position = (current + 1) % size

This modulo operation creates the wraparound effect that makes the queue "circular".

Real-World Uses:

• Buffer for streaming data (audio/video)

• Keyboard buffer in operating systems

• Network packet buffering

• Round-robin scheduling

Circular Queue Visualization

FRONT ↓

↑ REAR

Implementation Logic:

// Enqueue

rear = (rear + 1) % size;

arr[rear] = element;

// Dequeue

element = arr[front];

front = (front + 1) % size;

Memory Efficiency:

Uses 100% of allocated space, no wastage unlike simple queue!

Priority Queue

In a priority queue, elements are served based on their priority rather than their arrival order. Higher priority elements are dequeued first, regardless of when they were added.

Types of Priority:

Max Priority Queue: Highest priority served first

Min Priority Queue: Lowest priority served first

Custom Priority: User-defined priority function

Implementation Options:

Simple Array:O(n) insertion, O(1) deletion

Sorted Array:O(n) insertion, O(1) deletion

Heap:O(log n) insertion, O(log n) deletion

Priority Queue Example

Hospital Emergency Room:

Heart Attack PatientPriority: 1

Broken ArmPriority: 3

Minor CutPriority: 5

Chest PainPriority: 2

Serving Order:

1. Heart Attack (Priority 1) → 2. Chest Pain (Priority 2) → 3. Broken Arm (Priority 3) → 4. Minor Cut (Priority 5)

Real-World Priority Queue Applications

Operating Systems

• Process scheduling

• CPU task management

• Memory allocation

Network Systems

• Quality of Service (QoS)

• Packet routing

• Bandwidth allocation

Algorithms

• Dijkstra's shortest path

• A* pathfinding

• Huffman coding

Deque (Double-Ended Queue)

A deque (pronounced "deck") allows insertion and deletion at both ends. It combines the functionality of both stacks and queues, providing maximum flexibility.

Deque Operations:

Front Operations:

• addFront() - Insert at front

• removeFront() - Delete from front

• peekFront() - View front element

Rear Operations:

• addRear() - Insert at rear

• removeRear() - Delete from rear

• peekRear() - View rear element

Deque as Stack & Queue:

As Stack (LIFO): Use addFront() and removeFront()

As Queue (FIFO): Use addRear() and removeFront()

One data structure, multiple behaviors!

Deque Visualization

← addFront() / removeFront()

addRear() / removeRear() →

FRONT

REAR

Example Operations:

addFront('X') → [X, A, B, C, D]

addRear('Y') → [X, A, B, C, D, Y]

removeFront() → [A, B, C, D, Y]

removeRear() → [A, B, C, D]

Time Complexity:

All operations: O(1) with proper implementation

Real-World Uses:

• Browser history (back/forward)

• Undo/Redo with multiple paths

• Sliding window algorithms

• Palindrome checking

Queue Types Comparison

Queue Type	Insert	Remove	Memory Usage	Best For
Simple Queue	Rear only	Front only	Wasteful	Learning, simple cases
Circular Queue	Rear (wraps)	Front (wraps)	Efficient	Buffers, streaming
Priority Queue	By priority	Highest priority	Variable	Scheduling, algorithms
Deque	Both ends	Both ends	Efficient	Flexible applications

Previous: Queue Fundamentals Next: Queue Applications

Queue Type

Insert

Remove

Memory Usage

Best For

Simple Queue

Rear only

Front only

Wasteful

Learning, simple cases

Circular Queue

Rear (wraps)

Front (wraps)

Efficient

Buffers, streaming

Priority Queue

By priority

Highest priority

Variable

Scheduling, algorithms

Deque

Both ends

Efficient

Flexible applications