JavaScript ile Stack ve Queue Veri Yapılarını Keşfetmek

JavaScript ile Stack ve Queue Veri Yapılarını Keşfetmek

Giriş: Veri Yapılarının Temeli

Yazılım geliştirme dünyasında, verileri etkili bir şekilde depolamak ve yönetmek, uygulamaların performansı ve sürdürülebilirliği için kritik öneme sahiptir. Veri yapıları, verilerin belirli bir düzende organize edilmesini sağlayan ve bu verilere erişim, ekleme, silme gibi işlemleri optimize eden temel araçlardır. Doğru veri yapısını seçmek, bir algoritmanın veya uygulamanın verimliliğini büyük ölçüde etkileyebilir. Bu makalede, bilgisayar bilimlerinin en temel ve yaygın kullanılan doğrusal veri yapılarından ikisi olan Stack (Yığın) ve Queue (Kuyruk) yapılarını JavaScript bağlamında derinlemesine inceleyeceğiz.

JavaScript, dinamik yapısı ve geniş kullanım alanı sayesinde, bu temel veri yapılarını anlamak ve uygulamak için mükemmel bir platform sunar. Web tarayıcılarından sunucu tarafı uygulamalarına (Node.js) kadar her yerde karşımıza çıkan JavaScript, veri yapıları kavramlarını somutlaştırmak için esnek ve anlaşılır bir yol sağlar. Bu makale boyunca, Stack ve Queue’nun ne olduğunu, temel işlemlerini, JavaScript ile nasıl uygulanabileceğini, zaman karmaşıklıklarını (Big O notasyonu) ve gerçek dünya kullanım senaryolarını detaylı bir şekilde ele alacağız. Amacımız, bu yapıların sadece teorik bilgilerini vermekle kalmayıp, pratik JavaScript uygulamalarıyla kavramları pekiştirmektir.

Stack (Yığın) Veri Yapısı

Stack, “Last-In, First-Out” (LIFO) prensibine göre çalışan doğrusal bir veri yapısıdır. Bu prensip, bir yığına en son eklenen elemanın ilk çıkarılacağı anlamına gelir. Günlük hayattan bir örnekle açıklamak gerekirse, üst üste dizilmiş tabakları düşünebiliriz: en son konulan tabak en üstte olur ve ilk o alınır. Stack veri yapısı, belirli bir sırayla eklenen elemanların yine belirli bir sırayla işlenmesi gereken birçok senaryoda kullanılır.

Temel Stack İşlemleri

Bir Stack veri yapısının temel işlemleri şunlardır:

* push(element): Yığının en üstüne bir eleman ekler.
* pop(): Yığının en üstündeki elemanı çıkarır ve döndürür. Eğer yığın boşsa, genellikle bir hata fırlatılır veya undefined/null döndürülür.
* peek(): Yığının en üstündeki elemanı çıkarmaz, sadece değerini döndürür.
* isEmpty(): Yığının boş olup olmadığını kontrol eder ve bir boolean değer döndürür.
* size(): Yığındaki eleman sayısını döndürür.

JavaScript ile Stack Uygulaması

JavaScript’te Stack veri yapısını uygulamanın birkaç yolu vardır. En basit ve yaygın yol, JavaScript’in yerleşik Array (Dizi) nesnesini kullanmaktır. Array‘in push() ve pop() metotları doğrudan LIFO prensibine uygun çalışır. Ancak, daha yapılandırılmış ve veri yapısı özelliklerini daha iyi kapsayan bir yaklaşım, bir sınıf (Class) oluşturmaktır.

Array Kullanarak Basit Stack Uygulaması

class SimpleStack {
    constructor() {
        this.items = []; // Stack elemanlarını tutacak dizi
    }

    // Yığına eleman ekler
    push(element) {
        this.items.push(element);
        console.log(${element} yığına eklendi.);
    }

    // Yığından eleman çıkarır
    pop() {
        if (this.isEmpty()) {
            console.log("Yığın boş, çıkarılacak eleman yok.");
            return undefined; // veya hata fırlatabiliriz
        }
        const removedElement = this.items.pop();
        console.log(${removedElement} yığından çıkarıldı.);
        return removedElement;
    }

