leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1670.cpp (1596B)

      1 class FrontMiddleBackQueue {
      2   public:
      3     deque<int> left, right;
      4 
      5     void balance() {
      6         if (size(left) > size(right)) {
      7             right.push_front(left.back());
      8             left.pop_back();
      9         }
     10 
     11         if (size(left) + 1 < size(right)) {
     12             left.push_back(right.front());
     13             right.pop_front();
     14         }
     15     }
     16 
     17     void pushFront(int val) {
     18         left.push_front(val);
     19         balance();
     20     }
     21 
     22     void pushMiddle(int val) {
     23         left.push_back(val);
     24         balance();
     25     }
     26 
     27     void pushBack(int val) {
     28         right.push_back(val);
     29         balance();
     30     }
     31 
     32     int popFront() {
     33         if (size(left) == 0) {
     34             if (size(right) == 0) return -1;
     35             const int res = right.front();
     36             right.pop_front();
     37             return res;
     38         }
     39         const int res = left.front();
     40         left.pop_front();
     41         balance();
     42         return res;
     43     }
     44 
     45     int popMiddle() {
     46         if (size(right) + size(left) == 0) return -1;
     47         if (size(left) < size(right)) {
     48             const int res = right.front();
     49             right.pop_front();
     50             return res;
     51         } else {
     52             const int res = left.back();
     53             left.pop_back();
     54             balance();
     55             return res;
     56         }
     57     }
     58 
     59     int popBack() {
     60         if (size(right) == 0) {
     61             if (size(left) == 0) return -1;
     62             const int res = left.back();
     63             left.pop_back();
     64             return res;
     65         }
     66         const int res = right.back();
     67         right.pop_back();
     68         balance();
     69         return res;
     70     }
     71 };