queue

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

    public class StackQueue<T> : IQueue<T>
    {
        private readonly Stack<T> _stack1 = new Stack<T>();
        private readonly Stack<T> _stack2 = new Stack<T>();

        public void Enqueue(T value)
        {
            _stack1.Push(value);
        }

        public T Dequeue()
        {
            if (_stack2.Count == 0 && _stack1.Count == 0)
            {
                throw new InvalidOperationException("Queue is empty");
            }

            while (_stack1.Count != 0)
            {
                _stack2.Push(_stack1.Pop());
            }

            return _stack2.Pop();
        }
    }

    // + lower memory
    // - max elements in queue equals max elements in array, if need more, we will created new array and copy old to new
    public class ArrayQueue<T> : IQueue<T>
    {
        public int Capacity { get; set; }
        public int Length { get; set; }
        public int FrontIndex { get; set; }

        public int BackIndex
        {
            get
            {
                return (FrontIndex + Length) % Capacity;
            }
        }

        protected T[] Elements { get; set; }

        public ArrayQueue(int capacity = 10)
        {
            Capacity = capacity;
            Elements = new T[Capacity];
        }

        public void Enqueue(T element)
        {
            if (Length == Capacity)
            {
                IncreaseCapacity();
            }
            Elements[BackIndex] = element;
            Length++;
        }

        public T Dequeue()
        {
            if (Length < 1)
            {
                throw new InvalidOperationException("Queue is empty");
            }
            T element = Elements[FrontIndex];
            Elements[FrontIndex] = default(T);
            Length--;
            FrontIndex = (FrontIndex + 1) % Capacity;
            return element;
        }

        protected void IncreaseCapacity()
        {
            Capacity++;
            Capacity *= 2;
            ArrayQueue<T> tempQueue = new ArrayQueue<T>(Capacity);
            while (Length > 0)
            {
                tempQueue.Enqueue(Dequeue());
            }
            Elements = tempQueue.Elements;
            Length = tempQueue.Length;
            FrontIndex = tempQueue.FrontIndex;
        }
    }


    // + Dinamic size
    // - More memory, slowled work 
    public class LinkedQueue<T> : IQueue<T>
    {
        public class Element<T>
        {
            public Element<T> NextElement { get; set; }
            public T Value { get; set; }

            public Element(T value)
            {
                Value = value;
            }
        }

        private Element<T> headElement;
        private Element<T> tailElement;

        public void Enqueue(T value)
        {
            var newElement = new Element<T>(value);

            if (headElement == null)
            {
                headElement = tailElement = newElement;
            }
            else
            {
                tailElement.NextElement = newElement;
                tailElement = newElement;
            }
        }

        public T Dequeue()
        {
            if (headElement == null)
            {
                throw new NullReferenceException("queue is empty");
            }

            var result = headElement.Value;
            headElement = headElement.NextElement;

            return result;
        }
    }