问题:设计一个队列能够在O(1)时间内取得队列的最大值。
分析:
这个问题和设计一个在O(1)时间内取最大值的堆栈看似比较相似,但实现难度要比最大值的堆栈困难一些,开始想模仿最大值堆栈的思想来设计取最大值的堆栈都失败了。实际上这个问题可以拆分成两个问题:
1)设计一个在O(1)时间内取最大值的堆栈;
2)如何使用堆栈来实现一个队列;
如果这两个问题解决了,O(1)时间取最大值的队列也就解决了,这体现了把一个困难的问题,分解为几个比较简单的问题,分步骤处理的思想。
首先看第一个问题:设计一个在O(1)时间内取最大值的堆栈是比较容易的,我们可以使用两个堆栈来保存数据,其中一个保存正常的数据,另一个保存最大值,最大值堆栈在压栈前需要比较待压栈的元素与栈顶元素的大小,如果比栈顶大,那么是一个新的最大值,应该压入栈,否则保持当前最大值不变,也就是不压栈。弹出数据时,如果弹出的值和最大值栈的栈顶元素相同,说明最大值被弹出,此时最大值栈也应该跟着出栈,这样可以保持最大值的更新。
再看第二个问题,可以使用两个栈来实现一个队列,队列push时,将数据压入A栈中,Pop数据时,如果B栈为空,将A栈的数据Pop出来,压入B栈中,再Pop B栈的数据;当队列Pop时,如果B栈的数据不为空,则直接Pop B栈的数据。
取队列的Max就是取A栈和B栈的Max,而A、B栈都是我们刚才实现的最大值栈,他们取最大值的时间都是O(1),因此队列取最大值复杂度也是O(1)。但实现是要注意A、B栈有可能为空,在我们的实现中,对于空栈取最大值是未定义的,因此在对A、B栈取最大值时要先判断是否为空栈。
最后从复杂度来说,队列的Pop操作最坏情况是将A栈的数据都压入B栈,在Pop B栈的数据,最差是O(n),实际多数情况都是O(1)。
总结一下:这个问题,非常明显的体现了如何将一个新问题转成两个已知的简单问题,同时MaxStack的实现封装了复杂性,使得后面的实现更加简单。
代码如下:
#include <stdio.h> #include <queue> #include <stack> template<typename T> class MaxStack { public: void Push(const T& value) { data_.push(value); if (max_element_.empty()) { max_element_.push(value); } else if (value >= max_element_.top()) { max_element_.push(value); } } T Top() { return data_.top(); } void Pop() { if (data_.top() == max_element_.top()) { max_element_.pop(); } data_.pop(); } bool Empty() { return data_.empty(); } T Max() { if (!max_element_.empty()) { return max_element_.top(); } } private: std::stack<T> data_; std::stack<T> max_element_; }; template<typename T> class MaxQueue { public: void Push(const T& value) { push_stack_.Push(value); } T Front() { if (pop_stack_.empty()) { while (!push_stack_.Empty()) { pop_stack_.Push(push_stack_.Top()); push_stack_.Pop(); } } return pop_stack_.Top(); } void Pop() { if (pop_stack_.Empty()) { while (!push_stack_.Empty()) { pop_stack_.Push(push_stack_.Top()); push_stack_.Pop(); } } pop_stack_.Pop(); } bool IsEmpty() { return push_stack_.Empty() && pop_stack_.Empty(); } T Max() { if (!push_stack_.Empty() && !pop_stack_.Empty()) { return push_stack_.Max() > pop_stack_.Max() ? push_stack_.Max() : pop_stack_.Max(); } else if (push_stack_.Empty() && !pop_stack_.Empty()) { return pop_stack_.Max(); } else if (!push_stack_.Empty() && pop_stack_.Empty()) { return push_stack_.Max(); } else { // throw RUNTIME_ERROR; } } private: MaxStack<T> push_stack_; MaxStack<T> pop_stack_; }; int main(int argc, char** argv) { MaxQueue<int> max_queue; max_queue.Push(1); max_queue.Push(2); max_queue.Push(6); max_queue.Push(4); max_queue.Push(5); max_queue.Push(2); printf("max %d\n", max_queue.Max()); max_queue.Pop(); printf("max %d\n", max_queue.Max()); max_queue.Pop(); printf("max %d\n", max_queue.Max()); max_queue.Pop(); printf("max %d\n", max_queue.Max()); max_queue.Pop(); printf("max %d\n", max_queue.Max()); max_queue.Pop(); printf("max %d\n", max_queue.Max()); }
参考文献:
编程之美3.7