C# ile Stack, Queue ve Ring Buffer: Kendi Implementasyonun ve Gerçek Kullanımlar

Sürüm notu: Bu yazıdaki kodlar .NET 10 ve C# 14 ile derlenip xUnit v3 4.0.2 testleriyle doğrulanmıştır; ölçümler BenchmarkDotNet 0.15.8 ile alınmıştır.

Önce Tahmin Et

Bookstore'un sipariş işleme servisi gelen siparişleri sıraya koyuyor ve en eskisinden başlayarak işliyor. Bir geliştirici bu sırayı List<Order> ile kurmuş: yeni sipariş Add ile sona ekleniyor, işlenecek olan list[0] ile okunup RemoveAt(0) ile çıkarılıyor. Kod doğru çalışıyor; testler yeşil.

Kampanya günü sırada 100.000 sipariş birikiyor. Aynı işi Queue<Order> ile yapmak ne kadar fark eder: yüzde birkaç mı, 10 kat mı, 500 kat mı? İkinci soru: Queue<T> de içeride bir array kullanıyor. Baştan çıkarmayı array'de kaydırma yapmadan nasıl O(1) yapıyor?

Stack: Son Giren İlk Çıkar

Stack, LIFO (Last In, First Out) sözleşmesi olan bir ADT (Abstract Data Type): Push en üste koyar, Pop en üsttekini alır, Peek bakar ama almaz. Array ile implement etmek doğal: "en üst" array'in sonu, sona ekleme ve sondan çıkarma zaten ucuz. Serinin ikinci yazısındaki dynamic array'in neredeyse aynısı:

namespace Algorithms.Linear;

public sealed class ArrayStack<T>
{
    private T[] _items = new T[4];

    public int Count { get; private set; }

    public void Push(T item)
    {
        if (Count == _items.Length) Array.Resize(ref _items, _items.Length * 2);
        _items[Count++] = item;
    }

    public T Pop()
    {
        if (Count == 0) throw new InvalidOperationException("Stack is empty.");
        T item = _items[--Count];
        _items[Count] = default!; // çıkarılan element'e reference tutma
        return item;
    }

    public T Peek() => Count == 0 ? throw new InvalidOperationException("Stack is empty.") : _items[Count - 1];

    public bool TryPop(out T item)
    {
        if (Count == 0) { item = default!; return false; }
        item = Pop();
        return true;
    }

    public void Clear()
    {
        Array.Clear(_items, 0, Count);
        Count = 0;
    }
}

Push amortized O(1), Pop ve Peek O(1). Pop'taki default ataması, serinin ikinci yazısındaki silinen slot dersiyle aynı: çıkarılan element'i array'de bırakırsan GC (Garbage Collector) onu toplayamaz. BCL'nin (Base Class Library) Stack<T>'i de aynı şekilde array tabanlı ve aynı temizliği yapıyor.

Queue ve Circular Buffer

Queue, FIFO (First In, First Out) sözleşmesi: Enqueue sona ekler, Dequeue baştan alır. Açılıştaki List çözümünün sorunu burada: baştan almak, array'de geri kalan her şeyi bir slot sola kaydırmak demek. Çözüm, element'leri kaydırmak yerine "baş"ın nerede olduğunu gösteren index'i ilerletmek. Baş ve son array'in sonuna gelince başa sarıyor; array mantıksal olarak bir halka gibi kullanılıyor. Buna circular buffer deniyor.

namespace Algorithms.Linear;

public sealed class CircularQueue<T>
{
    private T[] _items = new T[4];
    private int _head; // sıradaki çıkacak element
    private int _tail; // sıradaki boş slot
    private int _count; // head == tail hem boş hem dolu anlamına gelebilir; hangisi olduğunu count söyler

    public int Count => _count;
    public int Capacity => _items.Length;

    public void Enqueue(T item)
    {
        if (_count == _items.Length) Grow();
        _items[_tail] = item;
        _tail = (_tail + 1) % _items.Length;
        _count++;
    }

    public T Dequeue()
    {
        if (_count == 0) throw new InvalidOperationException("Queue is empty.");
        T item = _items[_head];
        _items[_head] = default!;
        _head = (_head + 1) % _items.Length;
        _count--;
        return item;
    }

    private void Grow()
    {
        T[] bigger = new T[_items.Length * 2];
        // halkayı aç: önce [head..son), sonra [0..tail) kopyala; yeni array index 0'dan başlasın
        int firstPart = Math.Min(_count, _items.Length - _head);
        Array.Copy(_items, _head, bigger, 0, firstPart);
        Array.Copy(_items, 0, bigger, firstPart, _count - firstPart);
        _items = bigger;
        _head = 0;
        _tail = _count;
    }

