PapaMelon #7 设计双端队列

题目链接

• 设计双端队列
• https://www.papamelon.com/problem/7

题解

• 就是一个基础的数据结构题，选自 PapaMelon 系统算法课程 - 基础版
• https://www.papamelon.com/topic/papamelon-basic-algorithm-2021
• 双端队列有两种常见的时间方案，下面实现的是 C++ STL deque 的方案：离散块状数组 + 中控器。可以实现随机访问。

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <cassert>
#include <memory>

using namespace std;

const vector<string> OP = {
    "PUSH_FRONT", "POP_FRONT", "INDEX",  "CONTAINS",
    "REMOVE",     "REVERSE",   "FOR_EACH",
    "PUSH_BACK",  "POP_BACK"};

const int BLOCK_SIZE = 1024;
const int CENTER_SIZE = 8;

struct Block {
    int buf[BLOCK_SIZE];
    int begin, end;

    Block(): begin(-1), end(-1) {}

    void push_front(int x) { buf[--begin] = x; }
    void pop_front() { begin++; }
    void push_back(int x) { buf[end++] = x; }
    void pop_back() { end--; }
    bool empty() { return begin == end; }
    void front_init() { begin = end = BLOCK_SIZE; }
    void back_init() { begin = end = 0; }
    int size() { return end - begin; }
};

struct Dqueue {
    vector<shared_ptr<Block>> center;
    int begin, end, capacity, size;

    Dqueue(): 
        begin(CENTER_SIZE>>1), end(CENTER_SIZE>>1), capacity(CENTER_SIZE), size(0), 
        center(CENTER_SIZE) {}
    
    ~Dqueue() {
        center.clear();
        begin = end = -1;
    }

    void clear() {
        center.assign(capacity, nullptr);
        begin = end = -1;
    }

    shared_ptr<Block> get_first_block() {
        // center 为空, 新建一个 block
        if (end == begin) {
            begin = capacity >> 1;
            end = begin + 1;
            auto block = make_shared<Block>();
            block->front_init();
            center[begin] = block;
            return block;
        }

        // 第一个 block 未满, 直接返回
        if (center[begin]->begin > 0) return center[begin];

        // 第一个block 已满，但是center 未满，新建一个 block
        if (begin > 0) {
            auto block = make_shared<Block>();
            block->front_init();
            center[--begin] = block;;
            return block;
        }

        // 第一个block已满，center也满，扩容center
        int newcapacity = capacity << 1;
        center.resize(newcapacity);
        int size = end - begin;
        int pos = newcapacity - (newcapacity - size) / 2;
        for (int i = end - 1, j = pos; i >= begin; i--, j--) {
            center[j] = center[i];
            center[i] = nullptr;
        }
        end = pos + 1;
        begin = end - size;
        capacity = newcapacity;
        
        auto block = make_shared<Block>();
        block->front_init();
        center[--begin] = block;
        return block;
    }

    shared_ptr<Block> get_last_block() {
        // center 为空
        if (begin == end) {
            begin = capacity >> 1;
            end = begin + 1;
            auto block = make_shared<Block>();
            block->back_init();
            center[begin] = block;
            return block;
        }

        // 最后一个 block 未满
        if (center[end - 1]->end < BLOCK_SIZE) return center[end - 1];

        // 最后一个 block 已满，但是 center 未满
        if (end < capacity) {
            auto block = make_shared<Block>();
            block->back_init();
            center[end++] = block;
            return block;
        }

        // 最后一个 block 已满，center 已满，扩容
        int newcapacity = capacity >> 1;
        int size = end - begin;
        center.resize(newcapacity);
        int pos = (newcapacity - size) / 2;
        for (int i = begin, j = pos; i < end; i++, j++) {
            center[j] = center[i];
            center[i] = nullptr;
        }
        capacity = newcapacity;
        end = pos + size;
        begin = pos;

        auto block = make_shared<Block>();
        block->back_init();
        center[end--] = block;
        return block;
    }

