Queue

Single Ended

What is a Single-Ended Queue?

A single-ended queue is what most people just mean when they say "queue" — insertion only happens at the rear, removal only happens at the front, and that one-directional flow is what keeps the ordering strictly first-in, first-out.

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)
Advertisement

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

That predictability is the whole point. Plenty of algorithms and system designs depend on knowing that items get processed in exactly the order they arrived, and a single-ended queue is the simplest structure that guarantees it.

Daily DSA Challenge by Scale Engineer

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