1.3.33 #

/// <summary>
/// 双端队列。
/// </summary>
/// <typeparam name="TItem">队列中要存放的元素。</typeparam>
public class Deque<TItem> : IEnumerable<TItem>
{
    private class DoubleNode<T>
    {
        public T Item;
        public DoubleNode<T> Next;
        public DoubleNode<T> Prev;
    }

    private DoubleNode<TItem> _first;
    private DoubleNode<TItem> _last;
    private int _count;

    /// <summary>
    /// 默认构造函数，建立一个双端队列。
    /// </summary>
    public Deque()
    {
        _first = null;
        _last = null;
        _count = 0;
    }

    /// <summary>
    /// 检查队列是否为空。
    /// </summary>
    /// <returns></returns>
    public bool IsEmpty()
    {
        return _count == 0;
    }

    /// <summary>
    /// 返回队列中元素的数量。
    /// </summary>
    /// <returns></returns>
    public int Size()
    {
        return _count;
    }

    /// <summary>
    /// 向左端添加一个元素。
    /// </summary>
    /// <param name="item">要添加的元素。</param>
    public void PushLeft(TItem item)
    {
        var oldFirst = _first;
        _first = new DoubleNode<TItem>
        {
            Item = item,
            Prev = null,
            Next = oldFirst
        };
        if (oldFirst == null)
        {
            _last = _first;
        }
        else
        {
            oldFirst.Prev = _first;
        }
        _count++;
    }

    /// <summary>
    /// 向右端添加一个元素。
    /// </summary>
    /// <param name="item">要添加的元素。</param>
    public void PushRight(TItem item)
    {
        var oldLast = _last;
        _last = new DoubleNode<TItem>
        {
            Item = item,
            Prev = oldLast,
            Next = null
        };

        if (oldLast == null)
        {
            _first = _last;
        }
        else
        {
            oldLast.Next = _last;
        }
        _count++;
    }

    /// <summary>
    /// 从右端删除并返回一个元素。
    /// </summary>
    /// <returns></returns>
    public TItem PopRight()
    {
        if (IsEmpty())
        {
            throw new InvalidOperationException();
        }

        var temp = _last.Item;
        _last = _last.Prev;
        _count--;

        if (_last == null)
        {
            _first = null;
        }
        else
        {
            _last.Next.Item = default;
            _last.Next = null;
        }
        return temp;
    }

    /// <summary>
    /// 从左端删除并返回一个元素。
    /// </summary>
    /// <returns></returns>
    public TItem PopLeft()
    {
        if (IsEmpty())
        {
            throw new InvalidOperationException();
        }

        var temp = _first.Item;
        _first = _first.Next;
        _count--;

        if (_first == null)
        {
            _last = null;
        }
        else
        {
            _first.Prev.Item = default;
            _first.Prev = null;
        }

        return temp;
    }

    public IEnumerator<TItem> GetEnumerator()
    {
        return new DequeEnumerator(_first);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    private class DequeEnumerator : IEnumerator<TItem>
    {
        private DoubleNode<TItem> _current;
        private DoubleNode<TItem> _first;

        public DequeEnumerator(DoubleNode<TItem> first) 
        {
            _current = new DoubleNode<TItem>();
            _current.Next = first;
            _current.Prev = null;
            _first = _current;
        }

        public TItem Current => _current.Item;

        object IEnumerator.Current => _current.Item;

        public void Dispose()
        {
            _current = null;
            _first = null;
        }

        public bool MoveNext()
        {
            if (_current.Next == null)
                return false;
            _current = _current.Next;
            return true;
        }

        public void Reset()
        {
            _current = _first;
        }
    }
}

/// <summary>
/// 可自动扩容的双端队列。
/// </summary>
/// <typeparam name="TItem">队列中要存放的元素。</typeparam>
public class ResizingArrayDeque<TItem> : IEnumerable<TItem>
{
    private TItem[] _deque;
    private int _first;
    private int _last;
    private int _count;

