@Ross: I was thinking about this same question 6 months ago. I never posted thoughts anywhere, but here's my solution using 1 Queue and 1 Double Ended Queue. You would never have seen this solution before on the internet. Hence, I claim authorship. :D
Also, somebody posted this question on StackOverflow: http://stackoverflow.com/questions/4802038/implement-a-queue-in-which-push-rear-pop-front-and-get-min-are-all-constan (BTW, who's Bits?). Solution description: Maintain a normal FIFO queue for the elements (q) Maintain a double ended queue (or deque) for the min values (dq) The double ended queue is maintained using the following invariant: All elements in the queue are in weak increasing order (that is, duplicates are retained - eg. 3,3,4, 5,6 is a valid queue). The operations are: Enqueue(element): 1. q.push_rear(element); 2. While(element < dq.rear()) { dq.pop_rear(); } // This is an amortized operation which retains complexity to O(1) 3. dq.push_rear(element); Dequeue(element): 1. if(q.front() == dq.front()) { dq.pop_front(); } 2. q.pop_front(); FindMin(): 1. return dq.front(); Explanation: The deque is acting like a maintenance data structure. Whenever an element is inserted into the deque, the deque is altered such that the element is placed such that it is the min_value from the index of the previous element in dq to the current end of the queue. The elements in the deque thus in some sense maintain information about the ranges of the queue in which they are the min elements. This also allows us to support an interesting bonus operation: Bonus: If you associate a non-decreasing integer (something like an element number) with every element being inserted into the datastructure, you can answer the question: "what will be the minimum value associated with the queue if only deletions take place and the element e becomes the head of the queue?" or "What is the minimum element associated with the range [a-b] of the queue?" in logarithmic time. in O(log n) time. Just do a binary search on the elements of the dequeue based on element number to find the lower and upper bounds. The element present in the deque at that location will be the min-element. Note: using a naive implementation of a dequeue with linked lists makes the binary search impossible. Use an implementation that is similar to a vector with an amortized GROW and SHRINK operation. Complexity Comparison of solutions: Min Stacks based: Enqueue: O(1) Dequeue: amortized O(1) Supports answering the bonus question?: No idea. Possibly with some modifications. 2 Queues based: Enqueue: amortized O(1) Dequeue: O(1) Bonus: Supports answering the bonus question in O(log n) with an intelligent implementation. Hope you liked it! -- DK http://twitter.com/divyekapoor http://www.divye.in -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/iHm62yEZOgcJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
