Veri Yapıları - Kuyruk (Queue)Beğen

Veri yapılarının temel elementlerinden kuyruk (queue) elementini C# ile gerçekleştirmek istiyorum. Kuyruk, kuyruğa yeni bir eleman ekleme ve kuyruktan eleman çıkarma gibi 2 temel işleve sahip ve gerçek hayatta olduğu gibi kuyruğa ilk giren eleman ilk, son giren eleman son çıkmalı. Aşağıdaki gibi genel bir ara yüz (generic interface) yazıp gerçekleştirmeye çalıştım.

    public interface IQueue<T>
    {
        T Dequeue();
        void Enqueue(T value);
    }

Bu ara yüzü 2 farklı yaklaşımla gerçekleştirebiliriz:

1. Sabit boyutlu dizi ile:

Dizi kullanacağımız için dizi boyutunu en basta belirlememiz gerekiyor. Aşağıdaki gibi gerçekleştirdim. Burada diziyi döngüsel şekilde kullandım.

    public class FixedQueue<T> : IQueue<T> 
    {
        private readonly T[] _queue;
        private bool _isFull;
        private int _first;
        private int _last;

        public FixedQueue(int size)
        {
            _queue = new T[size];
            _isFull = false;
        }

        public T Dequeue()
        {
            if (!_isFull && _first == _last)
                throw new NotSupportedException("Queue is empty!");

            var value = _queue[_first];
            _first++;
            _first %= _queue.Length;
            _isFull = false;
            return value;
        }

        public void Enqueue(T value)
        {
            if (_isFull)
                throw new NotSupportedException("Queue is full!");
            _queue[_last] = value;
            _last++;
            _last %= _queue.Length;

            if (_last == _first)
                _isFull = true;
        }

        public override string ToString()
        {
            var str = "";
            if (!_isFull && _first == _last)
                return str;
            var index = _first;
            do
            {
                str += $"{_queue[index]}, ";
                index++;
                index %= _queue.Length;
            } while (index != _last);
            return str.Trim().Trim(',');
        }
    }

2. Bağlı liste ile:

Bu şekilde işaretleyici (pointer) kullanarak gerçekleştirdiğimiz için kuyruğumuzun herhangi bir sınırı olmayacaktır. Aşağıdaki gibi tanımlanabilir.

    internal class Node<T> 
    {
        private readonly T _value;

        public Node(T value)
        {
            _value = value;
        }

        private Node<T> _next;

        public T Value => _value;

        internal Node<T> Next { get => _next; set => _next = value; }
    }

Yukarıdaki gibi değeri ve kendisinden sonraki elemanı işaretleyen bir Node sınıfı kullanarak ve

    public class Queue<T> : IQueue<T>
    {
        private Node<T> _first;
        private Node<T> _last;

        public T Dequeue()
        {
            if (_first == null)
                throw new NotSupportedException("Queue is empty!");
            if (_first == _last)
            {
                _last = null;
            }
            var value = _first.Value;
            _first = _first.Next;
            return value;
        }

        public void Enqueue(T value)
        {
            var node = new Node<T>(value);
            if (_first == null)
                _first = node;
            if (_last == null)
                _last = node;
            else
            {
                _last.Next = node;
                _last = node;
            }
        }

        public override string ToString()
        {
            var str = "";
            var curr = _first;

            if (curr == null)
                return str;
            do
            {
                str += $"{curr.Value}, ";
                curr = curr.Next;
            } while (curr != null);
            return str.Trim().Trim(',');
        }
    }

Son olarak, bu 2 farklı kuyruk sınıfını aşağıdaki gibi rastgele doldur-boşalt yapan bir metot oluşturarak denedim ve doğru çalıştığını gördüm.

        private static void TryQueue(IQueue<short> queue)
        {
            var random = new Random();

            Console.WriteLine($"Display the queue: {queue}\n");

            const int OpCount = 100;
            for (short i = 0; i < OpCount; i++)
            {
                var op = random.Next(2); //randomly enqueue or dequeue
                try
                {
                    if (op % 2 == 0)
                    {
                        Console.WriteLine($"Trying to add {i} to the queue.");
                        queue.Enqueue(i);
                        Console.WriteLine($"{i} added to the queue.");
                    }
                    else
                    {
                        Console.WriteLine($"Trying to dequeue...");
                        short val = queue.Dequeue();
                        Console.WriteLine($"Dequeued item:{val}");
                    }
                }
                catch (NotSupportedException ex)
                {
                    Console.WriteLine(ex.Message);
                }


                Console.WriteLine($"Display the queue: {queue}\n");
            }
        }

Aşağıdaki gibi kullandım.

            Console.WriteLine("Trying linkedlist queue...");
            var queue = new Queue<short>();
            TryQueue(queue);

            Console.WriteLine("Trying fixed queue...");
            var fixedQueue = new FixedQueue<short>(5);
            TryQueue(fixedQueue);

Bu yapılar zaten .net içerisinde yerleşik (built-in) olarak geliyor ancak burada amaç içerikte nasıl gerçekleştirilir onu göstermekti. Örnek uygulama kodlara buradan ulaşabilirsiniz.