题目 基于Vector实现

cpp
class FrontMiddleBackQueue {
private:
    std::vector<int> queue;



public:
    FrontMiddleBackQueue() {
    }
    
    void pushFront(int val) {
        queue.insert(queue.begin(), val);
    }
    
    void pushMiddle(int val) {
        auto mid = queue.begin() + queue.size() / 2;
        queue.insert(mid, val);
    }
    
    void pushBack(int val) {
        queue.push_back(val);
    }
    
    int popFront() {
        if (queue.empty()) {
            return -1;
        }
        int front = queue.front();
        queue.erase(queue.begin());
        return front;
    }
    
    int popMiddle() {
        if (queue.empty()) {
            return -1;
        }
        auto mid = queue.begin() + (queue.size() - 1) / 2;
        int middle = *mid;
        queue.erase(mid);
        return middle;
    }
    
    int popBack() {
        if (queue.empty()) {
            return -1;
        }
        int back = queue.back();
        queue.pop_back();
        return back;
    }
};

基于list实现

cpp


class FrontMiddleBackQueue {
private:
    std::list<int> queue;

public:
    FrontMiddleBackQueue() {
    }
    
    void pushFront(int val) {
        queue.push_front(val);
    }
    
    void pushMiddle(int val) {
        auto mid = queue.begin();
        std::advance(mid, queue.size() / 2);
        queue.insert(mid, val);
    }
    
    void pushBack(int val) {
        queue.push_back(val);
    }
    
    int popFront() {
        if (queue.empty()) {
            return -1;
        }
        int front = queue.front();
        queue.pop_front();
        return front;
    }
    
    int popMiddle() {
        if (queue.empty()) {
            return -1;
        }
        auto mid = queue.begin();
        std::advance(mid, (queue.size() - 1) / 2);
        int middle = *mid;
        queue.erase(mid);
        return middle;
    }
    
    int popBack() {
        if (queue.empty()) {
            return -1;
        }
        int back = queue.back();
        queue.pop_back();
        return back;
    }
};

基于原生数组实现

cpp
class FrontMiddleBackQueue {
private:
    int capacity;
    int size;
    int* queue;

public:
    FrontMiddleBackQueue() {
        capacity = 1000; // 作为示例，设定一个初始容量
        size = 0;
        queue = new int[capacity];
    }

    void pushFront(int val) {
        if (size == capacity) {
            resize();
        }
        for (int i = size; i > 0; --i) {
            queue[i] = queue[i - 1];
        }
        queue[0] = val;
        ++size;
    }

    void pushMiddle(int val) {
        if (size == capacity) {
            resize();
        }
        int mid = size / 2;
        for (int i = size; i > mid; --i) {
            queue[i] = queue[i - 1];
        }
        queue[mid] = val;
        ++size;
    }

    void pushBack(int val) {
        if (size == capacity) {
            resize();
        }
        queue[size] = val;
        ++size;
    }

    int popFront() {
        if (size == 0) {
            return -1;
        }
        int front = queue[0];
        for (int i = 0; i < size - 1; ++i) {
            queue[i] = queue[i + 1];
        }
        --size;
        return front;
    }

    int popMiddle() {
        if (size == 0) {
            return -1;
        }
        int mid = (size - 1) / 2;
        int middle = queue[mid];
        for (int i = mid; i < size - 1; ++i) {
            queue[i] = queue[i + 1];
        }
        --size;
        return middle;
    }

    int popBack() {
        if (size == 0) {
            return -1;
        }
        int back = queue[size - 1];
        --size;
        return back;
    }

private:
    void resize() {
        int newCapacity = capacity * 2;
        int* newQueue = new int[newCapacity];
        for (int i = 0; i < size; ++i) {
            newQueue[i] = queue[i];
        }
        delete[] queue;
        queue = newQueue;
        capacity = newCapacity;
    }
};