特殊类型的队列

发布于 2024-08-26 00:23:06 字数 1311 浏览 2 评论 0原文

我正在寻找类似队列的东西，它允许我将元素放在队列的末尾并在开头将它们弹出，就像常规队列一样。

不同之处在于我还需要不时压缩队列。假设我的队列中有以下项目（每个字符，包括点，都是队列中的一个项目）：

e d . c . b . a
(this Queue has 8 items)

然后，我需要删除最后一个点，以便得到：

e d . c . b a

有什么吗就像 Java Collection 类中那样？我需要将其用于我正在执行的程序中，除了 Java 类之外我不能使用任何东西。我不被允许为自己设计一款。目前我只使用 LinkedList，但我想这可能更像是队列而不是 LinkedList。

谢谢

编辑：

基本上，该项目的内容如下：有一个交通灯可以是绿色（相关符号为“-”）或红色（“|”）。那个红绿灯在右边：替代文本 http://img684.imageshack.us/img684/9602/0xfhiliidyxdy43q5mageu0.png< /a> 一开始，你没有任何汽车，交通灯是绿色的，所以我们的列表表示为：

.......  -

现在，在下一次迭代中，我有一个随机变量，它会告诉我哪里有车来或没有车。如果有一辆车驶来，那么我们可以看到它从左边出现。在每次迭代中，所有汽车都向右移动一步。如果他们的右边有任何汽车，那么他们就不能移动：

a......  -   (iteration 1)
.a.....  -   (iteration 2)
..a....  -   (iteration 3)

等等。

现在，发生的情况是有时交通灯会变成红色（'-'）。在这种情况下，如果你有几辆车，那么即使它们在移动时之间有一定距离，当它们必须停下来等待红绿灯时，它们也会靠近：

...b.a.  -   (iteration n)
....b.a  -   (iteration n+1)
.....ba  -   (iteration n+2) here they got close to each other

现在，这就是为什么它像队列一样工作的原因，但是有时，当汽车靠近红色交通灯时，我必须记下这些点。还要记住，这里街道的大小是 7 个字符，但它有时会增长，所以我们不能假设这是一个固定长度的列表。

原文

I am looking for something like a Queue that would allow me to put elements at the end of the queue and pop them out in the beginning, like a regular Queue does.

The difference would be that I also need to compact the Queue from time to time. This is, let's assume I have the following items on my Queue (each character, including the dot, is an item in the Queue):

e d . c . b . a
(this Queue has 8 items)

Then, I'd need for example to remove the last dot, so to get:

e d . c . b a

Is there anything like that in the Java Collection classes? I need to use this for a program I am doing where I can't use anything but Java's classes. I am not allowed to design one for myself. Currently I'm just using a LinkedList, but I thought maybe this would be more like a Queue than a LinkedList.

Thanks

edit:

Basically here is what the project is about:
There is a traffic light that can be either green(and the symbol associated is '-') or red('|'). That traffic light is on the right:
alt text http://img684.imageshack.us/img684/9602/0xfhiliidyxdy43q5mageu0.png
In the beggining, you don't have any cars and the traffic light is green, so our list is represented as:

.......  -

Now, on the next iteration, I have a random variable that will tell me wherever there is a car coming or not. If there's a car coming, then we can see it appearing from the left. At each iteration, all cars move one step to the right. If they have any car directly on their right, then they can't move:

a......  -   (iteration 1)
.a.....  -   (iteration 2)
..a....  -   (iteration 3)

etc.

Now, what happens is that sometimes the traffic light can turn red('-'). In that case, if you have several cars, then even if they had some distance between them when moving, when they have to stop for the traffic light they will get close:

...b.a.  -   (iteration n)
....b.a  -   (iteration n+1)
.....ba  -   (iteration n+2) here they got close to each other

Now, that is the reason why this works like a Queue, but sometimes I have to take down those dots, when the cars are near the red traffic light.
Keep also in mind that the size of of the street here was 7 characters, but it sometimes grows, so we can't assume this is a fixed length list.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

水波映月 2024-09-02 00:23:06

队列基本上是具有已定义行为的项目列表，在本例中为 FIFO（先进先出）。您可以在末尾添加项目，并从开头删除它们。

现在队列可以以您选择的任何方式实现；使用链表或数组。我认为你走在正确的道路上。链接列表肯定会让事情变得更容易。

