Thread: The infamous Carwash Queue example...

Hello all, this is actually my first post on this threat, but I really need the help. I currently have an assignment for my CS1 class where we are to create a queue for a carwash by reading a txt file for different times cars tried to get into a queue of max = 5 cars. I decided to use linked lists instead of a circular queue just because I am more comfortable with it. My issue is this: I have all the functions set up and I can scan the file just fine, but I just dont know when to dequeue. When I dequeue right after I enqueue, then the next car does not go into the queue since there is no car in front of it! So am I supposed to create an additional node as the car bay? Below is an example of the exercise:

txt file: (first number is the time or arrival and second is the car ID)

10 44
15 56
30 64
...

output: (by the way, the time per wash is 10 mins)
10 arrival 44
15 arrival 56
20 departure 44
25 departure 56
30 arrival 64
...

I apologize if my explanation is confusing, but I would appreciate any help. From what I understand, this is a popular example in CS classes.

Thank you very much.

I'm somewhat confused at what your problem is.... Suppose you receive 4 cars.... So your linked list of nodes representing cars could look something like this:

Code:

Car 4 -> Car 3 -> Car 2 -> Car 1 -> NULL

When you need to dequeue, that will eliminates Car 1 from the list, and set Car 2's next node to NULL.

Code:

Car 4 -> Car 3 -> Car 2 -> NULL

If you enqueue another request, it should look like this:

Code:

Car 5 -> Car 4 -> Car 3 -> Car 2 -> NULL

To be honest, though, the efficiency for this using a single linked list is not good if you need to cycle through the entire list each time you need to find the last element. One thing you could do is have a pointer always set to the second last car in the queue (or the last one if this is a doubly-linked list) and then you always can find the element to dequeue and the previous element to set the next one to NULL.

What you need is a FIFO (First In, First Out) list. I would suggest when you enqueue a car, that you add it to the head of the list and when you dequeue, you remove the last car from the list.

Your code could look like this (pseudo-C):

Code:

struct node
{
    int ID,
    node *next;
};

struct list
{
    int size,
    node *head;
};

void addCar(int ID, struct list *myList)
{
    struct *node = malloc(sizeof(struct node));
    node->ID = ID;
    node->next = list->head;
    myList->head = node;
}

Thank you everybody for your help.
Mcgyver:
It is more like
Car 1 -> Car 2 -> Car 3 -> Car 4 -> NULL
Car would be the head node, which would be dequeued whenever the function is called. Any additional nodes would be added behind the rear node, in this case, Car 4. Because I have a pointer for the last and first element, it does not have to cycle through the whole list since it already knows where the last element is. Hope that clarifies things :-)

KONI:
Your code is very similar with what I currently have. I guess my real question is whether I should make the wash station a node. So that the REAL head node in the queue would be Q->head->next. Salem's suggestion also makes sense, and in this case, I would not need an additional node for the station.

Thanks