Special view of the queue

Question

I am looking for something like a queue that will allow me to put items at the end of the queue and push them at the beginning, as a regular queue does.

The difference is that I also need to squeeze the queue from time to time. This means that I have the following items in my queue (each character, including a dot, is an element in the queue):

ed . c . b . a (this Queue has 8 items) 

Then I need, for example, to remove the last point to get:

 ed . c . ba 

Is there anything similar in Java Collection classes? I need to use this for a program that I am doing, where I cannot use anything but Java classes. I am not allowed to create it for myself. I'm just using LinkedList for the time being, but I thought it might be more like a queue than LinkedList.

thanks

change

Basically, this is what a project is: There is a traffic light that can be either green (and the associated symbol is “-”) or red (“|”). This traffic light is on the right: alt text http://img684.imageshack.us/img684/9602/0xfhiliidyxdy43q5mageu0.png At the beginning you have no cars, and the traffic light is green, so our list is presented as:

 ....... - 

Now, in the next iteration, I have a random variable that will tell me wherever the car is or not. If the car comes, we will see it on the left. At each iteration, all the machines move one step to the right. If they have a car right on the right, then they cannot move:

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

and etc.

Now it happens that sometimes the traffic light may turn red ('-'). In this case, if you have several cars, then even if they have some distance between them when driving, when they should stop at the traffic lights, they will be close:

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

Now that’s why it works as a queue, but sometimes I have to shoot these points when cars approach a red traffic light. Keep in mind that the size of the street here is 7 characters, but sometimes it grows, so we cannot assume that this is a fixed list of lengths.

Answer 1

Homework / school projects are always complex, adding subtle things to requirements that can make someone's brain melt. Do you have any requirements for including spaces in the queue?

Personally, I would not do this if it was not explicitly required: it seems easier to present your cars as “Car”, “Space pairs” (you can define a pair as a structure, assuming that you are allowed to use structures), where space is a numerical value, representing the space for the next car in the car. Then, to compress, you only need to look at the list items: when you find Space > 0 , do Space--; return; Space--; return; , and all other cars will already be "advanced", as they save space with those in front of them. To conclude, make sure that you select Space points for each car after (if the brake light is on the right and cars go to the left) or earlier (the brake light on the left and cars coming to the right) the car itself, and there you go. Also note that the Space first car is the distance to the brake light itself, since there is no car in front of it.

If you add a pointer to the next car in the struct (and a null pointer to the last car), you already have a linked list: save the "global" variable pointing to the first car (or null for an empty queue). Since Java does not directly support pointers, turn the structure into a class and use "object references" (which are the same as pointers for all purposes other than C'ish pointer arithmetic), and there you go: only one class built from scratch. The only thing you need to touch on Java libraries is standard IO and maybe a little string manipulation, which is an inherent need for input and output input (some colleges have their own IO libraries, but it doesn't have much values ​​here). To go through the queue, you would do something like this (assuming the class is called "Node", which is a fairly common and explicit name 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 may have to take turns to figure out how far from the last a new car will appear; when you do, save the link from the last node and make its “next” breakpoint a 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, configure the constructor for everything you have.

Given that this is a college project, we’ll look at some details: the compact time of the process becomes O(n) , and the memory usage is O(0) (the process itself does not need any “local” variables, other than, possibly, a pointer to moving the collection, which does not depend on the length of the queue.) In addition, the use of memory for the queue itself will be guaranteed to be less or equal to the fact that it will represent spaces as elements (it only gets to be equal in the worst case scenario when enough cars are stuck in red light). Thus, if the requirements do not contain something that is incompatible with this approach, I would expect that it will be what your teachers want: it is reasoned, effective and corresponds to what you were asked about.

Hope this helps.

Answer 2

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

Now the queue can be implemented in any way; either with a linked list or with an array. I think you're on the right track. A linked list will definitely make things easier.

You will have O (1) to add and delete with your queue (if you maintain a link to the front and back), but in the worst case, O (p) to compact (delete a point).

I believe that there may be a way to reduce the compact operation to O (1) (if you delete only one point at a time) if you use a secondary data structure. You need another queue (implemented using another linked list) that maintains a link to the points in the first linked list.

So, when you insert (a,., B, c,., D), you have a list that looks like this:

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

and you also have a secondary queue (implemented as a linked list) that supports a point reference:

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

Then, when you need to perform the compact operation, all you have to do is remove the first element from the second queue and save the link. So now you have a link to the point that is in the middle of the first linked list. Now you can easily remove this point from the first list.

You mentioned in a comment that you need to track an order. A queue, by definition, is an ordered structure (in the sense that things remain in the order in which they were inserted). So all you have to do is insert the link to the point in the second place when you insert the point in the first. Thus, the order is preserved. Therefore, when you remove the link to a point from the second line, you have a link to the actual and corresponding point in the first line.

The tradeoff here for speed is that you need more memory because you maintain a second list of links. The worst case requirement is 2x of what you are using now. But it is a worthy compromise to get O (1) versus O (n).

Answer 3

I would say that LinkedList would be the best approach here ... since LinkedList allows you to push / pop front / back and allows you to delete an item in the middle of the list.

Obviously, the search time sucks, but if you add / remove a list from the front / rear list more often, and then look up, then I would say stick with LinkedList.

Answer 4

Maybe a second LinkedList that stores the dot element?