    // Yığının en üstündeki elemanı gösterir
    peek() {
        if (this.isEmpty()) {
            console.log("Yığın boş, gösterilecek eleman yok.");
            return undefined;
        }
        return this.items[this.items.length - 1];
    }

    // Yığının boş olup olmadığını kontrol eder
    isEmpty() {
        return this.items.length === 0;
    }

    // Yığındaki eleman sayısını döndürür
    size() {
        return this.items.length;
    }

    // Yığının içeriğini gösterir (isteğe bağlı)
    printStack() {
        console.log("Yığın içeriği:", this.items.toString());
    }
}

// SimpleStack kullanımı
const mySimpleStack = new SimpleStack();
console.log("Yığın boş mu?", mySimpleStack.isEmpty()); // true

mySimpleStack.push(10);
mySimpleStack.push(20);
mySimpleStack.push(30);
mySimpleStack.printStack(); // Yığın içeriği: 10,20,30

console.log("Yığının üstündeki eleman:", mySimpleStack.peek()); // 30

mySimpleStack.pop(); // 30 yığından çıkarıldı.
mySimpleStack.printStack(); // Yığın içeriği: 10,20

console.log("Yığın boyutu:", mySimpleStack.size()); // 2

mySimpleStack.pop(); // 20 yığından çıkarıldı.
mySimpleStack.pop(); // 10 yığından çıkarıldı.
mySimpleStack.pop(); // Yığın boş, çıkarılacak eleman yok.
console.log("Yığın boş mu?", mySimpleStack.isEmpty()); // true

Bu SimpleStack sınıfı, Array‘in push ve pop metotlarını kullanarak Stack işlevselliğini kolayca sağlar. peek, isEmpty ve size metotları da Array‘in length özelliğini kullanarak basitçe uygulanır. Bu yaklaşım oldukça etkilidir çünkü JavaScript dizileri, eleman ekleme ve çıkarma işlemlerini dizinin sonundan yaparken genellikle O(1) zaman karmaşıklığına sahiptir.

Object Kullanarak Stack Uygulaması (Daha Düşük Seviye Kontrol)

Diziler yerine, elemanları bir JavaScript objesi içinde tutarak ve bir count değişkeni ile yöneterek de Stack uygulayabiliriz. Bu yaklaşım, bazı durumlarda daha düşük seviye kontrol sağlayabilir ve dizilerin dahili yeniden boyutlandırma maliyetlerinden kaçınmak için düşünülebilir, ancak modern JavaScript motorları dizileri oldukça optimize etmiştir.

class Stack {
    constructor() {
        this.items = {}; // Elemanları tutacak obje
        this.count = 0;  // Yığındaki eleman sayısı
    }

    // Yığına eleman ekler
    push(element) {
        this.items[this.count] = element;
        this.count++;
        console.log(${element} yığına eklendi.);
    }

    // Yığından eleman çıkarır
    pop() {
        if (this.isEmpty()) {
            console.log("Yığın boş, çıkarılacak eleman yok.");
            return undefined;
        }
        this.count--;
        const removedElement = this.items[this.count];
        delete this.items[this.count]; // Elemanı objeden sil
        console.log(${removedElement} yığından çıkarıldı.);
        return removedElement;
    }

    // Yığının en üstündeki elemanı gösterir
    peek() {
        if (this.isEmpty()) {
            console.log("Yığın boş, gösterilecek eleman yok.");
            return undefined;
        }
        return this.items[this.count - 1];
    }

    // Yığının boş olup olmadığını kontrol eder
    isEmpty() {
        return this.count === 0;
    }

    // Yığındaki eleman sayısını döndürür
    size() {
        return this.count;
    }

    // Yığının içeriğini gösterir
    printStack() {
        let str = "";
        for (let i = 0; i < this.count; i++) {
            str += this.items[i] + " ";
        }
        console.log("Yığın içeriği:", str.trim());
    }
}

// Stack kullanımı
const myStack = new Stack();
console.log("Yığın boş mu?", myStack.isEmpty()); // true

myStack.push("A");
myStack.push("B");
myStack.push("C");
myStack.printStack(); // Yığın içeriği: A B C

