using System;

namespace zad1
{
    public class AuxClass<T>
    {
        public AuxClass<T> prev;
        public AuxClass<T> next;
        public T val;

        public AuxClass(T a)
        {
            prev = null;
            next = null;
            val = a;
        }
    }

    public class Lista<T>
    {
        protected AuxClass<T> first;
        protected AuxClass<T> last;
        protected int size;
        public Lista()
        {
            first = null;
            last = null;
            size = 0;
        }

        public int Size()
        {
            return size;
        }

        public bool IsEmpty()
        {
            if (size == 0) return true;
            return false;
        }

        public void AddFirst(T element)
        {
            AuxClass<T> v = new AuxClass<T>(element);
            if (this.IsEmpty())
            {
                first = v;
                last = v;
            }
            else
            {
                first.prev = v;
                v.next = first;
                first = v;
            }
            size++;
        }
        public void AddLast(T element)
        {
            AuxClass<T> v = new AuxClass<T>(element);
            if (this.IsEmpty())
            {
                first = v;
                last = v;
            }
            else
            {
                last.next = v;
                v.prev = last;
                last = v;
            }
            size++;
        }

        public T RemoveFirst()
        {
            if (this.Size() == 1)
            {
                T element = first.val;
                first = null;
                last = null;
                size = 0;
                return element;
            }
            else
            {
                AuxClass<T> v = first;
                first = first.next;
                first.prev = null;
                size -= 1;
                return v.val;
            }
        }
        public T RemoveLast()
        {
            if (this.Size() == 1)
            {
                T element = last.val;
                first = null;
                last = null;
                size = 0;
                return element;
            }
            AuxClass<T> v = last;
            last = last.prev;
            last.next = null;
            size -= 1;
            return v.val;
        }

        public class AuxClass<K,V>
        {
            K tab[] a = new tab[50];
        }

    class Program
    {
        static void Main()
        {
            Lista<int> lista = new Lista<int>();

            lista.AddFirst(3);
            lista.AddLast(4);
            lista.AddFirst(2);
            lista.AddLast(5);
            lista.AddFirst(1);
            lista.AddLast(6);
            Console.WriteLine(lista.RemoveFirst());
            Console.WriteLine(lista.RemoveFirst());
            Console.WriteLine(lista.RemoveFirst());
            Console.WriteLine(lista.RemoveLast());
            Console.WriteLine(lista.RemoveLast());
            Console.WriteLine(lista.RemoveLast());
        }
    }
}