3. Deque

---

// ── ABOUT ────────────────────────────────────────────────────────
// Same as vector but supports O(1) insert/delete at BOTH ends
// Random access O(1) like vector
 
// ── CREATE ───────────────────────────────────────────────────────
deque<int> dq;
 
// ── INSERT ───────────────────────────────────────────────────────
dq.push_back(1);                         // O(1) insert at back
dq.push_back(2);
dq.push_front(3);                        // O(1) insert at front
// dq = {3, 1, 2}
 
// ── DELETE ───────────────────────────────────────────────────────
dq.pop_back();                           // O(1)
dq.pop_front();                          // O(1)
 
// ── ACCESS ───────────────────────────────────────────────────────
dq.front();                              // first element
dq.back();                               // last element
dq[2];                                   // O(1) random access
 
// ── ITERATE ──────────────────────────────────────────────────────
for (auto &i : dq)
    cout << i << " ";

---