console.log("Yığının üstündeki eleman:", myStack.peek()); // C

myStack.pop(); // C yığından çıkarıldı.
myStack.printStack(); // Yığın içeriği: A B

console.log("Yığın boyutu:", myStack.size()); // 2

myStack.pop(); // B yığından çıkarıldı.
myStack.pop(); // A yığından çıkarıldı.
myStack.pop(); // Yığın boş, çıkarılacak eleman yok.
console.log("Yığın boş mu?", myStack.isEmpty()); // true

Bu Stack sınıfında, items bir obje olarak tanımlanır ve elemanlar sayısal anahtarlar kullanılarak saklanır. count değişkeni, yığının boyutunu ve bir sonraki elemanın ekleneceği indeksi takip eder. pop işlemi sırasında, eleman objeden delete anahtar kelimesi ile silinir. Bu yaklaşım da Stack'in O(1) zaman karmaşıklığına sahip olmasını sağlar.

Stack İşlemlerinin Zaman Karmaşıklığı (Big O)

Stack işlemlerinin çoğu, eleman sayısından bağımsız olarak sabit zamanda (O(1)) tamamlanır.

* push(): O(1) - Eleman eklemek her zaman aynı süreyi alır.
* pop(): O(1) - Eleman çıkarmak her zaman aynı süreyi alır.
* peek(): O(1) - En üstteki elemana bakmak her zaman aynı süreyi alır.
* isEmpty(): O(1) - Boşluk kontrolü her zaman aynı süreyi alır.
* size(): O(1) - Boyut bilgisini almak her zaman aynı süreyi alır.

Bu verimlilik, Stack'i birçok algoritma ve uygulama için cazip bir veri yapısı haline getirir.

Stack Kullanım Senaryoları

Stack veri yapısı, bilgisayar bilimlerinde ve yazılım geliştirmede çok çeşitli alanlarda kullanılır:

