Veri Yapıları - Yığın (Stack)Beğen

Veri yapılarındaki temel öğelerden biri de yığınlardır. Yığınları, tıpkı altı kapalı koliler gibi düşünebiliriz. İlk eklediğiniz nesneyi çıkarabilmek için daha sonra eklediğiniz nesnelerin hepsini önce çıkarmanız gerekir. Özetle, ilk giren son çıkar, son giren ilk çıkar. Yığın için gerçekleştirmemiz gereken ara yüz aşağıdaki gibidir.

    public interface IStack<T>
    {
        void Push(T value);
        T Pop();
    }

Bu arayüzü iki farklı şekilde gerçekleştirebildim.

1. Sabit bir dizi ile:

Bir dizi kullanarak sadece son eleman indisini tutarak aşağıdaki gibi basitçe gerçekleştirdim. Bu yapının dezavantajı ise yığın kapasitesinin değiştirilemez olmasıdır.

    internal class FixedStack<T> : IStack<T>
    {
        private readonly T[] _stack;
        private int _last;

        public FixedStack(int size)
        {
            _stack = new T[size];
        }

        public T Pop()
        {
            if (_last == 0)
                throw new NotSupportedException("Stack is empty!");

            return _stack[--_last];
        }

        public void Push(T value)
        {
            if (_last == _stack.Length)
                throw new NotSupportedException("Stack is full!");

            _stack[_last] = value;
            _last++;
        }

        public override string ToString()
        {
            var str = "";
            for (int i = _last - 1; i > -1; i--)
            {
                str += $"{_stack[i]}, ";
            }
            return str.Trim().Trim(',');
        }
    }

2. Bağlı liste ile:

Bağlı liste ile aşağıdaki gibi sınırsız bir yığın nesnesi tasarladım. Node sınıfı her bir elemanı temsil ediyor. Değer ve sonraki işaretleyicisine sahip. 

    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; }
    }

    public class Stack<T> : IStack<T>
    {
        Node<T> _last;

        public T Pop()
        {
            if (_last == null)
            {
                throw new NotSupportedException("Stack is empty!");
            }

            var val = _last.Value;
            _last = _last.Next;
            return val;
        }

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

        public override string ToString()
        {
            var str = "";
            var curr = _last;
            if (curr == null)
                return str;
            do
            {
                str += $"{curr.Value}, ";
                curr = curr.Next;
            } while (curr != null);

            return str.Trim().Trim(',');
        }
    }

Sonrasında bu iki sınıfı aşağıdaki metot yardımıyla test ettim.

        private static void TryStack(IStack<short> stack)
        {
            var random = new Random();

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

            const int OpCount = 100;
            for (short i = 0; i < OpCount; i++)
            {
                var op = random.Next(2); //randomly push or pop

                try
                {
                    if (op % 2 == 0)
                    {
                        Console.WriteLine($"Trying to add {i} to the stack.");
                        stack.Push(i);
                        Console.WriteLine($"{i} added to the stack.");
                    }
                    else
                    {
                        Console.WriteLine($"Trying to pop...");
                        var val = stack.Pop();
                        Console.WriteLine($"Popped item:{val}");
                    }
                }
                catch (NotSupportedException ex)
                {
                    Console.WriteLine(ex.Message);
                }

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

            Console.WriteLine("Trying linkedlist stack...");
            var stack = new Stack<short>();
            TryStack(stack);

            Console.WriteLine("Trying fixed stack...");
            var fixedStack = new FixedStack<short>(5);
            TryStack(fixedStack);

Kaynak kodların tümüne buradan ulaşabilirsiniz.