Deque with Minimum

Задача

Реализовать дек, который поддерживает операции:

push_front(x) — добавить в начало
push_back(x) — добавить в конец
pop_front() — удалить из начала
pop_back() — удалить из конца
get_min() — получить минимальный элемент

Идея: держим две структуры (две MinStack), но вместо «переливать всё как в очереди»
мы перебалансируем, когда одна из частей становится пустой (делаем размеры примерно одинаковыми).

Идея

Храним дек как две части:

L (left) — элементы ближе к началу дека (верх стека = front)
R (right) — элементы ближе к концу дека (верх стека = back)

Тогда:

front лежит на вершине L
back лежит на вершине R
минимум дека = min(L.min, R.min)

Если нам надо удалить из стороны, но соответствующий стек пуст:

собираем все элементы в правильном порядке,
делим пополам,
складываем обратно так, чтобы размеры L и R были близки.

Реализация (C++)

struct MinStack { stack<int> st; stack<int> mn; void push(int x) { st.push(x); if (mn.empty()) mn.push(x); else mn.push(min(x, mn.top())); } int pop_value() { int x = st.top(); st.pop(); mn.pop(); return x; } int top() { return st.top(); } int get_min() { return mn.top(); } bool empty() { return st.empty(); } int size() { return (int)st.size(); } void clear() { while (!st.empty()) st.pop(); while (!mn.empty()) mn.pop(); } }; struct MinDeque { MinStack L; // front side MinStack R; // back side // собрать все элементы дека в вектор в правильном порядке (front -> back) vector<int> dump_all() { vector<int> left_part; while (!L.empty()) { left_part.push_back(L.pop_value()); // уже в порядке front -> ... } vector<int> right_reversed; while (!R.empty()) { right_reversed.push_back(R.pop_value()); // это back -> ... } reverse(right_reversed.begin(), right_reversed.end()); // теперь ... -> back vector<int> all; all.reserve(left_part.size() + right_reversed.size()); for (int x : left_part) all.push_back(x); for (int x : right_reversed) all.push_back(x); return all; } // пересобрать так, чтобы L и R были примерно одинакового размера void rebalance() { vector<int> a = dump_all(); int n = (int)a.size(); if (n == 0) return; int left_cnt = (n + 1) / 2; // L чуть больше или равно R // восстановим L: хотим, чтобы top(L) был front = a[0] for (int i = left_cnt - 1; i >= 0; i--) { L.push(a[i]); } // восстановим R: хотим, чтобы top(R) был back = a[n-1] for (int i = left_cnt; i < n; i++) { R.push(a[i]); } } // добавить в начало void push_front(int x) { L.push(x); } // добавить в конец void push_back(int x) { R.push(x); } // удалить из начала void pop_front() { if (L.empty()) { rebalance(); } L.pop_value(); } // удалить из конца void pop_back() { if (R.empty()) { rebalance(); } R.pop_value(); } // минимум int get_min() { if (L.empty()) return R.get_min(); if (R.empty()) return L.get_min(); return min(L.get_min(), R.get_min()); } bool empty() { return L.empty() && R.empty(); } int size() { return L.size() + R.size(); } };