1. Fonksiyon Çağrı Yığını (Call Stack): Programların fonksiyon çağrılarını yönetmek için kullanılır. Bir fonksiyon çağrıldığında yığına eklenir, işi bittiğinde yığından çıkarılır.
2. Geri Al/Yinele (Undo/Redo) Fonksiyonelliği: Metin düzenleyicilerde veya diğer uygulamalarda yapılan işlemleri takip etmek için kullanılır. Her işlem yığına eklenir, "geri al" komutu son işlemi yığından çıkarır.
3. Tarayıcı Geçmişi: Web tarayıcılarında "geri" tuşuna basıldığında önceki sayfaya dönme işlevi, Stack mantığıyla çalışır. Ziyaret edilen sayfalar bir yığına eklenir.
4. Matematiksel İfadelerin Değerlendirilmesi: Infix (orta ek) gösterimdeki matematiksel ifadeleri postfix (son ek) veya prefix (ön ek) gösterime dönüştürmek ve bu ifadeleri değerlendirmek için Stack kullanılır.
5. Derinlemesine Arama (DFS - Depth-First Search) Algoritması: Graf ve ağaç yapılarında derinlemesine arama yapmak için Stack kullanılır.
6. Parantez Eşleştirme: Bir ifadedeki parantezlerin (, [ { gibi) doğru eşleşip eşleşmediğini kontrol etmek için Stack kullanılır.

* enqueue(element): Kuyruğun arkasına bir eleman ekler.
* dequeue(): Kuyruğun önündeki elemanı çıkarır ve döndürür. Eğer kuyruk boşsa, genellikle bir hata fırlatılır veya undefined/null döndürülür.
* front(): Kuyruğun önündeki elemanı çıkarmaz, sadece değerini döndürür.
* isEmpty(): Kuyruğun boş olup olmadığını kontrol eder ve bir boolean değer döndürür.
* size(): Kuyruktaki eleman sayısını döndürür.

JavaScript'te Queue veri yapısını uygulamanın en basit yolu yine Array kullanmaktır. Ancak Array'in shift() metodu, kuyruğun başından eleman çıkarmak için kullanıldığında performans sorunlarına yol açabilir. Bu nedenle, daha verimli bir uygulama için bir sınıf içinde obje veya bağlı liste (Linked List) kullanmak tercih edilebilir.

class SimpleQueue {
    constructor() {
        this.items = [];
    }

    // Kuyruğa eleman ekler (arkaya)
    enqueue(element) {
        this.items.push(element);
        console.log(${element} kuyruğa eklendi.);
    }

    // Kuyruktan eleman çıkarır (önden)
    dequeue() {
        if (this.isEmpty()) {
            console.log("Kuyruk boş, çıkarılacak eleman yok.");
            return undefined;
        }
        // Array.shift() kullanmak, dizinin başından eleman çıkardığı için
        // kalan tüm elemanların indekslerini yeniden düzenler.
        // Bu, büyük dizilerde O(n) zaman karmaşıklığına neden olur.
        const removedElement = this.items.shift();
        console.log(${removedElement} kuyruktan çıkarıldı.);
        return removedElement;
    }

    // Kuyruğun önündeki elemanı gösterir
    front() {
        if (this.isEmpty()) {
            console.log("Kuyruk boş, gösterilecek eleman yok.");
            return undefined;
        }
        return this.items[0];
    }

    // Kuyruğun boş olup olmadığını kontrol eder
    isEmpty() {
        return this.items.length === 0;
    }

    // Kuyruktaki eleman sayısını döndürür
    size() {
        return this.items.length;
    }

    // Kuyruğun içeriğini gösterir
    printQueue() {
        console.log("Kuyruk içeriği:", this.items.toString());
    }
}

// SimpleQueue kullanımı
const mySimpleQueue = new SimpleQueue();
console.log("Kuyruk boş mu?", mySimpleQueue.isEmpty()); // true

mySimpleQueue.enqueue("Görev 1");
mySimpleQueue.enqueue("Görev 2");
mySimpleQueue.enqueue("Görev 3");
mySimpleQueue.printQueue(); // Kuyruk içeriği: Görev 1,Görev 2,Görev 3

console.log("Kuyruğun önündeki eleman:", mySimpleQueue.front()); // Görev 1

mySimpleQueue.dequeue(); // Görev 1 kuyruktan çıkarıldı.
mySimpleQueue.printQueue(); // Kuyruk içeriği: Görev 2,Görev 3

console.log("Kuyruk boyutu:", mySimpleQueue.size()); // 2

mySimpleQueue.dequeue(); // Görev 2 kuyruktan çıkarıldı.
mySimpleQueue.dequeue(); // Görev 3 kuyruktan çıkarıldı.
mySimpleQueue.dequeue(); // Kuyruk boş, çıkarılacak eleman yok.
console.log("Kuyruk boş mu?", mySimpleQueue.isEmpty()); // true

Yukarıdaki SimpleQueue uygulaması basittir ancak dequeue() metodunda this.items.shift() kullanılması nedeniyle performans sorunları yaşayabilir. shift() metodu, dizinin başından bir eleman çıkardığında, kalan tüm elemanları birer indeks sola kaydırmak zorunda kalır. Bu işlem, dizinin boyutu n olduğunda O(n) zaman karmaşıklığına sahiptir. Bu da büyük kuyruklar için kabul edilemez bir yavaşlığa yol açabilir.

Dizinin shift() metodunun performans sorununu aşmak için, elemanları bir obje içinde saklayabilir ve head (ön) ve tail (arka) işaretçileri kullanarak kuyruğu yönetebiliriz. Bu yaklaşım, enqueue ve dequeue işlemlerini O(1) zaman karmaşıklığında yapmamızı sağlar.

class Queue {
    constructor() {
        this.items = {};    // Elemanları tutacak obje
        this.head = 0;      // Kuyruğun önünü işaret eder
        this.tail = 0;      // Kuyruğun arkasını işaret eder
    }

    // Kuyruğa eleman ekler (arkaya)
    enqueue(element) {
        this.items[this.tail] = element;
        this.tail++;
        console.log(${element} kuyruğa eklendi.);
    }

    // Kuyruktan eleman çıkarır (önden)
    dequeue() {
        if (this.isEmpty()) {
            console.log("Kuyruk boş, çıkarılacak eleman yok.");
            return undefined;
        }
        const removedElement = this.items[this.head];
        delete this.items[this.head]; // Elemanı objeden sil
        this.head++; // Ön işaretçiyi bir sonraki elemana kaydır
        console.log(${removedElement} kuyruktan çıkarıldı.);
        return removedElement;
    }

    // Kuyruğun önündeki elemanı gösterir
    front() {
        if (this.isEmpty()) {
            console.log("Kuyruk boş, gösterilecek eleman yok.");
            return undefined;
        }
        return this.items[this.head];
    }

    // Kuyruğun boş olup olmadığını kontrol eder
    isEmpty() {
        return this.head === this.tail; // head ve tail aynıysa kuyruk boştur
    }

    // Kuyruktaki eleman sayısını döndürür
    size() {
        return this.tail - this.head;
    }

    // Kuyruğun içeriğini gösterir
    printQueue() {
        let str = "";
        for (let i = this.head; i < this.tail; i++) {
            str += this.items[i] + " ";
        }
        console.log("Kuyruk içeriği:", str.trim());
    }
}

// Queue kullanımı
const myQueue = new Queue();
console.log("Kuyruk boş mu?", myQueue.isEmpty()); // true

myQueue.enqueue("İşlem A");
myQueue.enqueue("İşlem B");
myQueue.enqueue("İşlem C");
myQueue.printQueue(); // Kuyruk içeriği: İşlem A İşlem B İşlem C

console.log("Kuyruğun önündeki eleman:", myQueue.front()); // İşlem A

myQueue.dequeue(); // İşlem A kuyruktan çıkarıldı.
myQueue.printQueue(); // Kuyruk içeriği: İşlem B İşlem C

console.log("Kuyruk boyutu:", myQueue.size()); // 2

myQueue.dequeue(); // İşlem B kuyruktan çıkarıldı.
myQueue.dequeue(); // İşlem C kuyruktan çıkarıldı.
myQueue.dequeue(); // Kuyruk boş, çıkarılacak eleman yok.
console.log("Kuyruk boş mu?", myQueue.isEmpty()); // true

Bu Queue sınıfı, items objesi ve head, tail işaretçileri ile çok daha verimlidir. enqueue işlemi tail işaretçisini artırırken, dequeue işlemi head işaretçisini artırır ve elemanı objeden siler. Bu sayede, elemanların indekslerinin sürekli kaydırılmasına gerek kalmaz, bu da her iki işlemin de O(1) zaman karmaşıklığına sahip olmasını sağlar.

* enqueue(): O(1) - Eleman eklemek her zaman aynı süreyi alır.
* dequeue(): O(1) - Eleman çıkarmak (obje tabanlı veya bağlı liste ile) her zaman aynı süreyi alır. (Array.shift() ile O(n)).
* front(): O(1) - En öndeki elemana bakmak her zaman aynı süreyi alır.
* isEmpty(): O(1) - Boşluk kontrolü her zaman aynı süreyi alır.
* size(): O(1) - Boyut bilgisini almak her zaman aynı süreyi alır.

Bu makalede, Stack ve Queue'nun tanımlarını, temel işlemlerini, JavaScript'te Array ve Object` kullanarak nasıl uygulanabileceğini, zaman karmaşıklıklarını ve yaygın kullanım senaryolarını ayrıntılı bir şekilde inceledik. Ayrıca, dairesel kuyruk, öncelikli kuyruk ve Deque gibi gelişmiş kavramlara da kısaca değindik.

Veri yapıları dünyası geniş ve karmaşıktır, ancak Stack ve Queue ile sağlam bir başlangıç yapmak, daha karmaşık veri yapılarını (ağaçlar, graflar, hash tabloları vb.) anlamak için temel bir zemin oluşturur. Bu bilgileri pekiştirmek için farklı senaryolarda Stack ve Queue kullanarak pratik yapmaya devam etmek, problem çözme becerilerinizi ve algoritma bilginizi önemli ölçüde geliştirecektir. Unutmayın, iyi bir yazılımcı sadece kod yazmaz, aynı zamanda veriyi nasıl organize edeceğini ve işleyeceğini de bilir.