首页 > 代码库 > 编程之美---队列中取最大值操作问题

编程之美---队列中取最大值操作问题

2024-08-07 18:15:44   220人阅读

如何快速获取队列中的最大值？

最简单的办法，用一个for循环遍历，复杂度为o(n).

解法二：用大顶堆来实现，复杂度为哦o(1),但是入队和出队复杂度变为o(logN),堆中的每一个元素还得有个指针指向它的后继元素。

解法三：可以使用两个栈来模拟队列，从右边的栈进入元素相当于入队，出队时，只有当左边的栈为空时，才把右边栈的元素全部出栈到左边的栈。

 1 class stack 2 { 3 public: 4     stack() 5     { 6         stackTop = -1; 7         maxItemIndex = -1; 8     }  9     void Push(int x)10     {11         stackTop ++;12         if(stackTop >= MAXN) 13             ;14         else15         {16             items[stackTop]=x;17             if(x>Max())18             {19                 nextMaxItem[stackTop] = maxItemIndex;20                 maxItemIndex = stackTop;21             }22             else nextMaxItem[stackTop] = -1;23         }24     } 25     int Pop()26     {27         int x;28         if(stackTop < 0) return -1;29         else30         {31             x = items[stackTop];32             if(stackTop == maxItemIndex)33             {34                 maxItemIndex = nextMaxItem[stackTop];35             }36             stackTop--;37         }38         return x;39     } 40     int Max()41     {42         if(maxItemIndex >= 0) return items[maxItemIndex];43         else return -1;44     } 45     bool empty()46     {47         return stackTop == -1;48     }  49 private:50     int items[MAXN];51     int stackTop;52     int nextMaxItem[MAXN];53     int maxItemIndex;54 };55 class Queue56 {57 public:58     void Enqueue(int x)59     {60         B.Push(x);61     } 62     int Dequeue()63     {64         if(A.empty())65         {66             while(!B.empty())67             {68                 A.Push(B.Pop());69             }70         }71         return A.Pop();72     } 73     int Max()74     {75         if(A.Max() >= B.Max()) return A.Max();76         else return B.Max();77     } 78     private:79     stack A;80     stack B;81 };
View Code

 

编程之美---队列中取最大值操作问题


联系
我们