**Introduction **

Let us first discuss the problem statement. The problem statement goes like this: We need to implement a data structure known as the **double-ended priority queue** which supports the following methods:

- add(int x): Insert an element with the value ‘X’ into the double-ended priority queue.
- printQueue(): Outputs the content of the double-ended priority queue.
- getMax(): Outputs the maximum element from the double-ended priority queue.
- getMin(): Outputs the minimum element from the double-ended priority queue.
- eraseMax(): Removes the maximum element from the double-ended priority queue.
- eraseMin(): Removes the minimum element from the double-ended priority queue.
- isEmpty(): Outputs a boolean, true when the double-ended priority queue is empty and false otherwise.
- size(): Outputs the number of elements in the double-ended priority queue.

**Note**: in this blog “queue” and “double-ended priority queue” are used interchangeably.

**Solution Approach**

- We will use a multiset as our main data structure and build our queue on top of it. Let us define a multiset: A multiset is a container that is similar to a set but it can hold multiple elements of the same values.
- It is internally implemented as a self-balancing binary search tree. This makes insertion and deletion time in a multiset O(logn).
- Accessing elements in a multiset using iterators will take O(1) time.
- Below is the implementation, we have used the inbuilt methods of multiset to achieve what the problem statement demands.

**C++ Code**

```
#include <bits/stdc++.h>
using namespace std;
class DoubleEndedPQ
{
private:
multiset<int> nums;
public:
// Constructor clears the multiset 'nums'
DoubleEndedPQ()
{
nums.clear();
}
// This method inserts an element 'x' into the queue
void add(int x)
{
nums.insert(x);
}
// This method prints the content of the queue
void printQueue()
{
for (auto it = nums.begin(); it != nums.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
// This method gets the maximum element from the queue
int getMax()
{
if (nums.size() == 0)
{
return INT_MAX;
}
return *nums.rbegin();
}
// This method gets the minimum element from the queue
int getMin()
{
if (nums.size() == 0)
{
return INT_MAX;
}
return *nums.begin();
}
// This method removes the largest element from the queue
void eraseMax()
{
if (nums.size() != 0)
{
nums.erase(*nums.rbegin());
}
else
{
cout << "No elements found." << endl;
}
}
// This method removes the smallest element from the queue
void eraseMin()
{
if (nums.size() != 0)
{
nums.erase(*nums.begin());
}
else
{
cout << "No elements found." << endl;
}
}
// Checks if the queue is empty
bool isEmpty()
{
return nums.size() == 0 ? true : false;
}
// This methods returns the size of the queue
int size()
{
return nums.size();
}
};
int main()
{
DoubleEndedPQ depq = DoubleEndedPQ();
// Adding elements to the queue
depq.add(1);
depq.add(3);
depq.add(3);
depq.add(4);
depq.add(5);
depq.add(2);
// Printing the contents of the queue
cout << "Elements in the queue: ";
depq.printQueue();
// Getting the maximum element
cout << "Maximum element: " << depq.getMax() << endl;
// Getting the minimum element
cout << "Minimum element: " << depq.getMin() << endl;
// Removing the maximum element
depq.eraseMax();
cout << "After removing the largest element: ";
depq.printQueue();
// Removing the minimum element
depq.eraseMin();
cout << "After removing the smallest element: ";
depq.printQueue();
// Checking if the queue is empty
cout << depq.isEmpty() << endl;
// getting the size of the queue
cout << depq.size() << endl;
}
```

**Output:**

**Complexity Analysis**

- add(int x) / removeMax() / removeMin() : O(logN), we are inserting / deleting an element, and insertion / deletion time in a multiset is O(logN) as it uses self-balancing BST in the background (as discussed above).
- printQueue(): O(N), as we need to traverse through the queue to print the elements.
- getMin() / getMax(): O(1) as we are accessing the required elements using iterator.
- isEmpty(): O(1)
- size(): O(1)

O(N), as we are using an auxiliary container (multiset) to store all the ‘N’ elements.

Also Read, __Prefix Sum Array__