Ну, от хранения номеров в памяти вы не избавитесь. Вот насчёт времени можно что-то придумать. Погуглив подобные вопросы, я нашёл на английском СО вариант с разбиением очереди на 2 части. Плюс развил идею из вашего комментария.

Вариант 1

Просто делаете 2 очереди: для первой половины людей и для второй половины людей.

[очередь первой половины] [очередь второй половины]
 ^                       ^                       ^
 | начало                | середина              | конец

Тогда вставка в середину очереди будет сдвигать каждый раз не половину элементов очереди, а всего несколько. Которые лучше и не сдвигать, а перекидывать в другую очередь, возможно. Сами очереди реализуются традиционно - в виде кольцевых буферов.

В результате типичное время всех требуемых операций будет примерно O(1). Но периодически придётся перекидывать по нескольку элементов из одной очереди в другую. Ну и сами очереди при превышении буфера придётся переаллоцировать в более крупный буфер, ну это как обычно.

Логика будет сложноватая, но работать это должно эффективно.

Вариант 2

Можно, сделать связный список и ещё хранить ссылку на текущую его середину, от которой потом уже идти в следующий раз до актуальной середины, когда это понадобится. Для этого нужно будет ещё хранить текущее число элементов в очереди и порядковый номер элемента, на который указывает средний указатель (или это не надо? тут надо думать).

[ ] -> [ ] -> [ ] -> [ ] -> [ ]
 ^             ^             ^
 | начало      | середина    | конец

Эффективность этого метода будет зависеть от соотношения добавлений/удалений из очереди и вставок в середину. Если добавлений/удалений будет много, то идти до текущей середины придётся далеко. Впрочем, в варианте с двумя очередями в этом случае тоже придётся перекидывать много элементов из очереди в очередь, не уверен, что сложнее будет. Возможно, список будет эффективнее в этом случае.

А главное - сам алгоритм в случае списка будет гораздо проще, чем вариант с двумя очередями, особенно если вам придётся и сами очереди тоже "вручную" делать, а не брать готовые.

Впрочем, учитывая сложности пересчёта среднего элемента при добавлениях/удалениях, может этот алгоритм и не будет сильно проще.

P.S.

Какие есть источники, чтобы научится решать такие задачи?

Ну, есть всякие книги по типу "грокаем алгоритмы". И вообще, когда решаете много разнотипных задач на алгоритмы, то потом уже просто знаете, какой есть ассортимент коллекций и приёмов работы с ними, чтобы можно было подобрать подходящие инструменты под конкретную задачу. Нужно уметь оценивать алгоритмическую сложность тех или иных типовых действий и собирать оптимальную конфигурацию структур и методов под решение задачи.

Как можно решить эту задачу эффективно? Какие приёмы можно использовать для решения?

Сперва надо решить как решать задачу. Можно симулировать очередь, можно изобрести какой-то способ без прямолинейной симуляции. Симуляция возможна за линейное время и линейную память. Понятно что линейное время не улучшить, но вдруг получится сделать меньшую память? Так что я потратил время на решение без симуляции, но ничего не придумалось. Делаем симуляцию.

deques

Первая идея - двусторонняя очередь. Но она не эффективна при вставке в середину. Опыт подсказывает использовать две очереди: одну от начала до середины, вторую от середины до конца. Надо будет следить за их длинами, но в целом ничего особенного.

Примеры я буду приводить на С++, у него богатая библиотека, которая хорошо подходит для этой задачи.

void deques() {
    std::deque<int> q1, q2;
    char c;
    while (std::cin >> c) {
        assert(q1.size() == q2.size() || q1.size() == q2.size() + 1); 
        int x;
        switch (c) {
        case 'P':
            std::cin >> x;
            q2.push_back(x);
            if (q2.size() > q1.size()) {
                q1.push_back(q2.front());
                q2.pop_front();
                assert(q1.size() == q2.size() + 1); 
            }
            break;
        case 'M':
            std::cin >> x;
            if (q1.size() > q2.size()) {
                q2.push_front(x);
                assert(q1.size() == q2.size()); 
            } else {
                q1.push_back(x);
                assert(q1.size() == q2.size() + 1); 
            }
            break;
        case 'C':
            std::cout << q1.front() << '\n';
            q1.pop_front();
            if (q1.size() < q2.size()) {
                q1.push_back(q2.front());
                q2.pop_front();
                assert(q1.size() == q2.size() + 1); 
            }
            break;
        }
        assert(q1.size() == q2.size() || q1.size() == q2.size() + 1); 
    }
}

vector

В комментариях упомянули вектор. Мол, современные компьютеры так устроены, что вектора очень эффективны и будут быстрее других, специализированных структур данных до размеров около миллиона элементов. Я вектор-скептик, но вариант с вектором очень прост, добавим его:

void vector() {
    std::vector<int> v;
    char c;
    while (std::cin >> c) {
        int x;
        switch (c) {
        case 'P':
            std::cin >> x;
            v.push_back(x);
            break;
        case 'M':
            std::cin >> x;
            v.insert(v.begin() + (v.size() + 1) / 2, x);
            break;
        case 'C':
            std::cout << v.front() << '\n';
            v.erase(v.begin());
            break;
        }
    }
}

forward_list

Единственная структура, которая позволяет вставку в середину за константу, список. В C++ есть двусвязный список list и односвязный forward_list. Для этой задачи достаточно односвязного.