    /// <summary>
    /// 默认构造函数，建立一个双向队列。
    /// </summary>
    public ResizingArrayDeque()
    {
        _deque = new TItem[2];
        _first = 0;
        _last = 0;
        _count = 0;
    }

    /// <summary>
    /// 检查队列是否为空。
    /// </summary>
    /// <returns></returns>
    public bool IsEmpty()
    {
        return _count == 0;
    }

    /// <summary>
    /// 返回队列中元素的数量。
    /// </summary>
    /// <returns></returns>
    public int Size()
    {
        return _count;
    }

    /// <summary>
    /// 为队列重新分配空间。
    /// </summary>
    /// <param name="capacity">需要重新分配的空间大小。</param>
    private void Resize(int capacity)
    {
        if (capacity <= 0)
            throw new ArgumentException();

        var temp = new TItem[capacity];
        for (var i = 0; i < _count; i++)
        {
            temp[i] = _deque[(_first + i) % _deque.Length];
        }
        _deque = temp;
        _first = 0;
        _last = _count;
    }


    /// <summary>
    /// 在队列左侧添加一个元素。
    /// </summary>
    /// <param name="item">要添加的元素</param>
    public void PushLeft(TItem item)
    {
        if (_count == _deque.Length)
        {
            Resize(2 * _count);
        }

        _first--;
        if (_first < 0)
        {
            _first += _deque.Length;
        }
        _deque[_first] = item;
        _count++;
    }

    public void PushRight (TItem item)
    {
        if (_count == _deque.Length)
        {
            Resize(2 * _count);
        }

        _deque[_last] = item;
        _last = (_last + 1) % _deque.Length;
        _count++;
    }

    public TItem PopRight()
    {
        if (IsEmpty())
        {
            throw new InvalidOperationException();
        }

        _last--;
        if (_last < 0)
        {
            _last += _deque.Length;
        }
        var temp = _deque[_last];
        _count--;
        if (_count > 0 && _count == _deque.Length / 4)
            Resize(_deque.Length / 2);
        return temp;
    }

    public TItem PopLeft()
    {
        if (IsEmpty())
            throw new ArgumentException();

        var temp = _deque[_first];
        _first = (_first + 1) % _deque.Length;
        _count--;
        if (_count > 0 && _count == _deque.Length / 4)
        {
            Resize(_deque.Length / 2);
        }
        return temp;
    }

    public IEnumerator<TItem> GetEnumerator()
    {
        return new ResizingDequeEnumerator(_deque, _first, _count);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    private class ResizingDequeEnumerator : IEnumerator<TItem>
    {
        private TItem[] _deque;
        private int _current;
        private readonly int _first;
        private readonly int _count;

        public ResizingDequeEnumerator(TItem[] deque, int first, int count)
        {
            _deque = deque;
            _first = first;
            _count = count;
            _current = -1;
        }

        TItem IEnumerator<TItem>.Current => _deque[(_first + _current) % _deque.Length];

        object IEnumerator.Current => _deque[(_first + _current) % _deque.Length];

        void IDisposable.Dispose()
        {
            _deque = null;
            _current = -1;
        }

        bool IEnumerator.MoveNext()
        {
            if (_current == _count - 1)
            {
                return false;
            }

            _current++;
            return true;
        }

        void IEnumerator.Reset()
        {
            _current = -1;
        }
    }
}

var a = new Deque<string>();
var b = new ResizingArrayDeque<string>();

a.PushLeft("first");
b.PushLeft("first");
a.PushRight("second");
b.PushRight("second");
Display(a, b);

a.PopLeft();
b.PopLeft();
Display(a, b);
a.PopRight();
b.PopRight();
Display(a, b);

static void Display(Deque<string> a, ResizingArrayDeque<string> b)
{
    foreach (var s in a)
    {
        Console.Write(s + " ");
    }

    Console.WriteLine();
    foreach (var s in b)
    {
        Console.Write(s + " ");
    }

    Console.WriteLine();
    Console.WriteLine();
}