1.4.29

1.4.29 #

解答 #

和用两个栈实现队列的方法类似。

push 的时候把右侧栈内容倒到左侧栈，之后再入栈。

pop 的时候也做相同操作，右侧栈内容进左侧栈，之后再出栈。

enqueue 的时候则将左侧栈内容倒到右侧栈，之后再入队。

代码 #

internal class StackSteque<TItem>
{
    private readonly Stack<TItem> _h;
    private readonly Stack<TItem> _t;

    /// <summary>
    /// 初始化一个 Steque
    /// </summary>
    public StackSteque()
    {
        _h = new Stack<TItem>();
        _t = new Stack<TItem>();
    }

    /// <summary>
    /// 向栈中添加一个元素。
    /// </summary>
    /// <param name="item"></param>
    public void Push(TItem item)
    {
        ReverseT();
        _h.Push(item);
    }

    /// <summary>
    /// 将 T 中的元素弹出并压入到 H 中。
    /// </summary>
    private void ReverseT()
    {
        while (!_t.IsEmpty())
        {
            _h.Push(_t.Pop());
        }
    }

    /// <summary>
    /// 将 H 中的元素弹出并压入到 T 中。
    /// </summary>
    private void ReverseH()
    {
        while (!_h.IsEmpty())
        {
            _t.Push(_h.Pop());
        }
    }

    /// <summary>
    /// 从 Steque 中弹出一个元素。
    /// </summary>
    /// <returns></returns>
    public TItem Pop()
    {
        ReverseT();
        return _h.Pop();
    }

    /// <summary>
    /// 在 Steque 尾部添加一个元素。
    /// </summary>
    /// <param name="item"></param>
    public void Enqueue(TItem item)
    {
        ReverseH();
        _t.Push(item);
    }

    /// <summary>
    /// 检查 Steque 是否为空。
    /// </summary>
    /// <returns></returns>
    public bool IsEmpty()
    {
        return _h.IsEmpty() && _t.IsEmpty();
    }
}