Реализация очереди, где вы можете вставлять элементы в определенную позицию, в то же время ставя в очередь / освобождая от очереди в постоянное время?

Question

Пример ввода:

2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP

Первая строка = Количество «групп», N

После N строк = Первое число - это количество элементов в группе K, следующие числа: Kсами элементы (в диапазоне 0 ... 999999)

Все строки до ввода STOP = запрос либо постановки в очередь, либо удаления из очереди.Если поставить в очередь, вы ставите в очередь элемент, обрабатываемый в данный момент, E, либо в точке A. в конце очереди, если в очереди нет элемента, принадлежащего к той же «группе», что и E или B. сразу за последним элементомкоторый принадлежит к той же «группе», что и E

Удаление очереди просто, просто удалите первый элемент из очереди.Для каждого запроса Dequeue выведите элемент, который был исключен.

Постановка в очередь и освобождение элемента должны занимать только постоянное время

Вывод будет:

101
102
103
201
202
203

Сначала я думаю о каком-то2D вложенной структуры, например, массива очередей или чего-то подобного, но постановка в очередь / снятие очереди не займет постоянного времени, поэтому я не уверен.

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

Answer 1

Предположение: 1. Один элемент принадлежит только одной группе.2. Запрос ENQUEUE будет содержать данные, имеющие запись в одной группе.

Код:

public class Queue {
    private static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
    private static int noOfGroups = 0;
    private static int totalNumberOfElements = 0;
    private static HashMap<String, Element> elementsMap = new HashMap<String, Element>();
    private static HashMap<Integer, Group> groupsMap = new HashMap<Integer, Group>();
    private static Element queueStart = null;
    private static Element queueEnd = null;

    public static void main(String[] args) throws IOException {
        StringBuffer output = new StringBuffer();
        getInput(InputType.NO_OF_GROUP, null);
        for (int groupId = 0; groupId < noOfGroups; ++groupId) {
            getInput(InputType.GROUP_ENTRY, groupId);
        }
        if (elementsMap.size() != totalNumberOfElements) {
            System.err.println(
                    "Note: Same element found on different groups. Group that entered later will be considered.");
        }
        String query;
        while (!"STOP".equals(query = getInput(InputType.QUERY_ENTRY, null))) {
            if (query.equals("DEQUEUE")) {
                Element element = processDEQUEUE();
                if (element != null) {
                    // output the element that is dequeued.
                    output.append(element.getData()).append(System.lineSeparator());
                }
            } else {
                processENQUEUE(query);
            }
        }
        System.out.println(System.lineSeparator() + "Result:");
        System.out.println(output);

    }

    private static void processENQUEUE(String data) {
        Element currentElement = elementsMap.get(data);
        if (currentElement != null) {

            int groupId = currentElement.getGroupId();
            Group currentGroup = groupsMap.get(groupId);

            if (currentGroup.getLast() == null) {
                // Case A:
                // queuing the element "data" at the end of the queue if there's no
                // element in the queue that belongs to the same "group" as "data"
                currentGroup.setLast(currentElement);
                if (queueStart == null) {
                    queueStart = currentElement;
                }
                if (queueEnd == null) {
                    queueEnd = currentElement;
                } else {
                    queueEnd.setNext(currentElement);
                    queueEnd = currentElement;

                }

            } else if (currentGroup.getLast() != null) {
                // Case B:
                // queuing the element "data" right behind the last element which
                // belongs to the same "group" as "data"
                currentElement.setNext(currentGroup.getLast().getNext());
                currentGroup.getLast().setNext(currentElement);
                currentGroup.setLast(currentElement);

            }

        } else {
            System.err.println("Cannot process enqueue for " + data + ". There is no group that contains this data.");
        }

    }

    private static Element processDEQUEUE() {
        Element element = null;
        // removing the first element from the queue.
        if (queueStart == null) {
            System.err.println("Cannot process dequeue. Queue is empty.");
        } else {
            element = queueStart;
            queueStart = queueStart.getNext();
        }
        return element;
    }