对于队列的添加和删除，您的时间复杂度为 O(1)（如果您维护对前面和后面的引用），但压缩（删除点）的最坏情况将是 O(n) 。

我相信如果您使用辅助数据结构，可能有一种方法可以将compact操作减少到O(1)（如果您一次只删除一个点）。您需要的是另一个队列（使用另一个链表实现），它维护对第一个链表中点的引用。

因此，当您插入 (a, ., b, c, ., d) 时，您会得到一个如下所示的列表：

[pointer to rear] -> [d] -> [.] -> [c] -> [b] -> [.] -> [a] <- [pointer to front]

并且您还有一个辅助队列（实现为链表），它维护对点的引用：

[pointer to rear] -> [reference to second dot] -> [reference to first dot] <- [pointer to front]

然后，当您需要执行紧凑操作时，您所要做的就是从第二个队列中删除第一个元素并保留引用。现在您有了对第一个链表中间的点的引用。您现在可以轻松地从第一个列表中删除该点。

您在评论中提到您需要跟踪订单。根据定义，队列是一种有序结构（在某种意义上，事物保持其插入的顺序）。因此，当您将点插入第一个队列时，您需要做的就是将对该点的引用插入到第二个队列中。这样，秩序就得以维持。因此，当您从第二个队列中提取对点的引用时，您将获得对第一个队列中实际对应点的引用。

这里速度的权衡是您需要更多内存，因为您要维护第二个引用列表。最坏情况下的内存需求是您现在使用的内存的 2 倍。但这对于获得 O(1) 与 O(n) 来说是一个不错的权衡。

A queue is basically a list of items with a defined behavior, in this case FIFO (First In First Out). You add items at the end, and remove them from the beginning.

Now a queue can be implemented in any way you choose; either with a linked-list or with an Array. I think you're on the right path. A linked list would definitely make it easier.

You'll have O(1) for the add and the remove with your queue (if you maintain a reference to the front and the back), but the worst-case scenario for compacting (removing the dot) would be O(n).

