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

Queue & Deque

Guide 5 of 6 · Path 5 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 Deque

Problem (restated)

Fixed-capacity circular double-ended queue: insert/delete front and last, getFront/getRear, isEmpty/isFull.

Intuition

Same ring buffer as circular queue; insertFront moves head backward modulo k.

Approaches

Ring buffer double-ended

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

Idea. head points at front; rear is (head+count-1)%k. insertLast writes at (head+count)%k.

Walkthrough. k=3: insertLast 1,2; insertFront 3; getFront=3 getRear=2.

Trade-offs. Linked-list deque is simpler but not fixed capacity / O(1) memory.

Solution
export class MyCircularDeque {
  private a: number[];
  private head = 0;
  private count = 0;
  constructor(k: number) {
    this.a = Array(k).fill(0);
  }
  insertFront(value: number): boolean {
    if (this.isFull()) return false;
    this.head = (this.head - 1 + this.a.length) % this.a.length;
    this.a[this.head] = value;
    this.count++;
    return true;
  }
  insertLast(value: number): boolean {
    if (this.isFull()) return false;
    this.a[(this.head + this.count) % this.a.length] = value;
    this.count++;
    return true;
  }
  deleteFront(): boolean {
    if (this.isEmpty()) return false;
    this.head = (this.head + 1) % this.a.length;
    this.count--;
    return true;
  }
  deleteLast(): boolean {
    if (this.isEmpty()) return false;
    this.count--;
    return true;
  }
  getFront(): number {
    return this.isEmpty() ? -1 : this.a[this.head]!;
  }
  getRear(): 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 MyCircularDeque {
  private a: number[];
  private head = 0;
  private count = 0;
  constructor(k: number) {
    this.a = Array(k).fill(0);
  }
  insertFront(value: number): boolean {
    if (this.isFull()) return false;
    this.head = (this.head - 1 + this.a.length) % this.a.length;
    this.a[this.head] = value;
    this.count++;
    return true;
  }
  insertLast(value: number): boolean {
    if (this.isFull()) return false;
    this.a[(this.head + this.count) % this.a.length] = value;
    this.count++;
    return true;
  }
  deleteFront(): boolean {
    if (this.isEmpty()) return false;
    this.head = (this.head + 1) % this.a.length;
    this.count--;
    return true;
  }
  deleteLast(): boolean {
    if (this.isEmpty()) return false;
    this.count--;
    return true;
  }
  getFront(): number {
    return this.isEmpty() ? -1 : this.a[this.head]!;
  }
  getRear(): 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 deque / ring buffer.

Reflection