1.4.27

1.4.27 #

解答 #

实现比较简单，想象两个栈背靠背接在一起，左侧栈负责出队，右侧栈负责入队。

当左侧栈为空时就把右侧栈中的元素倒到左侧栈，这个过程是 O(n) 的。

但在这个过程之前必然有 n 个元素入栈，均摊后即为 O(1)。

代码 #

internal class StackQueue<TItem>
{
    private readonly Stack<TItem> _h;// 用于保存出队元素
    private readonly Stack<TItem> _;// 用于保存入队元素

    /// <summary>
    /// 构造一个队列。
    /// </summary>
    public StackQueue()
    {
        _h = new Stack<TItem>();
        _ = new Stack<TItem>();
    }

    /// <summary>
    /// 将栈 T 中的元素依次弹出并压入栈 H 中。
    /// </summary>
    private void Reverse()
    {
        while (!_.IsEmpty())
        {
            _h.Push(_.Pop());
        }
    }

    /// <summary>
    /// 将一个元素出队。
    /// </summary>
    /// <returns></returns>
    public TItem Dequeue()
    {
        // 如果没有足够的出队元素，则将 T 中的元素移动过来
        if (_h.IsEmpty())
        {
            Reverse();
        }

        return _h.Pop();
    }

    /// <summary>
    /// 将一个元素入队。
    /// </summary>
    /// <param name="item">要入队的元素。</param>
    public void Enqueue(TItem item)
    {
        _.Push(item);
    }
}