[CareerCup][Google Interview] 实现一个具有get_min的Queue - chkkch - 博客园
Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
http://www.careercup.com/question?id=7263132给出了很精彩的解答。
主要的思想是维护一个min_queue，保存当前队列最小值，当新加入一个元素时，min_queue遵照这样的规则
从min_queue的尾部开始和新加入元素（key）比较，当min_queue.back() > key时，弹出back()，直到back()<= key，或者min_queue为空。
当要返回min时，return min_queue.front()
而pop()时，比较queue.front() == min_queue.front()，相等则min_queue.pop_front()
这里，最关键的思想是后来的key和min_queue从后往前比较，能够保证min_queue是一个非降序列，这样就能维护一个当前队列的最小值序列。
分摊下来，每个操作O(1)
Read full article from [CareerCup][Google Interview] 实现一个具有get_min的Queue - chkkch - 博客园
