Queue With Minimum Algorithm
The Queue With Minimum Algorithm is a data structure that efficiently handles the problem of maintaining a queue while being able to access its minimum element in constant time. It is often used in scenarios where the queue is required to perform operations such as enqueue, dequeue, and finding the minimum in real-time, without having to spend time iterating through the entire queue. This algorithm combines two data structures, namely the queue and the double-ended queue (deque), to achieve its purpose. The queue is responsible for handling the enqueue and dequeue operations, while the deque is used to keep track of the minimum element in the queue at all times.
In this algorithm, when an element is enqueued, it is first added to the rear of the queue as well as to the deque. However, before inserting the element into the deque, all elements in the deque that are greater than the new element are removed from the rear. This ensures that the deque always maintains the elements in the queue in increasing order, with the minimum element being present at the front of the deque. When an element is dequeued, it is removed from the front of the queue. If this element is also present at the front of the deque, it is removed from there as well. Consequently, the front of the deque always contains the minimum element in the queue. The algorithm thus allows for constant time access to the minimum element and efficient implementation of enqueue and dequeue operations.
/*************************************************************************************
Modification of queue, which allows finding the minimum element in it.
Time complexity: O(1) on operation.
Based on problem 756 from informatics.mccme.ru:
http://informatics.mccme.ru//mod/statements/view.php?chapterid=756#1
*************************************************************************************/
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
using namespace std;
const int MAXN = 205000;
int n, m;
deque < pair <int, int> > d;
int a[MAXN];
void enqueue(int x) {
int num = 1;
while (!d.empty() && d.back().first > x) {
num += d.back().second;
d.pop_back();
}
d.push_back(make_pair(x, num));
}
void dequeue() {
if (d.front().second == 1) {
d.pop_front();
}
else {
d.front().second--;
}
}
int getMin() {
return d.front().first;
}
int main() {
//assert(freopen("input.txt","r",stdin));
//assert(freopen("output.txt","w",stdout));
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= m; i++) {
enqueue(a[i]);
}
printf("%d\n", getMin());
for (int i = m + 1; i <= n; i++) {
dequeue();
enqueue(a[i]);
printf("%d\n", getMin());
}
return 0;
}
