Problems

Here are the problem-solving sections for this chapter.

45. Priority queue

Write a data structure that represents a priority queue that provides constant time lookup for the largest element, but has logarithmic time complexity for adding and removing elements. A queue inserts new elements at the end and removes elements from the top. By default, the queue should use operator< to compare elements, but it should be possible for the user to provide a comparison function object that returns true if the first argument is less than the second. The implementation must provide at least the following operations:

• push() to add a new element
• pop() to remove the top element
• top() to provide access to the top element
• size() to indicate the number of elements in the queue
• empty() to indicate whether the queue is empty

46. Circular buffer

Create a data structure that represents a circular buffer of a fixed size. A circular buffer overwrites existing elements when the buffer is being filled beyond its...