The infamous Carwash Queue example...

This is a discussion on The infamous Carwash Queue example... within the C Programming forums, part of the General Programming Boards category; Hello all, this is actually my first post on this threat, but I really need the help. I currently have ...

  1. #1
    Registered User
    Join Date
    Mar 2007
    Posts
    2

    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.

  2. #2
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    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.

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,422
    Create another variable called carBeingWashed.
    Which has a counter initialised to 10 minutes.
    Which you count down to zero in a series of 1-minute 'ticks'.

    When the count reaches 0, you print
    20 departure 44

    At that time, you move the next car in the list into the car wash.

    Whenever you add a car to the list, you check to see if the car wash is empty or not.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    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;
    }

  5. #5
    Registered User
    Join Date
    Mar 2007
    Posts
    2
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with FIFO QUEUE
    By jackfraust in forum C++ Programming
    Replies: 23
    Last Post: 04-03-2009, 08:17 AM
  2. Fixing my program
    By Mcwaffle in forum C Programming
    Replies: 5
    Last Post: 11-05-2008, 02:55 AM
  3. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 09:09 PM
  4. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 11:39 AM
  5. queue help
    By Unregistered in forum C Programming
    Replies: 2
    Last Post: 10-29-2001, 08:38 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21