Thread: linked-list queue

  1. #1
    Registered User
    Join Date
    Sep 2005
    Posts
    52

    linked-list queue

    I need to modify this program to use a linked-list implementation of a queue. All of the queue functions must be rewritten. The queue length needs to be defined as 6. Arrange a queue of 6 items, try to enter one more item (make sure that your program produces the warning message about overflow), then delete 3 items, enter 1 more item and display the queue. We just barely covered queues the other day so I really don't understand this too much at all. We never covered how to implement queues with linked-lists either, so this is all new to me. Here is the code I need to rewrite. Please help.

    Code:
    /* queue2.c */
    /* a program to implement a queue using an array of int */
    
    #include <stdio.h>
    #define QSIZE 5
    
    typedef struct{
         int elem[QSIZE];
         int front;
         int rear;
         int count;
    }QType;
          
          /*    function prototypes   */
    void initialize(QType *);
    int empty(QType *);
    int full(QType *);
    int rem(QType *);
    void insert(QType *, int);
    
    main()
    {
       QType Q;     /* queue declaration */
       int code, code1, i, n;
       int i1, i2;
    
       initialize(&Q);
       printf("initially: is empty?\n %d\n", empty(&Q));
       printf("is full?\n %d\n", full(&Q));
    
       printf("Enter 1 to continue, 0 to stop: ");
       scanf("%d", &code);
       while(code!=0)
       {  printf("Enter 2 to insert an item, 3 to remove an item: ");
          scanf("%d", &code1);
          switch(code1)
          {   case 2: printf("Enter an integer to be inserted: ");
                      scanf("%d", &i1);    
                   /*   printf("case2: i1 is %d\n", i1); */
                      insert(&Q, i1);
                      break;
              case 3: i2=rem(&Q);
                      if(i2==0)
                        printf("Nothing is removed\n");
                      else
                        printf("%d is removed\n", i2);
                      break;
              default: printf("Wrong code\n");
          }
          printf("Currently in the queue:\n");
          if(Q.count==0)
             printf("Nothing\n");
          else
          {
          i=Q.front; n=0;
          do{
             printf("%d ", Q.elem[i]);
             n++;
             if(i>=QSIZE-1)
                i=0;
             else
                i++;
             }while(n<Q.count);   
         printf("\n");
         }
       printf("Enter 1 to continue, 0 to stop: ");
       scanf("%d", &code);
       }
       return 0;
    }
    
    void initialize(QType *q)
    /* set head counter and tail counter to 0;   */
    /* set counter of elements in the queue to 0 */
    {   q->front=q->rear=0;
        q->count=0;
    }
    
    int empty(QType * q)
    /* This function will determine if the queue is empty by        */
    /* testing  the value of a counter of elements in the queue.    */
    /* If the queue is empty, this function will print the message  */
    /* "queue is empty" and return a value of 1.                    */
    /* Otherwise, no message is displayed, and zero is returned.    */
    {
       if (q->count == 0)
       { printf("QUEUE IS EMPTY\n");
         return 1;
       }
       else return 0;
    }
    
    int full(QType * q)
    /* This function will determine if the queue is full by    */
    /* testing the value of a counter of elements in the queue.*/
    /* If the queue is full, prints "queue is full" and returns*/
    /* a value of 1. Otherwise, does not print anything        */
    /* and returns zero.                                       */
    {
       if (q->count == QSIZE) 
       {  printf("QUEUE IS FULL\n");
          return 1; 
       }
       else return 0;
    }
    
    int rem(QType *q)
    /* This function will return the item currently located  */
    /* in the head of the queue. Then, the head counter      */
    /* will be incremented.                                  */
    {
       int temp;
    
       if (empty(q)) return 0;
       temp = q->elem[q->front];
       q->front=(q->front+1) % QSIZE;
       (q->count)--;
       return temp;
    }
    
    void insert(QType *q, int item)
    /* The integer 'item' is inserted at the tail of the   */
    /* queue and the tail counter is incremented.          */
    {
       if (full(q)) return;
       q->elem[q->rear] = item;
    /*   printf("in the insert: %d inserted\n", q->elem[q->rear]);*/
       q->rear = (q->rear + 1) % QSIZE;
       (q->count)++;
       return;
    }

  2. #2
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,079
    Are you doing this for class? I don't understand how you could be doing something so advanced in a class, but in your last post you don't understand isdigit() and atof()?

    What is this for?
    Sent from my iPadŽ

  3. #3
    Registered User
    Join Date
    Sep 2005
    Posts
    52
    yes, this is for my level 2 programming course. I think I have figured out the project I referred to in the other post. I will be posting what I have on it in a minute. I am really having trouble with this course right now though that's the reason I need so much help. sorry, this stuff is just confusing to me. I don't think she covers it that well in class. oh yea, also on the isdigit() and the atof() functions, I don't understand them because she hasn't introduced these to us before. this is the first time we've ever used these or even heard of the functions.

  4. #4
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    To see what isdigit() and atof() do, you can always type "man isdigit" in a console window. That's if you are using Linux. Other ressources are also available on this site and on other places on the web
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  5. #5
    Registered User
    Join Date
    Sep 2005
    Posts
    52
    please, someone help me with this. I am still stuck on this. I have been reading stuff on linked-lists throughout these forums, my books, and the internet for about 3 hours tonight and can't even come up with where to start. I don't want anyone to do it for me. I just want someone to breakdown how I should go about this. what type of structures should I be setting up to tackle this project because I don't understand what all I would need?

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    What part don't you know how to do? Make a linked list? Or what exactly?


    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    Registered User
    Join Date
    Sep 2005
    Posts
    52
    ok. here is about as much code as I can come up with. the link-list queue needs to be limited to only 6 nodes. I don't know how to implement. also, I'm not sure if this code will work correctly. please point out any problems and give suggestions.

    Code:
    #include <stdio.h>
    #define QSIZE 6
    
    typedef struct QueueNodeTag {
       int Item;
       struct ListNode_tag * next;
    } QueueNode;
    
    typedef struct {
       QueueNode *Front;
       QueueNode *Rear;
    } Queue;
          
    void initialize(Queue *Q);
    int empty(Queue *);
    int full(Queue *);
    int rem(Queue *, int *);
    void insert(int , Queue *);
    
    main()
    {
       Queue Q;
       int code, code1, i, n;
       int i1, i2;
    
       initialize(&Q);
       printf("initially: is empty?\n %d\n", empty(&Q));
       printf("is full?\n %d\n", full(&Q));
    
       printf("Enter 1 to continue, 0 to stop: ");
       scanf("%d", &code);
       while(code!=0)
       {  printf("Enter 2 to insert an item, 3 to remove an item: ");
          scanf("%d", &code1);
          switch(code1)
          {   case 2: printf("Enter an integer to be inserted: ");
                      scanf("%d", &i1);
                      insert(i1,&Q);
                      break;
              case 3: i2=rem(&Q, &i2);
                      if(i2==0)
                        printf("Nothing is removed\n");
                      else
                        printf("%d is removed\n", i2);
                      break;
              default: printf("Wrong code\n");
          }
          printf("Currently in the queue:\n");
          if(Q.count==0)
             printf("Nothing\n");
          else
          {
          i=Q.front; n=0;
          do{
             printf("%d ", Q.elem[i]);
             n++;
             if(i>=QSIZE-1)
                i=0;
             else
                i++;
             }while(n<Q.count);   
         printf("\n");
         }
       printf("Enter 1 to continue, 0 to stop: ");
       scanf("%d", &code);
       }
       return 0;
    }
    
    void initialize(Queue *Q)
    {   Q->Front = NULL;
        Q->Rear = NULL;
    }
    
    int empty(Queue *Q)
    {
       return (Q->Front == NULL);
    }
    
    int full(Queue *Q)
    {
      return 0;
    }
    
    int rem(Queue *Q, int *F)
    {
        QueueNode *Temp;
    
        if (Q->Front == NULL) {
    	printf("Cannot delete an empty queue.");
        } else {
              *F = Q->Front->Item;
    	  Temp = Q->Front;
    	  Q->Front = Temp->Link;
    	  free(Temp);
    	  if (Q->Front == NULL) Q->Rear = NULL;
          }
    
    }
    
    void insert(int R, Queue *Q)
    {
       QueueNode *Temp;
    
       Temp = (QueueNode *) malloc(sizeof(QueueNode);
    
       if (Temp == NULL) {
             printf("Insufficient memory.");
       } else {
    	Temp->Item = R;
    	Temp->Link = NULL;
           if (Q->Rear == NULL) {
                Q->Front = Temp;
                Q->Rear = Temp;
            } else {
    	     Q->Rear->Link = Temp;
    	     Q->Rear = Temp;
    }

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You're still not answering my question. This is really your whole problem. You're just throwing code at it, in hopes it fixes whatever problem you're having. You're not taking the time to simply state what it is you are trying to do, what you can do, and what you can't do. You're just vomiting code in hopes that some of it is correct.

    So, one more time, what exactly are you having problems with?


    Quzah.
    Hope is the first step on the road to disappointment.

  9. #9
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Heres a hint: Write a function that will tell you how many nodes are in the list. If its more then X don't insert anymore.

    Of course implimenting a queue using a link list with a fixed and low queue size is just dumb

  10. #10
    Registered User
    Join Date
    Sep 2005
    Posts
    52
    I think my main problem is that I'm just not really sure at all how to create a queue using a linked-list. I have read through my book but it really doesn't help much, also, I have looked at examples on the internet but I'm just not really sure about them. The code I put up last, seems like the idea that I get of a queue using linked-lists. The problem I am running in to now is I'm not sure if that would work correctly and I don't have any function to limit the queue to only six nodes. The only thing I can think of would to make a variable to keep count each time a node is created but then, it seems like once you deleted a node, the count would be the same and not allow you to create another node when you should be able to.

  11. #11
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    I don't have any function to limit the queue to only six nodes.
    You can count the number of items in a linked list like this:
    Code:
    for(cur = head, count = 0; cur; cur = cur->next) {
        count ++;
    }
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  12. #12
    Registered User
    Join Date
    Mar 2005
    Location
    Mountaintop, Pa
    Posts
    1,058
    Here is a link to a demonstration of a sorted doubly linked list. It can be used as a starting point for this project. The SDL list should be changed to a singular linked list. This is done by removing the pointer references to priorPtr.

    Also, the queue functions have to be added to this code along with other linked list functions. But at least now you have a starting point.

    Linked List discussion

  13. #13
    Registered User
    Join Date
    Sep 2005
    Posts
    52
    ok, I read everything in the forum link you gave me and multiple explanations in internet articles, and I think I get the concept. the only problem is the code will not compile. when trying to compile it says that the variables within the structure do not exist. I don't understand why it is saying this or any of the other erros I am getting. please help me to get this program to compile.

    Code:
    #include <stdio.h>
    #define QSIZE 6
    
    struct node {
       int data;
       struct Node * next;
       };
    
    typedef struct node Node;
    
    struct queue {
       struct Node * front;
       struct Node * rear;
       int count;};
    
    typedef struct queue Queue;
    
    void initialize(Queue *Q);
    int empty(Queue *);
    int full(Queue *);
    int rem(Queue *,int *);
    void insert(int , Queue *);
    
    main()
    {
       Queue Q;
       int code, code1, i, n;
       int i1, i2;
       
       initialize(&Q);
       printf("initially: is empty?\n %d\n", empty(&Q));
       printf("is full?\n %d\n", full(&Q));
    
       printf("Enter 1 to continue, 0 to stop: ");
       scanf("%d", &code);
       while(code!=0)
       {  printf("Enter 2 to insert an item, 3 to remove an item: ");
          scanf("%d", &code1);
          switch(code1)
          {   case 2: printf("Enter an integer to be inserted: ");
                      scanf("%d", &i1);
                      insert(i1,&Q);
                      break;
              case 3: i2=rem(&Q, &i2);
                      if(i2==0)
                        printf("Nothing is removed\n");
    		  else
                        printf("%d is removed\n", i2);
                      break;
              default: printf("Wrong code\n");
          }
          printf("Currently in the Queue:\n");
          if(Q.count==0)
             printf("Nothing\n");
          else
          {
          i=Q.front; n=0;
          do{
             printf("%d ", Q.data);
             n++;
             if(i>=QSIZE)
                  i=0;
             else
                i++;
             }while(n<Q.count);
          printf("\n");
          }
        printf("Enter 1 to continue, 0 to stop: ");
        scanf("%d", &code);
        }
        return 0;
    }
    
    void initialize(Queue *Q)
    {   Q.Front = NULL;
        Q.Rear = NULL;
        Q.Count = 0;
    }
    
    int empty(Queue *Q)
    {
       if (Q.Front == NULL);
       { printf ("Queue IS EMPTY\n")
         return 1;
       }
       else return 0;
    }
    
    int full(Queue *Q)
    {
      if (Q.count == QSIZE);
      {  printf("Queue IS FULL\n");
         return 1;
      }  else return 0;
    }
    
    int rem(Queue *Q, int *F)
    {
        Node *Temp;
    
        if (Q.Front == NULL) {
    	printf("Cannot delete an empty Queue.");
        } else {
    	  (Q.count)--;            *F = Q.Front.Item;
    	  Temp = Q.Front;
    	  Q.Front = Temp.Link;
    	  free(Temp);
    	  if (Q.Front == NULL) Q.Rear = NULL;
          }
    }
    
    void insert(int R, Queue *Q)
    {
       Node *Temp;
    
       Temp = (Node *) malloc(sizeof(Node);
    
       if (full(Q)) return;
       if (Temp == NULL) {
             printf("Insufficient memory.");
       } else {
    	(Q.Count)++;
    	Temp.Data = R;
    	Temp.Link = NULL;
           if (Q.Rear == NULL) {
                Q.Front = Temp;
                Q.Rear = Temp;
            } else {
    	     Q.Rear.Link = Temp;
    	     Q.Rear = Temp;
    }
    Last edited by the_winky_files; 11-15-2005 at 03:18 PM.

  14. #14
    Registered User
    Join Date
    Mar 2005
    Location
    Mountaintop, Pa
    Posts
    1,058
    The code above needs a lot of work. So, I've listed below some starter code below. The remaining code will be displayed on this forum if you thoroughly comment the code below. Everything in the Add2Queue function has to be explained in detail. I would suggest you start by reviewing the excellent linklist tutorials on this site. If I'm thoroughly satisifed with your comments, the remaining code will be posted. Otherwise, good luck

    Bob

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct QueueNode {
        int iData;
        int iPriority;
        struct QueueNode *next;
    };
    
    int Add2Queue(struct QueueNode **QueueNodeFirst, struct QueueNode **QueueNodeLast,
        int iPriority, int iInput)
    {
        struct QueueNode *QueueNodeTemp1  = NULL; 
        struct QueueNode *QueueNodeTemp2 = NULL;
    
        if((QueueNodeTemp1 = malloc(sizeof(struct QueueNode)))  == NULL)
            return 1;
        QueueNodeTemp1->iData = iInput;
        QueueNodeTemp1->iPriority = iPriority;
        QueueNodeTemp1->next = NULL;
        if(*QueueNodeLast == NULL)
        {
            *QueueNodeLast = QueueNodeTemp1;
            *QueueNodeFirst = *QueueNodeLast;
        } 
        else
        {
            if((*QueueNodeFirst)->iPriority < iPriority)
            {
                QueueNodeTemp1->next = *QueueNodeFirst;
                *QueueNodeFirst = QueueNodeTemp1;
            } 
            else {
                if((*QueueNodeLast)->iPriority > iPriority)
                {
                    (*QueueNodeLast)->next = QueueNodeTemp1;
                    *QueueNodeLast = QueueNodeTemp1;
                } 
                else {
                    QueueNodeTemp2 = *QueueNodeFirst;
                    while((QueueNodeTemp2->next)->iPriority >= iPriority)
                    {
                        QueueNodeTemp2 = QueueNodeTemp2->next;
                    }
                    QueueNodeTemp1->next = QueueNodeTemp2->next;
                    QueueNodeTemp2->next = QueueNodeTemp1;
                }
            }
        }
        return 0;
    }
    
    int main(void)
    {
        struct QueueNode *QueueNodeFirst = NULL;
        struct QueueNode *QueueNodeLast = NULL;
        int iInput = 4, iPriority = 1;
        if(Add2Queue(&QueueNodeFirst, &QueueNodeLast, iInput, iPriority))
            return 1;
        return 0;
    }
    Last edited by BobS0327; 11-15-2005 at 06:01 PM.

  15. #15
    Registered User
    Join Date
    Sep 2005
    Posts
    52
    I tried to explain what each line of code was doing to the best of my ability. I'm pretty sure I understand all of what is going on here. The main concern which I have with this program is the priority. What is exactly is this for? Thanks for trying to help also. This thing is due tuesday which means I have to have it done by Friday night because I am going out of town Saturday, so I need to hurry and get this thing completed.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct QueueNode {   /*Declaration of the structure for the nodes*/
        int iData;       /* Data type to be stored in node */
        int iPriority;   
        struct QueueNode *next;  /* Points to the next node, linking them */
    };
    
    int Add2Queue(struct QueueNode **QueueNodeFirst, struct QueueNode **QueueNodeLast,
        int iPriority, int iInput) /* Definition of the function which accepts 4 parameters.  2 structure pointers being passed by address with ** so you can change the address of the original structure through derefrencing. iNput is the number to be added to the queue */
    {
        struct QueueNode *QueueNodeTemp1  = NULL; 
        struct QueueNode *QueueNodeTemp2 = NULL;  /* Declares two temporary pointer structures */
    
        if((QueueNodeTemp1 = malloc(sizeof(struct QueueNode)))  == NULL) /* Creates a node and tests if it is equal to NULL */
            return 1;
        QueueNodeTemp1->iData = iInput;  /* Sets the iData varible in the temporary structure equal to 4 */
        QueueNodeTemp1->iPriority = iPriority;  /* Sets the iPriority varible in the temporary structure equal to 1 */
        QueueNodeTemp1->next = NULL;  /* Sets the next variable in the temporary structure equal to NULL */
        if(*QueueNodeLast == NULL) /* Tests the condition if the Last node address is equal to NULL */
        {
            *QueueNodeLast = QueueNodeTemp1; /* If Last node address is equal to NULL then make the Last node point to the Temp1 node */
            *QueueNodeFirst = *QueueNodeLast;  /* If Last address value is equal to NULL then the first Node points to the Last node */
        } 
        else
        {
            if((*QueueNodeFirst)->iPriority < iPriority) /* Else the first Node's iPriority is less than 1 */
            {
                QueueNodeTemp1->next = *QueueNodeFirst; /* Sets Temp1 Node's next value equal to the address of the First Node */
                *QueueNodeFirst = QueueNodeTemp1;  /* Makes the First node point to the Temp1 Node */
            } 
            else {
                if((*QueueNodeLast)->iPriority > iPriority)  /* If the Last Node's priority is greater than the 1 */
                {
                    (*QueueNodeLast)->next = QueueNodeTemp1;  /* Makes the Last Node's next pointer point to the Temp1 Node */
                    *QueueNodeLast = QueueNodeTemp1;  /* Makes the Last Node point to the Temp1 Node */
                } 
                else {
                    QueueNodeTemp2 = *QueueNodeFirst;  /* If all previous conditions fail, Temp2 Node points to the first Node */
                    while((QueueNodeTemp2->next)->iPriority >= iPriority)  /*While Temp2's iPriority variable is greater than or equal to the 1 */
                    {
                        QueueNodeTemp2 = QueueNodeTemp2->next;  /* Points Temp2 node to where Temp2's next variable points */
                    }
                    QueueNodeTemp1->next = QueueNodeTemp2->next;  /* Makes Temp1's next pointer variable point to where Temp2's next variable is pointing */
                    QueueNodeTemp2->next = QueueNodeTemp1;  /* Makes Temp2's next pointer variable point to Temp1 node */
                }
            }
        }
        return 0;
    }
    
    int main(void)
    {
        struct QueueNode *QueueNodeFirst = NULL;
        struct QueueNode *QueueNodeLast = NULL;
        int iInput = 4, iPriority = 1;
        if(Add2Queue(&QueueNodeFirst, &QueueNodeLast, iInput, iPriority))
            return 1;
        return 0;
    }
    Last edited by the_winky_files; 11-15-2005 at 07:53 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  2. linked list question
    By mikeman in forum C Programming
    Replies: 1
    Last Post: 11-30-2008, 01:56 PM
  3. Anyone good with linked list.....I am not....
    By chadsxe in forum C++ Programming
    Replies: 11
    Last Post: 11-10-2005, 02:48 PM
  4. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 09:27 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM