FIFO queue implementation in C

[blob84]

Hello i implemented this FIFO queue:

#include <stdio.h>
 void enqueue(int *, int);
int dequeue(int *);
int qempty(void);
int head = 0;
int tail = 0;
int qerror(void);
#define N 4

int main(void)
{
    int i = 0;
    int v[N];

    while (i < 10) {
        enqueue(v, i);
        i++;
    }
    while (!qempty())
        printf("%d\n", dequeue(v));
}
void enqueue(int *q, int x)
{   //printf("head=%d\ttail=%d\n", head, tail+1);
    q[tail] = x;
    if (tail == N)      
        tail = 0;
    else
        tail++;
    printf("tail=%d\n", tail);
    //if (head == tail) 
        //fprintf(stderr, "full\n");
}
int dequeue(int *q)
{
    int x;
    //if (head == tail)
        //fprintf(stderr, "empty\n");
    x = q[head];
    if (head == N) 
        head = 0;
    else
        head++;
    return x;
}
int qempty(void)
{
    return head == tail;
}
int qerror(void)
{   printf("head%d=\ttail=%d\n", head, tail);
    if (head == tail+1)
        fprintf(stderr, "coda piena\n");
}

I'm trying to write a function qerror() that return a value if the queue is full or if the queue is empty and I use respectively enqueue and dequeue functions.
This is the implementation of the queue in the Cormen book.
I appreciate any suggestion, thanks.

[prakash4]

try like this

If(head==N-1)
{
  printf("queue is full");
  }
  if(head==-1)
  {
  printf("queue is empty");
  }

and try to give the queue values dynamically....if u r giving statically means you willl nt get a chance for testing the error....

[Nutster]

This is a rotating queue, so do not compare your head and tail to fixed points around the array to determine if it is full or not. You have to compare the head and tail positions to determine if the queue is full or empty or whatever.

You should probably check your conditions at the beginning of the enqueue and dequeue functions. Make sure you have a clear definition of what values your head and tail represent. Is the tail where you are next going to store a value or is the place you last stored a value and the next value to be stored goes in the next element? Similarily with the head.

You are using a pair of global variables to keep track of the head and tail of the queue in an array local to main(). A better practice would be to keep all those variables at the same level, preferably local, with a consistant mechanism for passing the variables. That way, if you wanted to use more than one queue at a time, the global variables would not get scrambled from one queue to the next. In the following code, I am using the first 2 elements of the array to store the head and tail; this way when you are passing your array, you are also passing the head and tail without needing to pass other variables at the same time.

You have a qempty() function. What about creating a qfull() function and then have qerror() just check each of those functions?

#include <stdio.h>

#define N 8

void enqueue(int *, int);
int dequeue(int *);
int qempty(const int *);
int qfull(const int *)
int qerror(const int *);

int main(void)
{
    int i = 0;
    int v[N];

    v[0] = 2; /* head */
    v[1] = 2; /* tail */
    while (i < 10) {
        enqueue(v, i);
        i++;
    }
    while (!qempty(v))
        printf("%d\n", dequeue(v));
}

int enqueue(int *q, const int x)
{
    int *tail = q + 1;  /* element 1 of the array */

    // printf("head=%d\ttail=%d\n", q[0], q[1]);
    if (qfull(q))
        return 0;   /* failure - the queue is full. */
    if (++(*tail) == N)
        *tail = 2;  /* back to the beginning of the array, skipping the head and tail values. */
    q[*tail] = x;
    // printf("tail=%d\n", *tail);
}

int dequeue(int *q)
{
    int x;
    int *head = q;

    // if (head == tail) fprintf(stderr, "empty\n");
    if (qempty())
        return 0;   /* should have already been checked, but just for safety. */
    x = q[(*head)++];
    if (*head == N)
        *head = 2;
    return x;
}

int qempty(const int *q)
{
    return q[0] == q[1];
}

int qfull(const int *q)
{
    if (q[0] == 2 && q[1] == N-1)   /* if head at the beginning and tail at the end? */
        return 1;
    else
        /* Is the tail just before the head? */
        return (q[0] == q[1] + 1);
}

int qerror(const int *q)
{
    return qempty() || qfull();
}

[rubberman]

A stack structure can work well for a FIFO queue. You push an element on the queue, and pull one off of it. The push makes that element the last in, and the pull gets the first in. A linked list is also good for this - push attaches the element to the top of the list, and a pull removes the bottom of the list. In this case, you want to keep pointers to both the head and tail of the list. In many cases, a linked list is more efficient than an array (as which stacks are often implemented). With a linked list you also don't have to resize an array, which adds non-deterministic overhead (important if you need real-time behavior).

[Nutster]

Actually, a traditional stack structure implements a LIFO structure: The last in is the first one out. Yes, linked lists are often used with FIFO queues for the reasons given, but the OP is asking about his non-dynamic array implementation.

Another thought. If you are going to define global variables, it is is easier to read if you do not mix them into the middle of your function prototypes.