Дек бо минимум

Дек бо ҳадди ақал

Вазифа

Амалӣ кардани дек, ки амалиётҳоро дастгирӣ мекунад:

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(); } };