Deque with Minimum

Task

Implement a deque that supports operations:

push_front(x) — add to the front
push_back(x) — add to the back
pop_front() — remove from the front
pop_back() — remove from the back
get_min() — get the minimum element

Idea: keep two structures (two MinStacks), but instead of “pouring everything like in a queue”
we rebalance when one of the parts becomes empty (make the sizes approximately equal).

Idea

Store the deque as two parts:

L (left) — elements closer to the front of the deque (stack top = front)
R (right) — elements closer to the back of the deque (stack top = back)

Then:

front is on the top of L
back is on the top of R
deque minimum = min(L.min, R.min)

If we need to remove from a side but the corresponding stack is empty:

collect all elements in the correct order,
split in half,
put them back so that the sizes of L and R are close.

Implementation (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 // collect all deque elements into a vector in the correct order (front -> back) vector<int> dump_all() { vector<int> left_part; while (!L.empty()) { left_part.push_back(L.pop_value()); // already in order front -> ... } vector<int> right_reversed; while (!R.empty()) { right_reversed.push_back(R.pop_value()); // this is back -> ... } reverse(right_reversed.begin(), right_reversed.end()); // now ... -> 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; } // rebuild so that L and R are approximately the same size void rebalance() { vector<int> a = dump_all(); int n = (int)a.size(); if (n == 0) return; int left_cnt = (n + 1) / 2; // L is slightly larger than or equal to R // restore L: we want top(L) to be front = a[0] for (int i = left_cnt - 1; i >= 0; i--) { L.push(a[i]); } // restore R: we want top(R) to be back = a[n-1] for (int i = left_cnt; i < n; i++) { R.push(a[i]); } } // add to the front void push_front(int x) { L.push(x); } // add to the back void push_back(int x) { R.push(x); } // remove from the front void pop_front() { if (L.empty()) { rebalance(); } L.pop_value(); } // remove from the back void pop_back() { if (R.empty()) { rebalance(); } R.pop_value(); } // minimum 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(); } };