Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Queue & Deque

Guide 4 of 6 · Path 4 of 6

← PreviousNext →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumqueue-deque

Design Circular Queue

Problem (restated)

Implement a fixed-capacity circular queue: enQueue, deQueue, Front, Rear, isEmpty, isFull.

Intuition

Array of size k with head index and count (or head/tail). Modular arithmetic for wrap-around.

Approaches

Ring buffer with head + count

Tested only
Time O(1) opsSpace O(k)

Idea. Write at (head+count)%k; dequeue advances head. Empty when count=0; full when count=k.

Walkthrough. k=3: en 1,2,3 full; de; en 4; Front=2 Rear=4.

Trade-offs. head/tail without count needs a waste slot or flag for full vs empty.

Solution
export class MyCircularQueue {
  private a: number[];
  private head = 0;
  private count = 0;
  constructor(k: number) {
    this.a = Array(k).fill(0);
  }
  enQueue(value: number): boolean {
    if (this.isFull()) return false;
    this.a[(this.head + this.count) % this.a.length] = value;
    this.count++;
    return true;
  }
  deQueue(): boolean {
    if (this.isEmpty()) return false;
    this.head = (this.head + 1) % this.a.length;
    this.count--;
    return true;
  }
  Front(): number {
    return this.isEmpty() ? -1 : this.a[this.head]!;
  }
  Rear(): number {
    return this.isEmpty() ? -1 : this.a[(this.head + this.count - 1) % this.a.length]!;
  }
  isEmpty(): boolean {
    return this.count === 0;
  }
  isFull(): boolean {
    return this.count === this.a.length;
  }
}

export class MyCircularQueue {
  private a: number[];
  private head = 0;
  private count = 0;
  constructor(k: number) {
    this.a = Array(k).fill(0);
  }
  enQueue(value: number): boolean {
    if (this.isFull()) return false;
    this.a[(this.head + this.count) % this.a.length] = value;
    this.count++;
    return true;
  }
  deQueue(): boolean {
    if (this.isEmpty()) return false;
    this.head = (this.head + 1) % this.a.length;
    this.count--;
    return true;
  }
  Front(): number {
    return this.isEmpty() ? -1 : this.a[this.head]!;
  }
  Rear(): number {
    return this.isEmpty() ? -1 : this.a[(this.head + this.count - 1) % this.a.length]!;
  }
  isEmpty(): boolean {
    return this.count === 0;
  }
  isFull(): boolean {
    return this.count === this.a.length;
  }
}

Template connection

Circular queue / ring buffer.

Reflection