Design a queue that supports push
and pop
operations in the front, middle, and back.
Implement the FrontMiddleBack
class:
FrontMiddleBack()
Initializes the queue.void pushFront(int val)
Addsval
to the front of the queue.void pushMiddle(int val)
Addsval
to the middle of the queue.void pushBack(int val)
Addsval
to the back of the queue.int popFront()
Removes the front element of the queue and returns it. If the queue is empty, return-1
.int popMiddle()
Removes the middle element of the queue and returns it. If the queue is empty, return-1
.int popBack()
Removes the back element of the queue and returns it. If the queue is empty, return-1
.
Notice that when there are two middle position choices, the operation is performed on the frontmost middle position choice. For example:
- Pushing
6
into the middle of[1, 2, 3, 4, 5]
results in[1, 2, 6, 3, 4, 5]
. - Popping the middle from
[1, 2, 3, 4, 5, 6]
returns3
and results in[1, 2, 4, 5, 6]
.
Example 1:
Input: ["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"] [[], [1], [2], [3], [4], [], [], [], [], []] Output: [null, null, null, null, null, 1, 3, 4, 2, -1] Explanation: FrontMiddleBackQueue q = new FrontMiddleBackQueue(); q.pushFront(1); // [1] q.pushBack(2); // [1, 2] q.pushMiddle(3); // [1, 3, 2] q.pushMiddle(4); // [1, 4, 3, 2] q.popFront(); // return 1 -> [4, 3, 2] q.popMiddle(); // return 3 -> [4, 2] q.popMiddle(); // return 4 -> [2] q.popBack(); // return 2 -> [] q.popFront(); // return -1 -> [] (The queue is empty)
Constraints:
1 <= val <= 109
- At most
1000
calls will be made topushFront
,pushMiddle
,pushBack
,popFront
,popMiddle
, andpopBack
.
Solution: List + Middle Iterator
Time complexity: O(1) per op
Space complexity: O(n) in total
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
// Author: Huahua class FrontMiddleBackQueue { public: FrontMiddleBackQueue() {} void pushFront(int val) { q_.push_front(val); updateMit(even() ? -1 : 0); } void pushMiddle(int val) { if (q_.empty()) q_.push_back(val); else q_.insert(even() ? next(mit_) : mit_, val); updateMit(even() ? -1 : 1); } void pushBack(int val) { q_.push_back(val); updateMit(even() ? 0 : 1); } int popFront() { if (q_.empty()) return -1; int val = q_.front(); q_.pop_front(); updateMit(even() ? 0 : 1); return val; } int popMiddle() { if (q_.empty()) return -1; int val = *mit_; mit_ = q_.erase(mit_); updateMit(even() ? -1 : 0); return val; } int popBack() { if (q_.empty()) return -1; int val = q_.back(); q_.pop_back(); updateMit(even() ? -1 : 0); return val; } private: void updateMit(int delta) { if (q_.size() <= 1) { mit_ = begin(q_); } else { if (delta > 0) ++mit_; if (delta < 0) --mit_; } } bool even() const { return q_.size() % 2 == 0; } list<int> q_; list<int>::iterator mit_; }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment