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

Kuyruk ve Deque

Rehber 4 / 6 · Yol 4 / 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 kuyruk, kapasite k=3. Dizi artı head indeksi ve count. (head+count) mod k konumuna yaz.

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 Queue

Problem (yeniden ifade)

Sabit kapasiteli dairesel kuyruk: enQueue, deQueue, Front, Rear, isEmpty, isFull.

Sezgi

k boyutlu dizi, head indeksi ve count (veya head/tail). Sarma için modüler aritmetik.

Yaklaşımlar

head + count ile ring buffer

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

Fikir. (head+count)%k konumuna yaz; dequeue head’i ilerletir. count=0 iken boş; count=k iken dolu.

Yürüyüş. k=3: en 1,2,3 full; de; en 4; Front=2 Rear=4.

Trade-off. count olmadan head/tail, dolu vs boş için boşa slot veya bayrak ister.

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

Şablon bağlantısı

Dairesel kuyruk / ring buffer.

Yansıma