Thread: Help with FIFO queue

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    51

    Help with FIFO queue

    Firstly this was set for coursework last week. The deadline has now passed and it is no longer being done for a grade. I would just like help getting started. I have been given the follwing header file outline :

    Code:
    /* file: myqueue.h -- definitions for queue manipulation routines. */
    
    #ifndef QUEUE_DEFINED
    #define QUEUE_DEFINED
    
    typedef struct qitem {
            struct qitem *next;
            char *data;
    } Qitem;
    typedef struct queue {
            Qitem *front, *back;
    } MyQueue;
    
    int queue_init(MyQueue *q);                 /* return -1 on error */
    int queue_empty(MyQueue *q);                /* return 1 if empty; else 0 */
    int queue_put(MyQueue *q, Qitem *new_item); /* return -1 on error */
    Qitem *queue_get(MyQueue *q); /* return (Qitem *)0 if the queue is empty */
    
    #endif
    
    /* end file: myqueue.h */
    With the instruction :

    Tasks

    1. Create a new file myqueue.c and #include the header file shown below.
    2. Implement the functions listed in myqueue.h (see below)
    3. Write a main() function that uses the functions from myqueue.h, and allows the user to:
    * Create new queues.
    * Add an element to a specified queue.
    * Remove an element and display its data.
    * Display the number of elements in a queue.
    * Display an entire queue, without removing elements.
    4. Ensure your program is robust at dealing with errors such as attempting to remove an element where none exist.
    5. Ensure that all memory which was malloc'd is free'd before your program exits

    Note that the queue_*() functions should not refer at all to the data field of Qitem.

    I understand it mostly but unsure how to start. Mainly where and how I initialise the "q" variable which is passed to several of the functions in the header file. Especially given that I don't know how many queues the user will want to create.

    I have a switch statement coded ready to select 1 to create a queue but am unsure of where to go from here. As I say I am looking for help, not for the work to be done for me.

    Any help really appreciated

  2. #2
    Registered User
    Join Date
    Feb 2009
    Posts
    35
    I think you should begin by first writing each of the functions in the header file, dont worry about the main for now.

    you might also like to write a test function so that you know your functions are working as desired.

    what does this function do?
    Code:
    int queue_init(MyQueue *q);

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Martin_T View Post
    Firstly this was set for coursework last week. The deadline has now passed and it is no longer being done for a grade. I would just like help getting started. I have been given the follwing header file outline :

    Tasks

    1. Create a new file myqueue.c and #include the header file shown below.
    2. Implement the functions listed in myqueue.h (see below)
    3. Write a main() function that uses the functions from myqueue.h, and allows the user to:
    * Create new queues.
    * Add an element to a specified queue.
    * Remove an element and display its data.
    * Display the number of elements in a queue.
    * Display an entire queue, without removing elements.
    4. Ensure your program is robust at dealing with errors such as attempting to remove an element where none exist.
    5. Ensure that all memory which was malloc'd is free'd before your program exits

    Note that the queue_*() functions should not refer at all to the data field of Qitem.

    I understand it mostly but unsure how to start. Mainly where and how I initialise the "q" variable which is passed to several of the functions in the header file. Especially given that I don't know how many queues the user will want to create.

    I have a switch statement coded ready to select 1 to create a queue but am unsure of where to go from here. As I say I am looking for help, not for the work to be done for me.
    That's a convenient story and whilst it may be true, I'm rather skeptical. Regardless, it doesn't change what I will and will not help with.

    That said, you should probably just declare a MyQueue variable (not a pointer), and pass its address into the queue_init function, which will set both members to NULL. From there I would find a good tutorial on building and working with linked lists. See where that takes you and get back to us.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Nov 2009
    Posts
    51
    Quote Originally Posted by Brain_Child View Post
    I think you should begin by first writing each of the functions in the header file, dont worry about the main for now.

    you might also like to write a test function so that you know your functions are working as desired.

    what does this function do?
    Code:
    int queue_init(MyQueue *q);
    Thankyou for reply, il try that.

    I think it initialises the queue somehow. It is not clear,I've pretty much pasted in the information I have.

  5. #5
    Registered User
    Join Date
    Nov 2009
    Posts
    51
    Quote Originally Posted by iMalc View Post
    That's a convenient story and whilst it may be true, I'm rather skeptical. Regardless, it doesn't change what I will and will not help with.

    That said, you should probably just declare a MyQueue variable (not a pointer), and pass its address into the queue_init function, which will set both members to NULL. From there I would find a good tutorial on building and working with linked lists. See where that takes you and get back to us.
    I guess it does sound hard to believe.

    Anyway, as I say i'm just looking for guidance like this, not answers.

    I'll try and make a start and let you know how it goes.

  6. #6
    Registered User
    Join Date
    Nov 2009
    Posts
    51
    I think with me not even being able to do this (last weeks work) I might see if I can drop this module. I still can't get started.

    The queue structure requires a *front and *back element to initialise as you will see from the above code. You will also see the initialise function only takes in one parameter "q". So I have no idea how I will initialise a front and back node given that we are told

    Note that the queue_*() functions should not refer at all to the data field of QItem
    So where do i initialise the front and back nodes? Given I can't refer to them in the header file and I can't pass them in as parameters TO the function.

    I really have no clue.

  7. #7
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    When you initialize the queue, there won't be any forward node or backward node to point to, so set them to null. (aka, initialize them).
    Mainframe assembler programmer by trade. C coder when I can.

  8. #8
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    The queue_init function takes a pointer to an anchor that you will define in main. This is the variable you will use to anchor your queue all throughout your program (just like iMalc said). If you've worked with scanf(), you would pass the address of your anchor just like you would pass the address of a receiving variable in scanf().
    Mainframe assembler programmer by trade. C coder when I can.

  9. #9
    Registered User
    Join Date
    Nov 2009
    Posts
    51
    Firstly, thankyou for your time and for replying. It is REALLY appreciated

    Ok, this is beginning to make sense now..... I think

    So I could declare a queue item as simply as

    Code:
    MyQueue queue1;
    Then call

    Code:
    queue_init(queue1)
    Then within that function I would simply set

    Code:
    *q = (MyQueue*)malloc(sizeof(MyQueue));
    q->front=NULL;
    q->back=NULL;
    Am I on the correct track or miles off?

  10. #10
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Martin_T View Post
    Am I on the correct track or miles off?
    Your are close. Here's a few technical details to consider. This is your prototype:
    Code:
    int queue_init(MyQueue *q);
    Notice "q" is a pointer.

    Now, you have two choices. #1, if you want to declare and pass in a "MyQueue" like this:
    Code:
    MyQueue queue1;
    queue_init(&queue1);
    First, notice I used the "address of" operator (&) since queue1 was not declared a pointer. That means queue1 already has assigned local stack space in the calling function (presumably main), so you should not malloc anything in queue_init IF you want to go that route.

    The other choice is to declare and submit a pointer:
    Code:
    MyQueue *queue1;
    queue_init(queue1);
    In this case, you DO need to malloc heap space for queue1. This is possibly better, depending on how the queue1 variable is going to be used.

    There is, I think, a significant issue to consider.
    3. Write a main() function that uses the functions from myqueue.h, and allows the user to:
    * Create new queues.
    That means you will need an indeterminate number of variables in main() to represent the queues! You cannot hardcode them (queue1, queue2, etc), you in effect need a dynamic array.

    Main() should contain the "user interface", ie, a simple menu of choices in the form of a switch/case, one of which is going to be "create new queue". Furthermore, you will also need a way to "select active queue" unless you intend to offer a choice of available queues everytime the user wants to add an item to a queue, etc (getting to sound like a lot of work, isn't it?) IMO, your prof made a bad call not including some kind of char "label" in the MyQueue struct. Without that, you will have to keep track of the user's "name" for each queue seperately, perhaps a parallel array of these:

    Code:
    typedef struct _listing {
         MyQueue *que;
         char label[32];
    } QueueTag;
    Anyway, here's a possibility for the dynamic array:
    Code:
    	int i;
    	MyQueue **queues=NULL, **tmp=NULL;
    	for (i=0; i<6; i++) {
    		tmp = realloc(queues,(i+1)*sizeof(MyQueue*));
    		if (tmp) queues = tmp;
    		else return -1; /* handle error */
    		queues[i] = malloc(sizeof(MyQueue));
    		queues[i]->front = NULL;
    		queues[i]->back = NULL;
    	}
    This creates an array of six queues. The last three lines would be taken care of in a call to init_queue (probably also a good place to maintain the global QueueTag list), this is just an illustration -- obviously, you do not want to arbitrarily create an array of six, but you do want to add one each time the user creates a new one, in more or less the same way.

    Some things to note:
    • **queues is a "pointer to pointer(s)"
    • **tmp is just to allow us to check the return value of realloc. Really, you should also check the return value of the malloc() in a similar way (but "out of memory" errors are rare, or even impossible on eg, a normal linux system)
    • **queues is allocated space for pointers -- sizeof(MyQueue*), but each element in queues is a pointer and needs further space to actually contain data, so it is malloced sizeof(MyQueue) BEFORE we set its internal elements "front" & "back" (even tho they are just set to NULL, NULL is still a value that requires a place to be stored).


    Quote Originally Posted by Martin_T View Post
    I think with me not even being able to do this (last weeks work) I might see if I can drop this module.
    If you are studying programming, I presume you will have to redo this in time. Also, if you are studying programming, IMO you better deal with this now, it involves a number of essential and fundamental concepts in C.

    If you are not studying programming, you may want to consider that this looks like a labour intensive course and whether you can eat everything you put on your plate.
    Last edited by MK27; 11-08-2009 at 09:59 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  11. #11
    Registered User
    Join Date
    Nov 2009
    Posts
    51
    Thankyou so much for your time. You have made the issue alot clearer. I am going to sit down with this, read over it again with the code in front of me and see where I get to. It will be alot further now thanks to your time and effort.

    p.s. I am not studying programming soley. I have done two semesters of Java last year and this is the only C programming I am or will be doing for the remained of the course. The course lasts until December and the remainder of the C programming will be based on networks. We are not taught any C, just set a task per week along with a very small handout explaining a few basic concepts we will need to know. For the % of the course it is worth it is VERY time consuming for me.

    Thanks again

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Memory Fragmentation with Dynamic FIFO Queue
    By fguy817817 in forum Linux Programming
    Replies: 17
    Last Post: 10-31-2009, 04:17 AM
  2. Help with FIFO QUEUE
    By jackfraust in forum C++ Programming
    Replies: 23
    Last Post: 04-03-2009, 08:17 AM
  3. Fixing my program
    By Mcwaffle in forum C Programming
    Replies: 5
    Last Post: 11-05-2008, 03:55 AM
  4. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 09:09 PM
  5. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 11:39 AM