I believe there might be a way to reduce the compact operation to O(1) (if you're only removing one dot at a time) if you use a secondary data structure. What you need is another queue (implemented using another linked-list) that maintains a reference to dots in the first linked list.

So, when you insert (a, ., b, c, ., d) you have a list that looks like:

[pointer to rear] -> [d] -> [.] -> [c] -> [b] -> [.] -> [a] <- [pointer to front]

and you also have a secondary queue (implemented as a linked list) that maintains a reference to the dot:

[pointer to rear] -> [reference to second dot] -> [reference to first dot] <- [pointer to front]

Then, when you need to perform a compact operation, all you have to do is remove the first element from the second queue and retain the reference. So you now have a reference to a dot that is in the middle of the first linked list. You can now easily remove that dot from the first list.

You mentioned in a comment that you need to keep track of the order. A queue by definition is an ordered structure (in the sense that things remain in the order they were inserted). So all you need to do is insert a reference to the dot into the second queue when you insert a dot into the first. That way, order is maintained. So when you pull off a reference to a dot from the second queue, you have a reference to the actual and corresponding dot in the first queue.

The trade-off here for speed is that you need more memory, because you're maintaining a second list of references. Worst-case memory requirement is 2x what you're using now. But that is a decent trade-off to get O(1) vs O(n).

回复收藏 0 原文

弄潮 2024-09-02 00:23:06

家庭作业练习/学校项目总是很棘手，在要求中添加微妙的东西可能会让某人的大脑崩溃。您是否需要将空格包含在队列中？

就我个人而言，除非明确要求，否则我不会这样做：将您的汽车表示为 Car、Space 对（您可以将这对定义为结构体，假设您可以使用结构体）似乎更简单，其中 space 是表示的数值车辆中下一辆车的空间。然后，为了压缩，您只需要查看列表项：当您找到具有 Space > 的列表项时0，做空格--； return;，所有其他汽车都已经“前进”了，因为它们与前面的汽车保持了空间。为了输出，请确保在之后（如果红绿灯位于右侧并且汽车来自左侧）或之前（红绿灯位于左侧且汽车来自右侧）为每辆车抛出 Space 点）汽车本身，就这样。另请注意，第一辆车的 Space 表示到红绿灯本身的距离，因为它前面没有车辆。

如果您向结构体添加一个指向下一辆车的指针（以及最后一辆车的空指针），则您已经有了一个链表：保留一个指向第一辆车的“全局”变量（或空队列的 null ）。由于 Java 不直接支持指针，因此将结构体转换为类并使用“对象引用”（除了 C'ish 指针算术之外，它与用于所有目的的指针相同），然后就可以了：只构建了一个类从头开始。 Java 库中您唯一需要接触的是标准 IO，也许还有一些字符串操作，这是由于必须接受输入并生成输出而产生的固有需求（一些大学有自己的课程特定的 IO）库，但这并没有多大区别）。要循环遍历队列，您需要执行以下操作（假设该类名为“Node”，这是非常通用且明显的字段名称）：

for(Node pos = First; pos != null; pos = pos.Next) {
    /* Do your stuff here, knowing that "pos" points to the "current" item on each iteration. */
}

要添加新节点，您可能必须遍历队列才能找出位置新车将与最后一辆汽车相距多远；当您这样做时，保留最后一个节点的引用并将其“下一个”引用指向新节点：

Node last = First;
int distance = 0;
for(Node pos = First; pos != null; pos=pos.Next) {
    distance += pos.Space;
    last = pos;
}
last.Next = new Node(the_letter_for_this_car, MaxDistance-distance, null);

当然，请将构造函数调整为您拥有的任何内容。

考虑到这是一个大学项目，让我们看一下一些细节：紧凑的处理时间变为 O(n) ，内存使用量为 O(0) （进程本身不需要任何“本地”变量，除了可能需要一个指针来遍历与队列长度无关的集合。）此外，队列本身的内存使用量保证小于或等于它将空间表示为项目（只有在最坏的情况下，当有足够多的汽车被困在红灯时，它才会相等）。因此，除非要求包含与此方法不兼容的内容，否则我希望这就是您的老师想要的：它是合理的、高效的并且符合您的要求。

希望这有帮助。

Homework exercises/school projects are always tricky, adding subtle stuff to the requirements that may make someone's brain melt down. Do you have any requirement to include the spaces as part of the queue?

Personally, I wouldn't do that unless explicitly required: it seems simpler to represent your cars as Car, Space pairs, (you can define the pair as a struct, assuming you are allowed to use structs) where space is a numeric value representing the space towards the next car in the vehicle. Then, to compact, you only need to look through the list items: when you find one that has Space > 0, do Space--; return;, and all other cars will have already "advanced", as they keep the space with the ones in front of them. In order to output, make sure to toss out Space dots for each car after (if the stoplight is at the right and the cars come from the left) or before (stoplight at left and cars coming from right) the car itself, and there you go. Also note that the Space of the first car represents the distance to the stoplight itself, since it has no car before it.

If you add to the struct a pointer to the next car (and a null pointer for the last car), you already have a linked list: keep a "global" variable that points to the first car (or null for an empty queue). Since Java doesn't directly supports pointers, turn the struct into a class and use "object references" (which are the same as pointers for all purposes other than C'ish pointer arithmetics), and there you go: only one class, built from scratch. The only thing you'll need to touch from Java's libraries is the standard IO and, maybe, a bit of string manipulation, which is an inherent need derived from having to take input and produce output (some colleges have their own course-specific IO libraries, but that doesn't make a big difference here). To loop through the queue you'd do something like this (assuming the class is named "Node", which is quite generic, and obvious names for the fields):

for(Node pos = First; pos != null; pos = pos.Next) {
    /* Do your stuff here, knowing that "pos" points to the "current" item on each iteration. */
}

To add new nodes you probably have to traverse the queue to figure out at which distance from the last will the new car "spawn"; when you do so keep the reference from the last node and make its "next" reference point to the new node:

Node last = First;
int distance = 0;
for(Node pos = First; pos != null; pos=pos.Next) {
    distance += pos.Space;
    last = pos;
}
last.Next = new Node(the_letter_for_this_car, MaxDistance-distance, null);

Of course, tune the constructor to whatever you have.

Considering that this is a college project, let's take a look at some details: the compact process time becomes O(n) and it's memory usage is O(0) (the process itself doesn't need any "local" variables, other than maybe a pointer to traverse the collection which is independent from the length of the queue.) In addition, the memory usage for the queue itself is guaranteed to be smaller or equal to what it would be representing the spaces as items (it only gets to be equal on the worst scenario, when enough cars are stuck at a red light). So, unless the requirements include something incompatible with this approach, I'd expect this to be what your teachers want: it's reasoned, efficient, and compliant to what you were asked for.

Hope this helps.

回复收藏 0 原文