LeetCode
comments powered by Disqus
Editorial: LeetCode 1670 Design Front Middle Back Queue
https://leetcode.com/problems/design-front-middle-back-queue/ from Amazon
Thinking process:
When talking about anything related to middle, the first thing comes up to me is to use two data structure to handle the first part and second part of our data.
This question is the same. From the example, looks like the first part should always equal or shorter than the seacond part. Just like below graph
Below is the code. We use deque data structure so that we can access the front and back element in O(1) time.
1class FrontMiddleBackQueue {
2public:
3 deque<int> fq, bq;
4 FrontMiddleBackQueue() {
5
6 }
7
8 void pushFront(int val) {
9 fq.push_front(val);
10 balance();
11 }
12
13 void pushMiddle(int val) {
14 if (fq.size() < bq.size()) {
15 fq.push_back(val);
16 } else
17 bq.push_front(val);
18 }
19
20 void pushBack(int val) {
21 bq.push_back(val);
22 balance();
23 }
24
25 int popFront() {
26 if (bq.empty()) return -1;
27 deque<int>& q = fq.size() ? fq : bq;
28 int ret = q.front();
29 q.pop_front();
30 balance();
31 return ret;
32 }
33
34 int popMiddle() {
35 if (bq.empty()) return -1;
36 int ret;
37 if (fq.size() < bq.size()) {
38 ret = bq.front(); bq.pop_front();
39 } else {
40 ret = fq.back(); fq.pop_back();
41 }
42 return ret;
43 }
44
45 int popBack() {
46 if (bq.empty()) return -1;
47 int ret = bq.back();
48 bq.pop_back();
49 balance();
50 return ret;
51 }
52
53 void balance() {
54 if (fq.size() + 1 < bq.size())
55 fq.push_back(bq.front()), bq.pop_front();
56 if (fq.size() > bq.size())
57 bq.push_front(fq.back()), fq.pop_back();
58 }
59};