Single Ended Queue

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.

Visualize Single Ended Queue Operations

Queue is empty
FrontRear
Queue is empty

Test Your Knowledge before moving forward!

Queue Quiz Challenge

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

Explore Other Types

Double Ended Queue

Circular Queue

Multiple Queue

Priority Queue