    internal (int Head, int Tail) Positions => (_head, _tail);
}

Circular buffer'ın klasik tuzağı boş ile doluyu ayırt etmek. İkisinde de _head == _tail: boş kuyrukta ikisi aynı boş slotu gösterir, dolu kuyrukta _tail sarılıp _head'e yetişmiştir. Üç yaygın çözüm var: ayrı bir _count tutmak (burada yaptığımız), bir slotu hep boş bırakıp "dolu" koşulunu (tail + 1) % length == head yapmak ya da index'leri modulo almadan sonsuza kadar artırıp farklarına bakmak. Grow'daki iki Array.Copy da ikinci kritik nokta: sarılmış bir halkayı büyük array'e olduğu gibi kopyalarsan sıra bozulur. Önce _head'den sona, sonra baştan _tail'e kopyalayıp halkayı düzleştirmek gerekiyor.

Test, tam bu iki durumu bir araya getiriyor: kuyruk doluyor, baştan iki element çıkıyor, iki yeni element sarılarak array'in başına yazılıyor ve tam o hâldeyken bir büyüme tetikleniyor:

[Fact]
public void CircularQueue_WrapsThenGrows_KeepsFifoOrder()
{
    CircularQueue<int> queue = new();
    for (int i = 1; i <= 4; i++) queue.Enqueue(i); // dolu: capacity 4
    queue.Dequeue();
    queue.Dequeue();
    queue.Enqueue(5);
    queue.Enqueue(6); // tail array'in başına sarıldı

    Assert.Equal((2, 2), queue.Positions);

    queue.Enqueue(7); // dolu ve sarılmış: grow halkayı açmalı
    List<int> drained = [];
    while (queue.Count > 0) drained.Add(queue.Dequeue());

    Assert.Equal([3, 4, 5, 6, 7], drained);
    Assert.Equal(8, queue.Capacity);
}

BCL'nin Queue<T>'i aynı yapıda: dotnet/runtime'daki Queue.cs'te _array, _head, _tail ve _size alanları var. İki farkı var: büyüme ×2 ama en az 4 slot ekleniyor ve index'i ilerletirken % yerine "sona geldiysen sıfırla" kontrolü kullanılıyor. Kaynak koddaki yoruma göre remainder operatörü bu iş için belirgin biçimde daha yavaş. API'nin (Application Programming Interface) kullanımı C# Koleksiyonlar serisinin "C# Queue, Stack, LinkedList ve PriorityQueue" yazısında.

Aynı halkayı iki uçtan da kullanırsan deque (double-ended queue) elde edersin: _head'i bir geri alarak başa ekleme de O(1) olur. BCL'de hazır bir Deque<T> yok; ihtiyaç olduğunda ya LinkedList<T> kullanılıyor ya da bu circular buffer'a AddFirst ve RemoveLast ekleniyor.

Bounded Ring Buffer: Son N Log Satırı

Bazen kuyruğun büyümesini istemezsin. Bookstore'un ödeme servisi hata aldığında son 200 log satırını hata raporuna eklemek istiyorsun ama bütün log'u bellekte tutamazsın. Sabit kapasiteli bir ring buffer bunun için: dolduğunda ne yapacağına önceden karar verilmiş bir halka.

namespace Algorithms.Linear;

public enum OverflowPolicy
{
    OverwriteOldest,
    Reject,
}

// sabit kapasite, hiç büyümez: bellek kullanımı baştan belli
public sealed class RingBuffer<T>(int capacity, OverflowPolicy policy)
{
    private readonly T[] _items = new T[capacity];
    private int _head;
    private int _count;

    public int Count => _count;
    public long Dropped { get; private set; }

    public bool TryWrite(T item)
    {
        if (_count == _items.Length)
        {
            if (policy == OverflowPolicy.Reject)
            {
                Dropped++;
                return false;
            }
            // overwrite: en eski element kaybolur, head bir ilerler
            _items[_head] = item;
            _head = (_head + 1) % _items.Length;
            Dropped++;
            return true;
        }
        _items[(_head + _count) % _items.Length] = item;
        _count++;
        return true;
    }

    // en eskiden en yeniye
    public T[] Snapshot()
    {
        T[] result = new T[_count];
        for (int i = 0; i < _count; i++) result[i] = _items[(_head + i) % _items.Length];
        return result;
    }
}

