Can you design a data structure just like a queue which contains 'enqueue', 'dequeue' 'minimum' and 'maximum'? I know a method to make a queue using 2 stacks to find the minimum and maximums respectively, but how can I get both simultaneously?
Thanks
Using standard containers, a completely ordered data structure like a std::set will provide access to both extrema, e.g. using *s.begin() and *s.rbegin(). If you have multiple objects of the same priority, you might want to break ties in an arbitrary fashion, or use a std::multiset instead.
Most implementations will probably use some form of red-black tree for the implementation of such a set. As the data structure will be kept sorted at all times, asymptotic performance might be worse than what a regular single-ended heap-based priority queue would give you, but for many applications the difference isn't crucial, and so the effort of implementing a custom data structure should be avoided.
Using Priority Queue!
C++ STL
#include<queue> Usually, priority queue is implemented by Binary-Heap. But it cannot maintain the maximum value and minimum value simultaneously. @_@
Maybe Balanced Search Tree, such as AVL, Splay, or Red-Black Tree should be a better choice.
Usually a priority queue is implemented using some kind of heap structure. There is a variation called a min-max heap which allows for constant-time access to both the maximum and the minimum element. There already is a question asking for C++ implementations of such a min-max heap. Its answers should prove useful to you as well.
This comment by Paul Dixon first mentioned min-max heaps, whereas this comment by Chris Mansley pointed out the implementation question on Stack Overflow.
The data structure is a well known structure called a Priority Queue. Each element in the queue has an associated priority, and the queue is kept in high to low sorted order.
Each element in the queue must carry a a priority, and the code must maintain the order contract.
Some STLs contain Priority Queue Implementations, though now that i look at it i am uncertain if the whole queue is kept in priority order.
You can store both the minimum stack and the maximum stack at once - and so on for each stack. This is victory. You can also make an implementation with two decks and one queue. Push into the queue: we push into the normal one, from the beginning of the deck of minimums we remove elements that are larger than the one we threw in (maybe all the elements of the deck). Then we put our element at the beginning of the deck. Pop from the queue: see if our element is equal to the minimum in the deck (and the minimum will always be at the end of the deck). If it is equal, then we also remove it from the deck, otherwise we leave it. Same with the maximum.
