1.3.32

1.3.32 #

解答 #

在队列的基础上增加一个在队首插入元素的方法即可。

代码 #

Steque.cs #

/// <summary>
/// Steque。
/// </summary>
/// <typeparam name="TItem">Steque 中要存放的元素。</typeparam>
public class Steque<TItem> : IEnumerable<TItem>
{
    private Node<TItem> _first;
    private Node<TItem> _last;
    private int _count;

    private class Node<T>
    {
        public T Item;
        public Node<T> Next;
    }

    /// <summary>
    /// 默认构造函数。
    /// </summary>
    public Steque()
    {
        _first = 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 Push(TItem item)
    {
        var oldFirst = _first;
        _first = new Node<TItem>();
        _first.Item = item;
        _first.Next = oldFirst;

        if (oldFirst == null)
        {
            _last = _first;
        }
        _count++;
    }

    /// <summary>
    /// 将一个元素从栈中弹出,返回弹出的元素。
    /// </summary>
    /// <returns></returns>
    public TItem Pop()
    {
        if (IsEmpty())
            throw new InvalidOperationException("Stack Underflow");
        var item = _first.Item;
        _first = _first.Next;
        _count--;
        if (_count == 0)
        {
            _last = null;
        }
        return item;
    }

    /// <summary>
    /// 将一个元素加入队列中。
    /// </summary>
    /// <param name="item">要入队的元素。</param>
    public void Enqueue(TItem item)
    {
        var oldLast = _last;
        _last = new Node<TItem>();
        _last.Item = item;
        _last.Next = null;
        if (IsEmpty())
            _first = _last;
        else
            oldLast.Next = _last;
        _count++;
    }

    /// <summary>
    /// 返回栈顶元素(但不弹出它)。
    /// </summary>
    /// <returns></returns>
    public TItem Peek()
    {
        if (IsEmpty())
            throw new InvalidOperationException("Stack Underflow");
        return _first.Item;
    }

    public override string ToString()
    {
        var s = new StringBuilder();
        foreach (var n in this)
        {
            s.Append(n);
            s.Append(' ');
        }
        return s.ToString();
    }

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

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

    private class StackEnumerator : IEnumerator<TItem>
    {
        private Node<TItem> _current;
        private Node<TItem> _first;

        public StackEnumerator(Node<TItem> first)
        {
            _current = new Node<TItem>();
            _current.Next = first;
            _first = _current;
        }

        TItem IEnumerator<TItem>.Current => _current.Item;

        object IEnumerator.Current => _current.Item;

        void IDisposable.Dispose()
        {
            _current = null;
            _first = null;
        }

        bool IEnumerator.MoveNext()
        {
            if (_current.Next == null)
                return false;

            _current = _current.Next;
            return true;
        }

        void IEnumerator.Reset()
        {
            _current = _first;
        }
    }
}

program.cs #

// 见 Steque.cs
var steque = new Steque<string>();
steque.Push("first");
steque.Push("second");
steque.Push("third");
steque.Enqueue("fourth");
Console.WriteLine(steque.ToString());
steque.Pop();
steque.Pop();
steque.Pop();
steque.Pop();
Console.WriteLine(steque.ToString());
steque.Enqueue("first");
steque.Push("zero");
Console.WriteLine(steque.ToString());