Special kind of queue

Question

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.

Answer 1

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).

Answer 2

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.