leetcode

0 class FrontMiddleBackQueue {

1 public:

2 deque<int> left, right;

3

4 void balance() {

5 if (size(left) > size(right)) {

6 right.push_front(left.back());

7 left.pop_back();

8 }

9

10 if (size(left) + 1 < size(right)) {

11 left.push_back(right.front());

12 right.pop_front();

13 }

14 }

15

16 void pushFront(int val) {

17 left.push_front(val);

18 balance();

19 }

20

21 void pushMiddle(int val) {

22 left.push_back(val);

23 balance();

24 }

25

26 void pushBack(int val) {

27 right.push_back(val);

28 balance();

29 }

30

31 int popFront() {

32 if (size(left) == 0) {

33 if (size(right) == 0) return -1;

34 const int res = right.front();

35 right.pop_front();

36 return res;

37 }

38 const int res = left.front();

39 left.pop_front();

40 balance();

41 return res;

42 }

43

44 int popMiddle() {

45 if (size(right) + size(left) == 0) return -1;

46 if (size(left) < size(right)) {

47 const int res = right.front();

48 right.pop_front();

49 return res;

50 } else {

51 const int res = left.back();

52 left.pop_back();

53 balance();

54 return res;

55 }

56 }

57

58 int popBack() {

59 if (size(right) == 0) {

60 if (size(left) == 0) return -1;

61 const int res = left.back();

62 left.pop_back();

63 return res;

64 }

65 const int res = right.back();

66 right.pop_back();

67 balance();

68 return res;

69 }

70 };