1.4.27

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

实现比较简单,想象两个栈背靠背接在一起,左侧栈负责出队,右侧栈负责入队。
当左侧栈为空时就把右侧栈中的元素倒到左侧栈,这个过程是 O(n) 的。
但在这个过程之前必然有 n 个元素入栈,均摊后即为 O(1)。

代码

namespace _1._4._27
{
    /// <summary>
    /// 用两个栈模拟的队列。
    /// </summary>
    /// <typeparam name="Item">队列中的元素。</typeparam>
    class StackQueue<Item>
    {
        Stack<Item> H;//用于保存出队元素
        Stack<Item> T;//用于保存入队元素

        /// <summary>
        /// 构造一个队列。
        /// </summary>
        public StackQueue()
        {
            this.H = new Stack<Item>();
            this.T = new Stack<Item>();
        }

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

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

            return this.H.Pop();
        }

        /// <summary>
        /// 将一个元素入队。
        /// </summary>
        /// <param name="item">要入队的元素。</param>
        public void Enqueue(Item item)
        {
            this.T.Push(item);
        }
    }
}
上一题 下一题