[Fact]
public void RingBuffer_Overwrite_KeepsLastN()
{
    RingBuffer<string> lastLines = new(3, OverflowPolicy.OverwriteOldest);
    foreach (string line in new[] { "l1", "l2", "l3", "l4", "l5" }) lastLines.TryWrite(line);

    Assert.Equal(["l3", "l4", "l5"], lastLines.Snapshot());
    Assert.Equal(2, lastLines.Dropped);
}

[Fact]
public void RingBuffer_Reject_KeepsFirstN()
{
    RingBuffer<string> buffer = new(3, OverflowPolicy.Reject);
    bool[] accepted = [.. new[] { "l1", "l2", "l3", "l4" }.Select(buffer.TryWrite)];

    Assert.Equal([true, true, true, false], accepted);
    Assert.Equal(["l1", "l2", "l3"], buffer.Snapshot());
}

İki politika iki farklı soruya cevap veriyor. Overwrite "en son ne oldu?" sorusu için: log, metrik örnekleri, son N istek. Reject ise "hiçbir şey sessizce kaybolmasın, fazlası geri çevrilsin" için: işlenmesi zorunlu siparişler, çağıran tarafın tekrar denemesi gereken işler. Dropped sayacı ikisinde de önemli; kaybolan ya da reddedilen element sayısını bir metrik olarak dışarı vermezsen, buffer'ın sürekli taştığını kimse fark etmez.

Stack ile Çözülen İşler: Parantez ve Undo/Redo

Stack, "en son açılanı ilk kapat" yapısındaki her problemin doğal aracı. Bookstore'un kampanya kuralı editörü kullanıcının yazdığı ifadeyi kaydetmeden önce parantez dengesini kontrol ediyor:

public static class BracketValidator
{
    // ilk hatanın index'ini döner; metin dengeliyse -1
    public static int FindError(string text)
    {
        Stack<(char Bracket, int Index)> open = new();
        for (int i = 0; i < text.Length; i++)
        {
            char c = text[i];
            if (c is '(' or '[' or '{')
            {
                open.Push((c, i));
            }
            else if (c is ')' or ']' or '}')
            {
                char expected = c switch { ')' => '(', ']' => '[', _ => '{' };
                if (!open.TryPop(out (char Bracket, int Index) top) || top.Bracket != expected)
                    return i;
            }
        }
        return open.TryPeek(out (char Bracket, int Index) unclosed) ? unclosed.Index : -1;
    }
}

[Theory]
[InlineData("order.Items[0].Price * (1 - discount)", -1)]
[InlineData("{ \"title\": [\"Dune\" }", 19)]
[InlineData("f(a, g(b)", 1)]
[InlineData(")(", 0)]
public void BracketValidator_FindsFirstError(string text, int expected)
{
    Assert.Equal(expected, BracketValidator.FindError(text));
}

İkinci test bozuk bir JSON (JavaScript Object Notation) parçası: [ açılmış ama önce } geliyor, hata index 19'da. Üçüncüsünde kapanmamış ilk parantez index 1'de. Stack, hatanın yerini de söyleyebildiği için kullanıcıya "19. karakterde beklenmeyen }" gibi bir mesaj gösterebiliyorsun. Tek bir sayaçla yapılan kontrol yalnızca tek tip parantezde çalışır; ([)] gibi çapraz bir metni yakalayamaz.

Undo/redo ise iki stack: biri geri alınabilecek durumları, diğeri yeniden yapılabilecekleri tutuyor.

public sealed class EditorHistory(string initial)
{
    private readonly Stack<string> _undo = new();
    private readonly Stack<string> _redo = new();

    public string Text { get; private set; } = initial;

    public void Apply(string newText)
    {
        _undo.Push(Text);
        _redo.Clear(); // yeni bir düzenleme redo dalını geçersiz kılar
        Text = newText;
    }

    public bool Undo()
    {
        if (!_undo.TryPop(out string? previous)) return false;
        _redo.Push(Text);
        Text = previous;
        return true;
    }

    public bool Redo()
    {
        if (!_redo.TryPop(out string? next)) return false;
        _undo.Push(Text);
        Text = next;
        return true;
    }
}

Apply'daki _redo.Clear() satırı unutulursa, kullanıcı geri alıp yeni bir şey yazdıktan sonra "redo" ona hiç yazmadığı bir geleceği geri getirir. Gerçek bir editörde her adımın bütün metni değil yalnızca değişikliği (command) tutması gerekir; aksi hâlde 10.000 adımlık bir history, metnin 10.000 kopyası demek. Command pattern'i Design Patterns serisinde anlatılıyor; buradaki iki stack yapısı aynen kalıyor.

Monotonic Stack: Next Greater ve Stock Span

