18. Мини-служба поддержки — повышенный уровень
Очередь и словарь вместе
Что хранит. Очередь хранит порядок идентификаторов, а словарь связывает каждый идентификатор с его текущими данными. Эти коллекции отвечают на разные вопросы об одних записях.
Для чего используют. Подходит, когда задания обрабатываются по очереди, но их состояние нужно читать или менять по идентификатору.
Основные операции
| Запись на C# | Назначение |
|---|
order.Enqueue(id) | Добавить идентификатор в конец очереди. |
order.Peek() / order.Dequeue() | Посмотреть или извлечь первый идентификатор; очередь должна быть непустой. |
order.Count | Число записей в очереди; оно может включать отменённые записи. |
state[id] = value | Создать или обновить состояние по ключу. |
state.TryGetValue(id, out value) | Безопасно прочитать состояние. |
state.ContainsKey(id) | Проверить, известен ли идентификатор. |
Пример
Для примера нужны using System; и using System.Collections.Generic;. Код выполняется внутри Main.
Queue<int> order = new Queue<int>();
Dictionary<int, int> remaining = new Dictionary<int, int>();
order.Enqueue(42);
remaining[42] = 3;
int id = order.Dequeue(); // Очередь выбирает задание.
remaining[id]--; // Словарь хранит его данные.
order.Enqueue(id);
Console.WriteLine(remaining[order.Peek()]);
Вывод:
2
Важно. Изменение словаря само по себе не удаляет элемент очереди. При отмене можно пометить состояние, а ненужную запись пропустить при извлечении.
Для этой задачи
- Отменённые заявки. Храните их состояние в словаре и пропускайте их номера при извлечении из очереди.
- Уникальность. Сведения об использованных номерах сохраняйте и после завершения заявки.
Служба поддержки обрабатывает заявки в порядке создания. Изначально заявок нет. Каждая заявка имеет уникальный идентификатор и состояние WAITING, CANCELLED или DONE. Идентификатор нельзя использовать повторно даже после отмены или обработки заявки. Команда NEXT обрабатывает самую раннюю из всё ещё ожидающих заявок, пропуская отменённые.
Команды
| Команда | Действие и ответ |
|---|
NEW id | Создать заявку со статусом WAITING: OK. Если id когда-либо использовался: EXISTS. |
CANCEL id | Отменить ожидающую заявку: OK. Для отсутствующей, отменённой или обработанной: REJECTED. |
NEXT | Обработать первую ожидающую заявку, присвоить ей DONE и вывести id. Если ожидающих нет: EMPTY. |
STATUS id | Вывести WAITING, CANCELLED, DONE или MISSING, если заявка не создавалась. |
Входные данные
Первая строка содержит q. Далее идут q команд, по одной в строке.
Выходные данные
Для каждой команды выведите ответ из таблицы. Неуспешные NEW и CANCEL, запрос STATUS и NEXT без ожидающих заявок не меняют состояния заявок.
Не выводите приглашения к вводу и пояснения. Служебные слова в ответах пишите в указанном регистре.
Ограничения
1 ≤ q ≤ 100000; идентификатор id от 1 до 10⁹.
| № | Входные данные | Выходные данные |
|
1
|
11
NEW 10
NEW 20
CANCEL 10
NEXT
STATUS 10
STATUS 20
NEW 10
CANCEL 20
NEXT
STATUS 30
CANCEL 30
|
OK
OK
OK
20
CANCELLED
DONE
EXISTS
REJECTED
EMPTY
MISSING
REJECTED
|
|
2
|
8
NEW 7
NEW 7
STATUS 7
NEXT
NEW 7
CANCEL 7
STATUS 7
NEXT
|
OK
EXISTS
WAITING
7
EXISTS
REJECTED
DONE
EMPTY
|
Напишите программу
Auto