leetcode/algorithms/cpp/designFrontMiddleBackQueue/designFrontMiddleBackQueue.cpp at main · MichelleZ/leetcode · GitHub

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// Source: https://leetcode.com/problems/design-front-middle-back-queue/
// Author: Miao Zhang
// Date:   2021-05-26

class FrontMiddleBackQueue {
public:
    FrontMiddleBackQueue() {

    }

    void pushFront(int val) {
        q_.push_front(val);
        updateMidit(even() ? -1 : 0);
    }

    void pushMiddle(int val) {
        if (q_.empty()) {
            q_.push_back(val);
        } else {
            q_.insert(even() ? next(midit_) : midit_, val);
        }
        updateMidit(even() ? -1 : 1);
    }

    void pushBack(int val) {
        q_.push_back(val);
        updateMidit(even() ? 0 : 1);
    }

    int popFront() {
        if (q_.empty()) return -1;
        int val = q_.front();
        q_.pop_front();
        updateMidit(even() ? 0 : 1);
        return val;
    }

    int popMiddle() {
        if (q_.empty()) return -1;
        int val = *midit_;
        midit_ = q_.erase(midit_);
        updateMidit(even() ? -1 : 0);
        return val;
    }

    int popBack() {
        if (q_.empty()) return -1;
        int val = q_.back();
        q_.pop_back();
        updateMidit(even() ? -1 : 0);
        return val;
    }

private:
    list<int> q_;
    list<int>::iterator midit_;

    bool even() const {
        return q_.size() % 2 == 0;
    }

    void updateMidit(int flag) {
        if (q_.size() <= 1) {
            midit_ = begin(q_);
        } else {
            if (flag > 0) midit_++;
            if (flag < 0) midit_--;
        }
    }
};

/**
 * Your FrontMiddleBackQueue object will be instantiated and called as such:
 * FrontMiddleBackQueue* obj = new FrontMiddleBackQueue();
 * obj->pushFront(val);
 * obj->pushMiddle(val);
 * obj->pushBack(val);
 * int param_4 = obj->popFront();
 * int param_5 = obj->popMiddle();
 * int param_6 = obj->popBack();
 */