Stack'in daha az bilinen ama güçlü bir kullanımı var: element'leri belli bir sırada (hep azalan ya da hep artan) tutan bir stack. Bookstore'un fiyat geçmişi ekranı her gün için "fiyat bundan sonra ilk kez hangi gün daha yüksek oldu?" sorusunu soruyor. Her gün için ileriye bakan iç içe bir döngü O(n²); monotonic stack ile O(n):

public static class MonotonicStack
{
    // her gün için fiyatın daha yüksek olduğu sonraki gün; yoksa -1. O(n): her index bir kez push, bir kez pop
    public static int[] NextGreater(int[] prices)
    {
        int[] result = new int[prices.Length];
        Array.Fill(result, -1);
        Stack<int> waiting = new(); // alttan üste fiyatları azalan index'ler
        for (int i = 0; i < prices.Length; i++)
        {
            while (waiting.Count > 0 && prices[waiting.Peek()] < prices[i])
                result[waiting.Pop()] = i;
            waiting.Push(i);
        }
        return result;
    }

    // span: bugüne kadar art arda kaç gün fiyat bugünkünden küçük ya da eşitti
    public static int[] StockSpan(int[] prices)
    {
        int[] span = new int[prices.Length];
        Stack<int> higher = new();
        for (int i = 0; i < prices.Length; i++)
        {
            while (higher.Count > 0 && prices[higher.Peek()] <= prices[i])
                higher.Pop();
            span[i] = higher.Count == 0 ? i + 1 : i - higher.Peek();
            higher.Push(i);
        }
        return span;
    }
}

[Fact]
public void NextGreater_ReturnsIndexOfNextHigherPrice()
{
    int[] prices = [73, 74, 75, 71, 69, 72, 76, 73];

    Assert.Equal([1, 2, 6, 5, 5, 6, -1, -1], MonotonicStack.NextGreater(prices));
}

[Fact]
public void StockSpan_ReturnsConsecutiveLowerOrEqualDays()
{
    int[] prices = [100, 80, 60, 70, 60, 75, 85];

    Assert.Equal([1, 1, 1, 2, 1, 4, 6], MonotonicStack.StockSpan(prices));
}

Fikir şu: stack, henüz cevabını bulamamış günleri tutuyor ve bu günlerin fiyatları alttan üste azalıyor. Yeni bir gün geldiğinde, ondan ucuz olan bütün bekleyen günlerin cevabı bu gün; onlar stack'ten çıkıyor. İç içe bir while olduğu için kod O(n²) gibi görünse de her index stack'e bir kez girip en fazla bir kez çıkıyor. Bütün while döngülerinin toplam iterasyon sayısı n'i geçmiyor. Bu tür "toplam maliyet" sayımı, Big-O ve Complexity serisinin "Amortized Analysis" yazısındaki aggregate method'un ta kendisi.

$ dotnet test --project tests/Algorithms.Tests -- --filter-class Algorithms.Tests.StackQueueTests
tests/Algorithms.Tests/bin/Debug/net10.0/Algorithms.Tests.dll (net10.0|arm64) passed (567ms)

Test run summary: Passed!
  total: 11
  failed: 0
  succeeded: 11

Ölçüm: List.RemoveAt(0) ile Queue

Açılıştaki soruya dönelim. Benchmark N element'i sıraya koyup hepsini sırayla çıkarıyor; üç implementation aynı işi yapıyor:

[Benchmark]
public long ListRemoveAtZero()
{
    List<int> queue = [];
    for (int i = 0; i < N; i++) queue.Add(i);
    long sum = 0;
    while (queue.Count > 0)
    {
        sum += queue[0];
        queue.RemoveAt(0); // kalan her element'i kaydırır: her dequeue O(n)
    }
    return sum;
}

BenchmarkDotNet v0.15.8, macOS 27.0.1 (26A434) [Darwin 27.0.0]
Apple M5, 1 CPU, 10 logical and 10 physical cores
.NET SDK 10.0.402
  [Host] : .NET 10.0.13 (10.0.13, 10.0.1326.50504), Arm64 RyuJIT armv8.0-a

| Method           | N      | Mean           | Ratio  | Allocated  |
|----------------- |------- |---------------:|-------:|-----------:|
| BclQueue         | 1000   |       4.298 us |   1.00 |    8.23 KB |
| OwnCircularQueue | 1000   |       5.876 us |   1.37 |     8.2 KB |
| ListRemoveAtZero | 1000   |      24.514 us |   5.71 |    8.23 KB |
|                  |        |                |        |            |
| BclQueue         | 100000 |     582.184 us |   1.00 | 1024.59 KB |
| OwnCircularQueue | 100000 |     620.533 us |   1.07 | 1024.55 KB |
| ListRemoveAtZero | 100000 | 289,619.803 us | 497.52 | 1024.39 KB |