Обычно односвязные списки пишут руками, но в данном я использовал готовый forward_list, что радикально уменьшает объём кода: не нужно самому выделять память, писать примитивные операции.

Это решение самое сложное: требуется хранить сам список, указатели на середину и конец, размер. И отладка далась с трудом, я упустил тонкий момент, когда указатели на середину и конец равны.

void forward_list() {
    std::forward_list<int> l;
    auto mid = l.end();
    auto last = l.end();
    size_t size = 0;
    char c;
    while (std::cin >> c) {
        int x;
        switch (c) {
        case 'P':
            std::cin >> x;
            if (last == l.end()) {
                l.push_front(x);
                mid = l.begin();
                last = l.begin();
            } else {
                l.insert_after(last, x);
                ++last;
                if (size % 2 == 0) {
                    ++mid;
                }
            }
            ++size;
            break;
        case 'M':
            std::cin >> x;
            if (last == l.end()) {
                l.push_front(x);
                mid = l.begin();
                last = l.begin();
            } else {
                l.insert_after(mid, x);
                if (mid == last) {
                    ++last;
                }
                if (size % 2 == 0) {
                    ++mid;
                }
            }
            ++size;
            break;
        case 'C':
            std::cout << l.front() << '\n';
            if (size == 1) {
                mid = l.end();
                last = l.end();
            } else {
                if (size % 2 == 0) {
                    ++mid;
                }
            }
            l.pop_front();
            --size;
            break;
        }
    }
}

Производительность

Раз есть три решения и утверждение что решение с вектором самое из них прекрасное, грех не проверить. Я написал main, которая конфигурирует cin/cout на скорость. Это типичный олимпиадный трюк, без него программы на C++, в которых перемежается ввод и вывод, очень тормозят. Вызывается программа так:

./a.out q < in.txt > out.txt

Единственный параметр выбирает вариант: q для очередей, v для вектора, l для списка. В in.txt входные данные, в out.txt результат.

int main(int, char *argv[]) {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    switch (argv[1][0]) {
    case 'q': deques      (); break;
    case 'v': vector      (); break;
    case 'l': forward_list(); break;
    }
}

Программа тестировалась на некоторых входах чтобы убедиться что все алгоритмы делают одно и то же. Потом я перешёл к замерам времени.

Я хотел измерить времена обработки очереди определённого размера. Сперва очередь заполнялась до этого размера командами P x. Затем один миллион раз повторялись четыре команды: M x, C, P x, C. Во второй фазе размер очереди почти не меняется, мы просто тестируем как быстро разные структуры справляются с очередью этого конкретного размера.

Размеры очереди были 10, 20, 30, ..., 100, 200, 300, ..., 1000, 2000, 3000, ..., 10000, 20000, 30000, ..., 100000.

И его нижняя часть покрупнее:

Выводы

Я сравню операции который делают список и вектор на левом конце графика (длина очереди 10 элементов), когда у вектора должно быть максимальное преимущество.

Всего список делает два выделения и два освобождения памяти. Вектор вмещает вперёд-назад всего 100 байт в небольшом стационарном буфере, работы с памятью нет совсем, она вся делается в начале до первой итерации.

Односвязный список всегда быстрее вектора. Код с его участием сложный, но он делает мало операций.

Очереди показывают то же O-большое что и список, но константа хуже. Очередей две, требуется перекладка элементов между ними, сами очереди внутри устроены сложнее списков.

Вектор начинает хорошо и до тысячи элементов не уступает очереди, но потом сдаётся, O-большое не обманешь. Какой бы ни был великолепный кэш, скопировать тысячу элементов не получается так же быстро как переставить два указателя.

Напомню цитату, которая побудила меня провести анализ:

Кэш побеждает асимптотику. Берём динамический массив (в C++ это vector<T>, в C# это List<T>) и он, несмотря на копирования элементов, окажется быстрее чем списки. Если только речь не о миллионах элементов.

Если в этой цитате поправить "о миллионах элементов" на "о двух тысячах элементов" и "список" заменить на "очереди", она становится правдой. А пока обойти список у вектора не получилось.

Мертвы ли списки? Нет. Есть ряд задач в которых односвязный список обходит любые другие структуры данных и по константе и по O-большому.

Какие есть источники, чтобы научится решать такие задачи?

Ищите книги и учебные материлы по структурам данных. Когда вы освоитесь с массивами, списками, деревьями, очередями, стеками, и хеш-таблицами, порешайте олимпиадные задачи на структуры данных. Решить задач надо много, и будет у вас понимание какой контейнер каким концом прикладывать к задаче, чтобы она решилась быстро и в минимальной памяти.

P.S. Сказ про то как мужик из двух стеков очередь сделал

Я не стал добавлять ещё одно решение, и так ответ гигантский, но из двух стеков можно сделать двустроннюю очередь. Она будет во всём прекрасна, кроме ситуации когда вы попеременно вынимаете элементы с двух концов. В этой задаче такой ситуации не бывает: почитайте deques, там элементы удаляются только из начала очередей. Так вот, если deque заменить на такую двухстековую очередь, она может стать лучшей по производительности. Потому что не нужно выделять память под узлы списка, а операции со стеками (которые на самом деле вектора) могут быть быстрее, чем операции с deque.