FIFO Queue

[gajya]

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

#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

[Salem]

I would suggest you start with a simple finite array version you can prototype with to make sure everything works as you expect.

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.

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.

[gajya]

void queueInit(struct Queue *q);  // Initialise

.

Salem, Thank you

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

[Sir Galahad]

Salem, Thank you

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

Consider the state of this object:

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.)

[gajya]

(Setting all pointers to zero, for example.)

I think I have done

#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; 
}

[aghast]

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.

[laserlight]

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:

struct Queue q;
queueInit(&q);

Anyway, in queueInit, this is wrong:

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:

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?)

[gajya]

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

#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; 
}

[Salem]

This should be

   struct Queue q;
   queueInit(&q);

[gajya]

This should be

   struct Queue q;
   queueInit(&q);

@Salem I think I have done

#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

[aghast]

@Salem I think I have done

#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

Okay, but ...

First, let's talk about notation:

    (*q).data[0] = data;
 
    q->data[0] = data;

Those two lines ^^ mean exactly the same thing.

In C, the -> operator was created specifically to create a shorthand for (*pointer).member expressions. In much the same way that the ++ and -- operators were created as a shorthand for x = x + 1. They're the same under the hood.

So, first of all, you wrote a completely valid expression, and that statement is totally correct.

But, second of all, the "idiomatic" way to write that is to use the -> operator, and every C programmer (including me) is going to read that, wince, and go "okay, but ..."

Next, let's talk about "meanings." You have a queue of your own data type. How do you know when the queue is empty? How do you know when the queue is not empty? How do you know how many values are in the queue? Also, how do you handle an error? If the queue has 10 values in it and I call enqueue, what will happen? If the queue has no values in it and I call dequeue, what will happen?

(This is not a trick question: these are normal conditions that can be expected to occur. The designer of the library, which in this case is YOU has to make the rules for this. So... what are the rules?)

Now here are some more questions. Given this code:

    typedef struct Queue Queue;
    
    extern bool    q_is_empty(Queue *);
    extern size_t  q_length(Queue *);
    extern error_t q_enqueue(Queue *, value_t data);

    struct Queue * q = &(struct Queue){ .data = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, .front=0, .back=0 };

    printf("%s\n", q_is_empty(q) ? "empy" : "not empty");   // what does this print?

    printf("%d\n", q_length(q)); // what does this print?

    printf("%d\n", q_enqueue(q, (value_t){0})); // what does this print?

    // what does the q structure look like after that last call to enqueue?

What do the statements print, and what are the new values in the queue structure? (This is all about you making decisions, and understanding how these things are going to be used.)


[/code]

[Salem]

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.

[gajya]

Enqueue is
q->data[q->front++] = data;

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

I don't understand these two lines exactly what happens

#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; 
}

[Salem]

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.

[gajya]

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

#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; 
}