Queue

Single Ended

What is a Single-Ended Queue?

A single-ended queue (often just called a queue) is a linear data structure that follows the FIFO (First-In-First-Out) principle. Elements are added (enqueued) at the rear and removed (dequeued) from the front, maintaining strict ordering.

Key Characteristics

Single-ended queues have these fundamental properties:

  1. Two ends:
    • Front (for removal) and rear (for insertion)
  2. Basic Operations:
    • enqueue() - Add to rear
    • dequeue() - Remove from front
    • peek() - View front element
    • isEmpty() - Check if empty
  3. Fixed Order:
    • Elements are processed in exact arrival sequence

Visual Example

Operation sequence on an initially empty queue:

  1. enqueue(10): [10]
  2. enqueue(20): [10, 20]
  3. enqueue(30): [10, 20, 30]
  4. dequeue(): Returns 10 → [20, 30]
  5. peek(): Returns 20 → [20, 30] (unchanged)

Implementation Variations

Common implementation approaches:

  1. Array-Based:
    • Fixed or dynamic array
    • Need to handle wrap-around for circular queues
  2. Linked List:
    • Head pointer as front
    • Tail pointer as rear
    • Efficient O(1) operations

Time Complexity

  • enqueue(): O(1)
  • dequeue(): O(1)
  • peek(): O(1)
  • isEmpty(): O(1)

Applications

Single-ended queues are used in:

  • CPU task scheduling
  • Print job management
  • Breadth-First Search (BFS) algorithms
  • Buffering data streams
  • Handling requests in web servers

Comparison with Double-Ended Queue

Key differences:

  • Single-ended only allows insertion at rear and removal at front
  • Double-ended (deque) allows insertion/removal at both ends
  • Single-ended has stricter FIFO enforcement
  • Single-ended is simpler to implement

The single-ended queue is a fundamental data structure in computer science, providing predictable ordering that's essential for many algorithms and system design patterns where processing order matters.

Daily DSA Challenge by Hello World

Single-Ended Queue Visualiser (FIFO)

Queue is empty

Test Your Knowledge before moving forward!

Single-Ended Queue Quiz

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Single Ended Queue Implementation

// Queue Implementation (JavaScript)
class Queue {
  constructor(size = 10) {
    this.items = new Array(size);
    this.front = 0;
    this.rear = -1;
    this.size = 0;
    this.capacity = size;
  }

  // Add to rear (enqueue)
  enqueue(item) {
    if (this.isFull()) {
      console.log("Queue Overflow");
      return;
    }
    this.rear = (this.rear + 1) % this.capacity;
    this.items[this.rear] = item;
    this.size++;
  }

  // Remove from front (dequeue)
  dequeue() {
    if (this.isEmpty()) {
      console.log("Queue Underflow");
      return undefined;
    }
    const item = this.items[this.front];
    this.front = (this.front + 1) % this.capacity;
    this.size--;
    return item;
  }

  // Peek front element
  peek() {
    if (this.isEmpty()) {
      console.log("Queue is empty");
      return undefined;
    }
    return this.items[this.front];
  }

  // Check if empty
  isEmpty() {
    return this.size === 0;
  }

  // Check if full
  isFull() {
    return this.size === this.capacity;
  }

  // Get current size
  getSize() {
    return this.size;
  }

  // Print queue contents
  print() {
    if (this.isEmpty()) {
      console.log("Queue is empty");
      return;
    }
    console.log("Queue contents (front to rear):");
    for (let i = 0; i < this.size; i++) {
      const index = (this.front + i) % this.capacity;
      console.log(this.items[index]);
    }
  }
}

// Usage
const queue = new Queue(5);
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log("Front element:", queue.peek()); // 10
console.log("Queue size:", queue.getSize()); // 3
queue.print();
queue.dequeue();
console.log("After dequeue, front element:", queue.peek()); // 20

Done With the Learning

Mark Single Ended Queue as done and view it on your dashboard

Explore Other Types

Double Ended Queue

Circular Queue

Multiple Queue

Priority Queue