Like Tree9Likes

Accessing next entry in a queue.

This is a discussion on Accessing next entry in a queue. within the C Programming forums, part of the General Programming Boards category; Hello, I would like to check whether a driver's name is listed under available drivers in a drivers' queue, using ...

  1. #1
    Registered User
    Join Date
    Apr 2013
    Posts
    122

    Accessing next entry in a queue.

    Hello,
    I would like to check whether a driver's name is listed under available drivers in a drivers' queue, using the following function:
    Code:
    int isDriverInQueue(Driver * driversQueue, char* name);
    whereas:
    Code:
    typedef struct driver{
    	char name[101];
    	int priority;
    	struct driver* next;
    }Driver;
    typedef struct taxiSystem{
    	Driver * driversQueue;
    	Order * ordersQueue;
    	int numOrder;
    }TaxiSystem;
    What I am not sure of is how to actually move within the queue to the next driver? Is that implemented simply by doing next++, where next is as defined above?

  2. #2
    Registered User migf1's Avatar
    Join Date
    May 2013
    Location
    Athens, Greece
    Posts
    235
    Better try: p = p->next

    But if you have a queue structure, the whole purpose is to only use enqueue() and dequeue() for adding and removing elements.

  3. #3
    Registered User
    Join Date
    Apr 2013
    Posts
    122
    Forgive me, what I meant to write was:could accessing the next entry be accomplished via - driversQueue->next++?

  4. #4
    Registered User migf1's Avatar
    Join Date
    May 2013
    Location
    Athens, Greece
    Posts
    235
    Quote Originally Posted by peripatein View Post
    Forgive me, what I meant to write was:could accessing the next entry be accomplished via - driversQueue->next++?
    The typical purpose of using a queue in the 1st place is to hide away the internal implementation and define at least the enqueue() and dequeue() operations for handling elements in FIFO order (First In First Out).

    You enqueue elements at the back and you dequeue them from the front of the queue.

    You can also define additional operations, say peek() for example in order to check the element at the front without removing it.

    That being said, since internally your queue is implemented as a linked list, and you don't mind violating its classic usage principles, then you could set a pointer p at the back and iterate through until the front element, by ...

    Code:
    p = p->next;
    Last edited by migf1; 06-07-2013 at 08:53 AM. Reason: typo: had LIFO instead of FIFO

  5. #5
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,802
    Incrementing pointer types as you are doing would attempt to change the value pointer itself by sizeof(Driver) bytes. It would not allow you to "move within the queue". This would invalidate the next pointer causing it to point to an incorrect address. Subsequent operations on this mangled pointer would result in weirdness.

    This brings up the issue of const correctness. Your compiler would (should if it is a decent one) tell you you were doing something wrong in the isDriverInQueue function had you used the appropriate const qualifiers. Since the function should logically not mess with either of the pointers passed into it, the function should be declared as follows:

    Code:
    	
    int isDriverInQueue(const Driver * const driversQueue, const char* const name);
    Now if you tried to do any kind of naughty next++ business, the compiler would object... and rightfully so with a slap upside yo' head.

    What you were trying to do does work in the world of C++ container objects where you can increment/decrement iterators to items in those containers (the iterators have this behavior coded for them). But this is not the case using pointers in C.

    migf1's solution is the one to use here. Your function should have some sort of temp pointer that you can use to "iterate" through the queue/list.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  6. #6
    Registered User
    Join Date
    Apr 2013
    Posts
    122
    I was instructed to thus declare my function.
    As I am quite new to using structs and pointers, I am not certain how to approach this and would by all means appreciate some more punctual guidance.
    Ergo, would/could the following allow me to determine whether a driver with a given name is listed as available?
    Code:
    int isDriverInQueue(Driver * driversQueue, char* name){
        for (; driversQueue->next[i] != NULL; i++)
        if strcmp(driversQueue->next->name, name) return 1;
        return 0;
    
    }
    Last edited by peripatein; 06-07-2013 at 12:47 PM.

  7. #7
    Registered User
    Join Date
    Apr 2013
    Posts
    122
    Or perhaps thus:
    Code:
    int isDriverInQueue(Driver * driversQueue, char* name){
        int i = 0;
    	while (driversQueue->next++ != NULL)
        if strcmp(driversQueue->name, name) return 1;
        return 0;
     
    }

  8. #8
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,802
    Post #6 assumes an array of "next" pointers with some trailing NULL marking the last array element. The strcmp operation does not change at all repeatedly testing the same single name element in the passed in pointer and not checking any of the ones.

    Post #7 again makes the mistake of attempting to increment a pointer (an error which again would be caught if you were employing proper const-correctness) by some fixed amount equal to sizeof(Driver) instead of actually walking through the array from element to element.

    Your if statement has a syntax error (missing parenthesis).

    You also need to remember that strcmp returns 0 when the strings match and a non-zero value when the strings do not match. Assuming you simply added the aforementioned parenthesis to correct that syntax error, your current comparison would immediately return 1 (true) the first time it came across a non-matching name and would return 0 (false) only if all names matched the test string.

    Try this:
    Code:
    int isDriverInQueue(const Driver * const driversQueue, const char* const name)
    {
        Driver * currDriver = driversQueue;
        while ( currDriver != NULL )
        {
            if ( !strcmp(currDriver->name, name) ) return 1;
            currDriver = currDriver->next;
        }
        return 0;
    }
    If you wanted to, you could forgo the const bits here since at least the rest of the code isn't attempting to modify the input parameters.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  9. #9
    Registered User migf1's Avatar
    Join Date
    May 2013
    Location
    Athens, Greece
    Posts
    235
    Quote Originally Posted by hk_mp5kpdw View Post
    ...
    If you wanted to, you could forgo the const bits here since at least the rest of the code isn't attempting to modify the input parameters.
    And perhaps changing ...

    Code:
    ...
        Driver * currDriver = driversQueue; 
    ...
    to...
    Code:
    Driver *currDriver = (Driver *)driversQueue;
    to spare the compiler warning "const qualifier was dropped" or something similar (at least with gcc).

  10. #10
    Registered User
    Join Date
    Apr 2013
    Posts
    122
    Why couldn't I use driversQueue itself? Why is there a need to declare currDriver?

  11. #11
    Registered User
    Join Date
    Apr 2013
    Posts
    122
    Could I write it thus?:


    Code:
    int isDriverInQueue(Driver * const driversQueue, char* const name)
    {
        if (driversQueue == NULL) return 0;
        return (!strcmp(driversQueue->name, name) ? 1 : isDriverInQueue(driversQueue->next, name));
    }

  12. #12
    Registered User
    Join Date
    Apr 2013
    Posts
    122
    Furthermore, I'd now like to create a function the purpose of which is to delete from the Order's queue a specific order for the driver with the given name. May I write it thus? (Please note that the declarations themselves of the relevant struct and the function are a given)
    Code:
    typedef struct order{
    	int orderID;
    	int isSpecific;
    	char specificDriver[101];
    	struct order* next;
    }Order;
    int removeOrderByName(TaxiSystem * system, char * name){
    	while (system->ordersQueue != NULL && !strcmp(system->ordersQueue->specificDriver, name))
    		system->ordersQueue = system->ordersQueue->next;
    	free(system);
    	return 1;
    }

  13. #13
    Registered User migf1's Avatar
    Join Date
    May 2013
    Location
    Athens, Greece
    Posts
    235
    Quote Originally Posted by peripatein View Post
    Why couldn't I use driversQueue itself? Why is there a need to declare currDriver?
    Because the queue nodes are not stored consecutively in memory. So, applying a ++ on a queue node does not move you to the next node.

    In other words, node++ is quite different than node->next.

    If you had implemented the queue as an array instead of a linked-list, then nodes would actually be consecutive array slots and there would be no need to have defined a separate next field inside struct Driver. In that case, you could indeed use ++ to iterate through all indices (nodes) of the array.

    But here your queue is implemented as a linked-list, not as an array.

  14. #14
    Registered User migf1's Avatar
    Join Date
    May 2013
    Location
    Athens, Greece
    Posts
    235
    Quote Originally Posted by peripatein View Post
    Could I write it thus?:


    Code:
    int isDriverInQueue(Driver * const driversQueue, char* const name)
    {
        if (driversQueue == NULL) return 0;
        return (!strcmp(driversQueue->name, name) ? 1 : isDriverInQueue(driversQueue->next, name));
    }
    It looks fine to me.

  15. #15
    Registered User
    Join Date
    Apr 2013
    Posts
    122
    Alright, thanks. And what about the function
    Code:
    intremoveOrderByName(TaxiSystem * system, char* name)
    ?
    Is it coded correctly?

Page 1 of 6 123456 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. (queue*)this)->queue::qput does not have class type
    By brack in forum C++ Programming
    Replies: 13
    Last Post: 11-11-2010, 02:41 PM
  2. DNS entry changes
    By Thantos in forum Tech Board
    Replies: 4
    Last Post: 09-02-2003, 08:57 PM
  3. Min, Max field entry?
    By JCCC in forum C Programming
    Replies: 1
    Last Post: 04-16-2002, 07:46 PM
  4. Registry entry from AIM help!
    By SyntaxBubble in forum Windows Programming
    Replies: 3
    Last Post: 01-02-2002, 04:00 PM
  5. Queue and Priority Queue
    By Pamela in forum C++ Programming
    Replies: 1
    Last Post: 12-07-2001, 10:09 PM

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