    private static String getInput(InputType inputType, Integer groupId) throws IOException {
        boolean isValidInput = false;
        String input = null;
        String message = null;
        String returnValue = null;
        while (!isValidInput) {
            switch (inputType) {
            case NO_OF_GROUP:
                System.out.println("Number of \"groups\": ");
                break;
            case GROUP_ENTRY:
                System.out.println("Group-" + groupId + " Entry: ");
                break;
            case QUERY_ENTRY:
                System.out.println("Query: ");
            }
            input = BR.readLine();
            switch (inputType) {
            case NO_OF_GROUP:
                try {
                    noOfGroups = Integer.parseInt(input);
                    isValidInput = true;
                } catch (NumberFormatException ex) {
                    message = ex.getMessage();
                    isValidInput = false;
                }
                break;
            case GROUP_ENTRY:
                try {
                    String groupInputElements[] = input.split(" ");
                    int noOfElements = 0;

                    noOfElements = Integer.parseInt(groupInputElements[0]);
                    if (groupInputElements.length != noOfElements + 1) {
                        throw new IllegalArgumentException("Expecting " + noOfElements + " elements. Found "
                                + (groupInputElements.length - 1) + " elements.");
                    }
                    groupsMap.put(groupId, new Group());
                    for (int index = 1; index < groupInputElements.length; ++index) {
                        Element element = new Element();
                        element.setGroupId(groupId);
                        element.setData(groupInputElements[index]);
                        elementsMap.put(groupInputElements[index], element);
                    }
                    totalNumberOfElements += noOfElements;
                    isValidInput = true;
                } catch (IllegalArgumentException ex) {
                    message = ex.getMessage();
                    isValidInput = false;
                }
                break;
            case QUERY_ENTRY:
                try {
                    if (!input.contains("ENQUEUE") && !input.equals("DEQUEUE") && !input.equals("STOP")) {
                        throw new IllegalArgumentException("Query can only be ENQUEUE, DEQUEUE or STOP");
                    } else if (input.contains("ENQUEUE")) {
                        String[] enqueueData = input.split(" ");
                        if (enqueueData.length != 2) {
                            throw new IllegalArgumentException(
                                    "Invalid Data. Expected format: ENQUEUE <DATA>\t\tExample: ENQUEUE 101");
                        }
                        returnValue = enqueueData[1];
                    } else {
                        returnValue = input;
                    }
                    isValidInput = true;
                } catch (IllegalArgumentException ex) {
                    message = ex.getMessage();
                    isValidInput = false;
                }
            }
            if (message != null) {
                System.err.println(message);
                message = null;
            }

        }
        return returnValue;
    }

}

enum InputType {
    NO_OF_GROUP, GROUP_ENTRY, QUERY_ENTRY
}

class Element {
    private Element next;
    private int groupId;
    private String data;

    public Element getNext() {
        return next;
    }

    public void setNext(Element next) {
        this.next = next;
    }

    public int getGroupId() {
        return groupId;
    }

    public void setGroupId(int groupId) {
        this.groupId = groupId;
    }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }
}

class Group {

    public Element getLast() {
        return last;
    }

    public void setLast(Element last) {
        this.last = last;
    }

    private Element last;
}

Результат:

Answer 2

Если группы не пересекаются, элементы из каждой группы всегда группируются вместе.Другими словами, у вас есть очередь очередей:

• Для каждой группы создайте (изначально пустую) очередь;
• Создайте структуру индекса для поиска в постоянном временигруппа, соответствующая введенному номеру (решение грубой силы - это массив с 1000000 ссылками, может измениться на HashSet);
• Создать очередь ссылок на очереди («основная» очередь).

Теперь для ENQUEUE X

• Найдите соответствующую очередь для X;
• Добавьте X к ней;если он был пуст, поместите очередь в основную очередь.

For DEQUEUE

• Возьмите первую очередь в главной очереди, удалите из нее элемент dequeue;
• Если он пуст, исключите очередь из основной очереди.