《编程之美》-取队列中的最大值

时间：2010-09-05 来源：小伦

题目：设计一种数据结构和算法，让取队列最大值的操作的事件复杂度降到最低。

对于栈来讲，Push和Pop均是在栈顶完成的，所以很容维护最大值，而且他的时间复杂度是O(1),基本实现如下所示：

实现代码：

1.栈类：

代码

 /// <summary>
    /// 堆栈类
    /// </summary>
    public class MyStack
    {
        private int _capacity;
        private int[] _stackItems;
        private int _maxStackItemIndex;
        private int _stackTop;
        private int[] _link2NextMaxitem;

        public MyStack(int capacity)
        {
            _capacity = capacity;
            _stackTop = -1;
            _maxStackItemIndex = -1;
            _link2NextMaxitem = new int[_capacity];
            _stackItems = new int[_capacity];
        }

        /// <summary>
        /// 将元素压入堆栈
        /// </summary>
        /// <param name="item"></param>
        public void Push(int item)
        {
            _stackTop++;
            if (_stackTop >= _capacity)
            {
 
            }
            else
            {
                _stackItems[_stackTop] = item;
                //维护列表,绝妙之处
                if (item > Max())
                {
                    _maxStackItemIndex = _stackTop;
                    _link2NextMaxitem[_stackTop] = _maxStackItemIndex;

                  
                }
                else//这里就不记录_maxStackItemIndex了，这样保证了_maxStackItemIndex记录的是最大值
                    _link2NextMaxitem[_stackTop] = -1;

            }
        }

        /// <summary>
        /// 从堆栈中弹出元素
        /// </summary>
        /// <returns></returns>
        public int Pop()
        {
            int rt = 0;
            if (_stackTop < 0)
                throw new Exception("Queue is null");

            rt = _stackItems[_stackTop];
            //维护列表
            if (_stackTop == _maxStackItemIndex)
            {
                _maxStackItemIndex = _link2NextMaxitem[_stackTop];
            }
            _stackTop--;
            return rt;
        }

        /// <summary>
        /// 取堆栈中的最大值
        /// </summary>
        /// <returns></returns>
        public int Max()        
        {
            if (_maxStackItemIndex >= 0)
                return _stackItems[_maxStackItemIndex];
            else
                return -1;
        }

        public bool IsEmpty()
        {
            return _stackTop == -1;
        }
     
    }

栈能够有效的实现队列，而且栈的取最大值的操作又很容，所以队列的取最大值的操作可以很容易完成了，考虑使用两个栈来实现队列：

（队列入队的实现：利用栈B入栈所有元素；队列出队的实现：将栈B中的元素放入栈A，对栈A进行出栈操作正好满足队列元素的出队顺序要求）

2.队列类(使用了1中定义的堆栈类作为队列的底层数据结构来实现)：

代码

  /// <summary>
    /// 队列类
    /// </summary>
    public class MyQueue
    {
        //利用堆栈与队列的相似性，用两个堆栈来实现队列
        private MyStack _stacka;
        private MyStack _stackb;

        public MyQueue(int capacity)
        {
            _stacka = new MyStack(capacity);
            _stackb = new MyStack(capacity);
        }

        public void Enqueue(int item)
        {
            _stackb.Push(item);
        }

        public int Dequeue()
        {
            if (_stacka.IsEmpty())
            {
                while (!_stackb.IsEmpty())
                    _stacka.Push(_stackb.Pop());
            }
            return _stacka.Pop();
        }

        public int Max()
        {
            return Math.Max(_stacka.Max(), _stackb.Max());
        }
    }

采用了C#语言实现，思想归《编程之美》作者所有，头脑风暴一下，欢迎拍砖！