Thread: FIFO Queue

  1. #1
    Registered User
    Join Date
    Oct 2019
    Posts
    81

    FIFO Queue

    I am trying to understand queue in c language. I have gone through page Programming Concepts: Queues - Wikibooks, open books for an open world

    Code:
    #include<stdio.h>
    
    #include<stdlib.h> 
        
    struct Queue  
    { 
      int data;              
      struct Queue *Next;  
    }; 
    
    
    
    
    int main() 
    { 
      struct Node* Front = NULL; 
      
      return 0; 
    }
    I am planning two write two functions, enqueue to insert data into queue and dequeue to delete. I don't understand how to implement.

    I would apricate for any help


  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,658
    I would suggest you start with a simple finite array version you can prototype with to make sure everything works as you expect.
    Code:
    struct Queue {
      int data[10];
      int front;
      int back;
    };
    
    void queueInit(struct Queue *q);  // Initialise
    void queueFini(struct Queue *q);  // Cleanup
    void queueEnqueue(struct Queue *q, int data);  // enqueue a value
    void queueDequeue(struct Queue *q, int *data); // dequeue a value
    int queueIsEmpty(struct Queue *q);  // is it empty?
    When that works, then you can do this.
    Code:
    struct QueueData
    { 
      int data;              
      struct QueueData *Next;  
    }; 
    struct Queue {
      struct QueueData *front;
      struct QueueData *back;
    };
    void queueInit(struct Queue *q);  // Initialise
    void queueFini(struct Queue *q);  // Cleanup
    void queueEnqueue(struct Queue *q, int data);  // enqueue a value
    void queueDequeue(struct Queue *q, int *data); // dequeue a value
    int queueIsEmpty(struct Queue *q);  // is it empty?
    Notice the interface to the functions does NOT change just because you changed the inside of struct Queue.

    So whatever 'main' you had to test the queue functionality with should continue to work when you've changed the implementation.
    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.

  3. #3
    Registered User
    Join Date
    Oct 2019
    Posts
    81
    Quote Originally Posted by Salem View Post

    Code:
    void queueInit(struct Queue *q);  // Initialise
    .
    Salem, Thank you

    What function queueInit(struct Queue *q); supposed to do ?

  4. #4
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    242
    Quote Originally Posted by gajya View Post
    Salem, Thank you

    What function queueInit(struct Queue *q); supposed to do ?
    Consider the state of this object:

    Code:
    struct Queue q;
    The object's members are most likely "pointing" to invalid memory addresses. The queueInit function is simply defined to ensure that the data structure is initialized properly. (Setting all pointers to zero, for example.)

  5. #5
    Registered User
    Join Date
    Apr 2021
    Posts
    38
    Quote Originally Posted by gajya View Post
    Salem, Thank you

    What function queueInit(struct Queue *q); supposed to do ?
    When you are seated at a table in a restaurant, what does the table look like?

    That's what queueInit() does. It "sets the table." It doesn't know who is going to eat, or how many, or what they will have. It just ensures that there is a clean table, with napkins, maybe some condiments, maybe some small plates and water glasses, maybe a tablecloth, the chairs are straight and in the right position, etc.

    If your queue is using an array, then there are probably some integers telling how many values are stored. At the start, queueInit would set them to zero.

    If your queue is using a linked list, then there might be an integer length, which should start at zero. And there would be a "head" pointer to the first node in the linked list, which should be set to null.

    If your queue is using a dictionary, then there should be an empty dictionary.

    If your queue is using a file, there should be a filename, maybe a file handle or file pointer, all set up.

    The point is, whatever your queue does, the queueInit() function should set it up to the "empty" state.

  6. #6
    Registered User
    Join Date
    Oct 2019
    Posts
    81
    Quote Originally Posted by Sir Galahad View Post
    (Setting all pointers to zero, for example.)
    I think I have done

    Code:
    #include<stdio.h>#include<stdlib.h> 
        
    struct Queue {
      int data[10];
      int front;
      int back;
    };
    
    
    void queueInit(struct Queue *q)  // Initialise
    {
    	
        q-> data[10] = 0;
    	q-> front = NULL;
    	q-> back = NULL;
    }
    
    
    
    
    int main() 
    { 
       struct Queue *q =  NULL;
       q = malloc(sizeof(*q));
      
       queueInit(q); 
       
      return 0; 
    }

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,323
    The idea is to pass a pointer to a struct Queue object to queueInit so that queueInit can supply the initial values which will then be reflected in the object from the caller. You don't have to use dynamic memory allocation for this, e.g., to keep things simple you could have written:
    Code:
    struct Queue q;
    queueInit(&q);
    Anyway, in queueInit, this is wrong:
    Code:
    q-> data[10] = 0;
    What you're doing is setting the element of data at index 10 to 0. Since data only has 10 elements, there is no element at index 10, so you have accessed the array out of bounds.

    Also, this can work:
    Code:
    q-> front = NULL;
    q-> back = NULL;
    but it is conceptually wrong: NULL is a null pointer constant, so it is meant to be used in a pointer context, not in an integer context. You should just use 0 (but then you may have to consider how you will differentiate between a queue with one item and a queue with no items, e.g., will the back index mean "one past the end", i.e., the index of the next item to be enqueued?)
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User
    Join Date
    Oct 2019
    Posts
    81
    Quote Originally Posted by laserlight View Post
    The idea is to pass a pointer to a struct Queue object to queueInit so that queueInit can supply the initial values which will then be reflected in the object from the caller. You don't have to use dynamic memory allocation for this, e.g., to keep things simple you could have written:
    Am I doing that ?
    Both pointers initially at 0

    Code:
    #include<stdio.h>
    
    #include<stdlib.h> 
        
    struct Queue {
      int data[10];
      int front;
      int back;
    };
    
    
    
    
    void queueInit(struct Queue *q)  // Initialise
    {
    	q->data[0] = 0; 
    	q->front = 0;
        q->back = 0;	
    	
    }
    
    
    int main() 
    { 
       struct Queue *q = NULL;
    
    
       queueInit(&q);  
       
      return 0; 
    }

  9. #9
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,658
    This should be
    Code:
       struct Queue q;
       queueInit(&q);
    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.

  10. #10
    Registered User
    Join Date
    Oct 2019
    Posts
    81
    Quote Originally Posted by Salem View Post
    This should be
    Code:
       struct Queue q;
       queueInit(&q);
    @Salem I think I have done

    Code:
    #include<stdio.h>  
    #include<stdlib.h> 
          
    struct Queue {
      int data[10];
      int front;
      int back;
    };
     
     
    void queueInit(struct Queue *q)  // Initialise
    {
        (*q).data[0] = 0;
        (*q).front = 0;
        (*q).back = 0;     
    } 
     
     
    void queueEnqueue(struct Queue *q, int data)  // enqueue a value
    {
        (*q).data[0] = data;   // add 1 into queue 
        (*q).front = 0;
        (*q).back = 0;     
    }
      
    int main() 
    { 
    
    
      struct Queue q;
      queueInit(&q); 
      queueEnqueue(&q, 1);  // enqueue a value
      
        
      return 0; 
    }
    Now I need help in enqueue
    Last edited by gajya; 05-14-2021 at 12:27 AM.

  11. #11
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,658
    Enqueue is
    q->data[q->front++] = data;

    Dequeue is
    return q->data[q->back++];

    Well that's the essential part, you need to
    - check the queue isn't full when adding
    - check the queue isn't empty when removing
    - wrap around the indices when the end of the array is reached.
    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.

  12. #12
    Registered User
    Join Date
    Oct 2019
    Posts
    81
    Quote Originally Posted by Salem View Post
    Enqueue is
    q->data[q->front++] = data;

    Dequeue is
    return q->data[q->back++];
    I don't understand these two lines exactly what happens

    Code:
    #include<stdio.h>  
    
    #include<stdlib.h> 
    
    
    #define size  10
    #define  True  1
           
    struct Queue {
      int data[size];
      int front;
      int back;
    };
      
      
    void queueInit(struct Queue *q)  // Initialise
    {
        q->data[0] = 0;
        q->front = 0;
        q->back = 0;     
    } 
      
     int queueIsEmpty() // is it empty?
     {
         if (size < 0)
             return True; 
     }
      
      int queueIsFull()  // is it Full?
     {
         if ( size == 10)
             return True; 
     }
     
    void queueEnqueue(struct Queue *q, int data)  // enqueue a value
    {
        if (queueIsEmpty()== 1)
        {
            
        }
    
    }
    
    
    void queueDequeue(struct Queue *q, int *data) // dequeue a value
    {
        if (queueIsFull()== 1)
        {
            
        }
    }
       
    int main() 
    { 
     
      struct Queue q;
      queueInit(&q); 
      queueEnqueue(&q, 1);  // enqueue a value
         
      return 0; 
    }

  13. #13
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,658
    Your size is the size of the array, which is constant.

    You want the number of elements presently stored in the queue.
    In rather simplistic terms, this is just front - back.
    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.

  14. #14
    Registered User
    Join Date
    Oct 2019
    Posts
    81
    Quote Originally Posted by Salem View Post
    Your size is the size of the array, which is constant.

    You want the number of elements presently stored in the queue.
    In rather simplistic terms, this is just front - back.
    sorry but still I don't have clear idea

    Code:
    #include<stdio.h>   
    #include<stdlib.h> 
     
     
    #define size  10
    #define  True  1
            
    struct Queue {
      int data[size];
      int front;
      int back;
    };
       
       
    void queueInit(struct Queue *q)  // Initialise
    {
        q->data[0] = 0;
        q->front = 0;
        q->back = 0;     
    } 
       
     int queueIsEmpty() // is it empty?
     {
         if (size < 0)
             return True; 
     }
       
      int queueIsFull()  // is it Full?
     {
         if ( size == 10)
             return True; 
     }
      
    void queueEnqueue(struct Queue *q, int data)  // enqueue a value
    {
        if (queueIsEmpty()== 1)
        {
             q->data[0] = data;
    		 printf ("%d",  q->data);
    		 q->front++; 
    		 
        }
     
    }
     
     
    int main() 
    { 
      
      struct Queue q;
      queueInit(&q); 
      queueEnqueue(&q, 1);  // enqueue a value
     
      return 0; 
    }

  15. #15
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,658
    Code:
    #define CAPACITY  10
    #define  True  1
             
    struct Queue {
      int data[CAPACITY];
      int front;
      int back;
      int size;
    };
        
        
    void queueInit(struct Queue *q)  // Initialise
    {
        q->data[0] = 0;
        q->front = 0;
        q->back = 0;     
        q->size = 0;
    } 
        
     int queueIsEmpty(struct Queue *q) // is it empty?
     {
         return q->size == 0 
     }
        
      int queueIsFull(struct Queue *q)  // is it Full?
     {
         return q->size == CAPACITY; 
     }
    void queueEnqueue(struct Queue *q, int data)  // enqueue a value
    {
        if (!queueIsFull(q))  // it's not full
        {
             q->data[q->front] = data; // store at the front of the queue
             q->front++; // move to next free slot
             q->size++;  // and count the number added
        }
    }
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. FIFO queue vs Link List
    By DeeMan in forum C Programming
    Replies: 8
    Last Post: 02-16-2013, 08:29 PM
  2. Priority queue and FIFO
    By Elysia in forum C++ Programming
    Replies: 12
    Last Post: 02-29-2012, 02:32 PM
  3. Help with FIFO queue
    By Martin_T in forum C Programming
    Replies: 10
    Last Post: 11-08-2009, 10:30 AM
  4. understanding queue FIFO
    By arastoo.s in forum C Programming
    Replies: 6
    Last Post: 08-18-2009, 10:16 AM
  5. Help with FIFO QUEUE
    By jackfraust in forum C++ Programming
    Replies: 23
    Last Post: 04-03-2009, 08:17 AM

Tags for this Thread