当前位置: 首页 > 知识库问答 >
问题:

实现一个队列,在该队列中,您可以在固定时间内排队/退队时在特定位置插入元素?

姚高韵
2023-03-14

输入样本:

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)

停止输入之前的所有行=排队或出列查询。如果排队,则您正在将当前正在处理的元素E排队,在A处。如果队列中没有与E或B属于同一“组”的元素,则在队列的末尾。位于与E属于同一“组”的最后一个元素的正后方

出列很简单,只需从队列中删除第一个元素。对于每个出列查询,输出出列的元素。

一个元素的排队和退队应该只需要固定的时间

产出将是:

101
102
103
201
202
203

我最初考虑的是某种2D嵌套结构,比如队列数组之类的,但是排队/出队不会花费恒定的时间,所以我不确定。

另外,我在查询之前就得到了元素本身这一事实应该是一个提示,但我不确定是什么。

共有2个答案

支劲
2023-03-14

假设:1。一个元素只属于一个组。2.排队查询将包含在一个组中有条目的数据。

代码

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;
}
孔永年
2023-03-14

如果组不相交,则来自每个组的图元始终聚集在一起。换句话说,您有一个队列:

  • 对于每个组,创建一个(初始为空)队列;
  • 创建一个索引结构,用于对输入的数字对应的组进行恒定时间搜索(蛮力解决方案是一个有1000000引用的数组,可以改为HashSet);
  • 创建队列引用队列(主队列)。

现在为排队X

  • 查找X对应的队列

对于DEQUEUE

  • 取主队列中的第一个队列,从中取出元素
 类似资料:
  • 问题内容: 我有一个作业,使用另一个作业的参数触发了该作业。每次给工作分配不同的参数- 运行哪个修订版。 我不想允许同一作业的并发运行,但是我想在该作业的队列中允许多个挂起的构建。 从我尝试过的方法来看,它无效,无论队列中触发了多少个构建,我都只能在队列中看到一个待完成的构建。 任何插件都有可能吗? 问题答案: 如果Jenkins已经包含具有相同param值的构建,则不会将其放置在队列中。 为此,

  • 我有一个简单的场景,有两个线程,第一个线程永久读取一些数据,并将这些数据排入队列。第二个线程首先从队列中查看单个对象,并进行一些条件检查。如果这些都是好的,单个对象将被出列并传递给一些处理。 我尝试过使用< code>ConcurrentQueue,这是一个简单队列的线程安全实现,但是这个队列的问题是所有调用都被阻塞了。这意味着,如果第一个线程正在将一个对象入队,第二个线程就不能查看对象或将其出队

  • 问题内容: 我的ActiveMQ服务器中目前有一个名为的队列。每当消息处理失败时,ActiveMQ都会创建一个默认目录。是否可以将该名称更改为类似的名称?原因是将来我可能会有几个队列,而我希望它像 问题答案: 您要查找的东西称为,在此过程中,ActiveMQ为每个队列/主题创建特定的DLQ, 您可以按如下,通过调整你实现它有点 此配置将创建名称为的DLQ ,如果您不需要前缀,则可以删除属性。 希望

  • 我有一个使用Spring和RabbitMQ的项目设置。目前,我的应用程序可能会收到一条amqp消息,在另一个异步进程完成之前无法处理该消息(遗留和完全分离,我无法控制)。因此,结果是我可能不得不等待处理消息一段时间。其结果是变压器出现异常。 当消息被NACK回rabbitMQ时,它会将其放回队列的头部,并立即重新拉入队列。如果我收到的无法处理的消息等于并发侦听器的数量,我的工作流就会被锁定。它转动

  • 问题内容: 当前的Go库不提供队列容器。为了实现一个简单的队列,我使用圆形数组作为基础数据结构。它遵循TAOCP中提到的算法: 以下是代码: 但是输出显然是错误的: 1是2是3是4是5是6是7是8是9是10是11是12是 11是12是0错误0错误0错误0错误0错误0错误0错误0错误0错误0错误0错误0错误 我认为我还需要一个领域来使代码正常工作。你有什么建议? 改进的代码有一个小的缺点:大小为n的

  • 问题内容: 我正在尝试编写一个解决方案,其中单个线程会生成可并行执行的I / O密集型任务。每个任务都有重要的内存数据。因此,我希望能够限制当前待处理的任务数。 如果我这样创建ThreadPoolExecutor: 然后,当队列已满并且所有线程都已经繁忙时,抛出该异常。 当队列已满并且所有线程都忙时,我该怎么做才能阻塞? 编辑 :我试过了: 它以某种微妙的方式达到了我想要达到的效果(基本上被拒绝的