LeetCode:实现队列与栈的高级应用

队列的实现与平均值计算

在某些应用场景中，我们需要一个能够动态添加和移除元素的队列，并且每次操作后都需要计算当前队列中所有元素的平均值。为了实现这一需求，我们可以设计一个名为 AvgLoadWindow 的类，该类包含以下功能：

• 初始化时设置队列的最大容量。
• 支持向队列中添加新元素。
• 当队列已满时，自动移除最早的元素。
• 每次添加或移除元素后，重新计算并返回当前队列中所有元素的平均值。

class AvgLoadWindow { public:     int size;     explicit AvgLoadWindow(int s) : size(s), sum(0) {}     queue q;     double sum;     double Next(int val) {         if (q.size() == size) {             sum -= q.front();             q.pop();         }         q.push(val);         sum += val;         return sum / q.size();     } };

通过这种方式，我们可以在保证队列长度不超过设定值的同时，高效地计算出队列中所有元素的平均值。

栈的操作优化

对于栈的操作，尤其是涉及到取栈顶元素时，必须确保栈不为空以避免运行时错误。此外，单调栈是一种特殊的栈结构，它能帮助我们在处理如“下一个更大元素”等问题时更加高效。以下是几个关键点：

• 在访问栈顶元素之前，应先检查栈是否为空。
• 使用单调栈可以简化一些复杂问题的求解过程，例如寻找数组中每个元素右侧第一个比它大的元素。