    void adjust() {
        // 第一个 block 为空
        if (center[begin]->empty()) {
            center[begin] = nullptr;
            begin++;
            return;
        }

        // 最后一个 block 为空
        if (center[end - 1]->empty()) {
            center[end - 1] = nullptr;
            end--;
            return;
        }
    }

    void push_front(int x) {
        auto block = get_first_block();
        block->push_front(x);
        size++;
    }

    void pop_front() {
        auto block = center[begin];
        block->pop_front();
        adjust(); // 判断是否要清除第一块 block
        size--;
    }

    void push_back(int x) {
        auto block = get_last_block();
        block->push_back(x);
        size++;
    }

    void pop_back() {
        auto block = center[end - 1];
        block->pop_back();
        adjust();
        size--;
    }

    void foreach() {
        bool first = true;

        for (int i = begin; i < end; i++)
            for (int j = center[i]->begin; j < center[i]->end; j++) {
                if (!first) cout << " ";
                first = false;
                cout << center[i]->buf[j];
            }
        cout << endl;
    }

    bool contains(int x) {
        for (int i = begin; i < end; i++)
            for (int j = center[i]->begin; j < center[i]->end; j++) 
                if (center[i]->buf[j] == x) return true;

        return false;
    }

    int& index(int idx) {
        idx++;

        // 在第一个 block 中
        if (idx <= center[begin]->size()) {
            auto block = center[begin];
            return block->buf[block->begin + idx - 1];
        }

        // 只有两个 block，在最后一个 block 中
        if (end - begin == 2) {
            idx -= center[begin]->size();
            auto block = center[end - 1];
            return block->buf[block->begin + idx - 1];
        }

        int count = end - begin - 2;
        int mid = count * BLOCK_SIZE;
        if (idx - center[begin]->size() > mid) {
            idx -= center[begin]->size() + mid;
            auto block = center[end - 1];
            return block->buf[block->begin + idx - 1];
        }

        idx -= center[begin]->size();
        int num = idx / BLOCK_SIZE;
        idx -= num * BLOCK_SIZE;
        if (!idx) return center[begin + num]->buf[BLOCK_SIZE - 1];
        return center[begin + num + 1]->buf[center[begin + num - 1]->begin + idx - 1];
    }

    void reverse() {
        int i = 0, j = size - 1;
        while (i < j) {
            std::swap(index(i), index(j));
            i++, j--;
        }
    }

    void remove(int x) {
        int cnt = 0, i = 0, j = 0;
        while (j < size) {
            if (index(j) == x) cnt++;
            else {
                int& x = index(i);
                int& y = index(j);
                x = y;
                i++;
            }
            j++;
        }

        while (cnt--) pop_back();
    }
};

Dqueue data;

void dpushfront() {
    int x;
    cin >> x;
    data.push_front(x);
}

void dpopfront() {
    data.pop_front();
}

void dindex() {
    int index;
    cin >> index;
    cout << data.index(index) << endl;
}

void dcontains() {
    int x;
    cin >> x;
    bool ret = data.contains(x);
    if (ret) cout << "true" << endl;
    else cout << "false" << endl;
}

void dremove() {
    int x;
    cin >> x;
    data.remove(x);
}

void dreverse() {
    data.reverse();
}

void dforeach() {
    data.foreach();
}

void dpushback() {
    int x;
    cin >> x;
    data.push_back(x);
}

void dpopback() {
    data.pop_back();
}

void solve() {
    int M;
    cin >> M;
    
    data.clear();
    while (M--) {
        string op;
        cin >> op;
        int id = find(OP.begin(), OP.end(), op) - OP.begin();

        switch (id) {
            case 0:
                dpushfront();
                break;
            case 1:
                dpopfront();
                break;
            case 2:
                dindex();
                break;
            case 3:
                dcontains();
                break;
            case 4:
                dremove();
                break;
            case 5:
                dreverse();
                break;
            case 6:
                dforeach();
                break;
            case 7:
                dpushback();
                break;
            case 8:
                dpopback();
                break;
            default:
                assert(0);
        }
    }
}

int main() {
    solve();
    return 0;
}