1.000 siparişte fark 5,7 kat ve 24 µs; kimse fark etmez. 100.000'de List 290 ms, Queue<T> 0,58 ms: 497 kat. List versiyonu her RemoveAt(0)'da kalan bütün element'leri kaydırıyor; toplam kaydırma n²/2 civarında, yani 100.000 için yaklaşık 5 milyar element kopyası. Üç implementation'ın da bellek ayırması aynı (array'in büyümesi), fark tamamen kaydırmadan geliyor. Kendi circular queue'muz BCL'den yüzde 7–37 yavaş; büyük kısmı her adımdaki % operatörü ve BCL'nin bizim yapmadığımız mikro optimizasyonları. Ölçüm makinede başka işler çalışırken alındı; oranlara bak.

Üretimde Dikkat

Bu yazıdaki yapıların hiçbiri thread-safe değil, BCL'deki Stack<T> ve Queue<T> de değil. Birden fazla thread aynı kuyruğa yazıp okuyorsa ConcurrentQueue<T> ya da daha iyisi System.Threading.Channels kullan. Bounded bir channel, burada yazdığımız overflow politikasının production versiyonunu veriyor: BoundedChannelFullMode ile dolunca beklemeyi, en eskiyi ya da en yeniyi atmayı seçiyorsun. Ayrıntılar C# Asenkron serisinin "C# Senkronizasyon: lock, Interlocked, SemaphoreSlim ve Concurrent Collection'lar" ve "C# Channels ile Producer/Consumer" yazılarında.

Sınırsız kuyruk, sınırsız bellek demek. Tüketici üreticiden yavaşsa Queue<T> sonsuza kadar büyür ve process bellek sınırına çarpınca çöker. Production'daki her kuyruğun bir üst sınırı ve o sınıra gelince ne olacağına dair yazılı bir kararı olmalı; bu karar sistemin backpressure davranışı.

Stack'ten gelen bir sıra beklentisine dikkat et. Stack<T>'i foreach ile gezmek ya da ToArray() çağırmak element'leri en üstteki ilk olacak şekilde, yani eklenme sırasının tersiyle verir. Bir stack'i JSON'a çevirip sonra geri yükleyen kod sırayı ters çevirmiş olur.

Sık Düşülen Tuzaklar

Ring buffer'da overflow politikasını belirlememek. "Dolunca ne olacak?" sorusunun cevabı koddaki bir if'in dalında sessizce verilmemeli; enum ile açıkça seçilmeli, düşen element sayısı metrik olarak raporlanmalı.

Boş ile doluyu karıştırmak. Ayrı bir count tutmayan circular buffer'da head == tail iki anlama gelir; "dolu" durumunu yanlışlıkla "boş" sanan kod, kuyruktaki bütün element'leri bir anda kaybeder.

Büyürken halkayı açmamak. Sarılmış bir buffer'ı Array.Copy(_items, bigger, _count) ile tek parça kopyalamak sırayı bozar; test, tam bu durumu yakalamak için yazıldı.

Kuyruk yerine List kullanmak. RemoveAt(0) küçük veride masum görünür; ölçüm 100.000 elemanda 497 kat fark gösterdi. Baştan çıkarılan her yapı için Queue<T> kullan.

Küçük Bir Deneme

★☆☆ CircularQueue<T>'deki % operatörlerini "sona geldiysen sıfırla" kontrolüyle değiştir ve benchmark'ı tekrar çalıştır. BCL ile aradaki fark ne kadar kapanıyor?

★★☆ CircularQueue<T>'yi bir CircularDeque<T>'ye çevir: AddFirst, AddLast, RemoveFirst, RemoveLast. _head'i geri alırken negatif index'i nasıl sararsın? LinkedList<T> ile aynı işlemleri yapan bir test yaz.

★★★ Monotonic stack fikrini "son 30 günün en düşük fiyatı" için kullan: her gün için o güne kadarki 30 günlük pencerenin minimumunu O(n)'de veren bir method yaz. İpucu: iki uçtan da çıkarma gerekiyor, yani deque.

Stack'i bu yazıda kendimiz tuttuk. Bir sonraki yazıda runtime'ın bizim için tuttuğu stack'e bakıyoruz: call stack. Recursion'ın anatomisi, yakalanamayan StackOverflowException ve recursive bir algoritmayı burada yazdığımız gibi açık bir Stack<T> ile iterative'e çevirme tekniği.