İçeriğe atla
ΣDSA Patterns
Menü
KalıplarProblemlerŞablonlarYol haritasıKaynaklarMatematikTekrarlarHakkında
Dil
EnglishTürkçe

Kuyruk ve Deque

Rehber 5 / 6 · Yol 5 / 6

← ÖncekiSonraki →

Etkileşimli

Zihinsel model

Bu problem için animasyonlu çözüm. Adımları kaydır veya boşlukla duraklat; değişmezi yüksek sesle yeniden anlat.

Adım 1 / 6
·
·
·

head = 0 · count = 0

Dairesel deque, k=3. Aynı halka; insertFront head'i modulo k geri adımlar.

Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumqueue-deque

Design Circular Deque

Problem (yeniden ifade)

Sabit kapasiteli dairesel çift uçlu kuyruk: insert/delete front ve last, getFront/getRear, isEmpty/isFull.

Sezgi

Dairesel kuyrukla aynı ring buffer; insertFront head’i modulo k geri kaydırır.

Yaklaşımlar

Çift uçlu ring buffer

Doğrulanmadı
Zaman O(1) opsAlan O(k)

Fikir. head öne işaret eder; rear (head+count-1)%k. insertLast (head+count)%k konumuna yazar.

Yürüyüş. k=3: insertLast 1,2; insertFront 3; getFront=3 getRear=2.

Trade-off. Bağlı liste deque daha basit ama sabit kapasite / O(1) bellek değil.

Çözüm
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;
  }
}

Şablon bağlantısı

Dairesel deque / ring buffer.

Yansıma