Using pointers for queue type

Question

I am very new to c and pointers. Each time I thin k I have understood it, there comes a problem that I don't really understand (I spent some time reading c docs but pointers still remain unclear to me) :

typedef struct {
        int q[QUEUESIZE+1];
        int first;
        int last;
        int count;
} queue;

enqueue(queue *q, int x)
{
  if (q->count >= QUEUESIZE)
        printf("Warning: queue overflow enqueue x=%d\n",x);

  else {
    q->last = (q->last+1) % QUEUESIZE;
    q->q[ q->last ] = x;
    q->count = q->count + 1;
  } 
}

I hope my question will not be too opaque but could someone explain the use of pointer in enqueue function? I thought the principle of queuing was to allocate some precise successive memory addresses, but it is not that for sure....

What's the problem? Do you get errors? What's not working? Please be precise, so you save us time about guessing :) — m0skit0
– m0skit0, Commented Feb 3, 2013 at 16:08
@m0skit0: Let me highlight it for you: could someone explain the use of pointer in enqueue function? — Alok Save
– Alok Save, Commented Feb 3, 2013 at 16:09
@AlokSave Explain what? How a pointer works? I don't understand what he wants to know exactly... — m0skit0
– m0skit0, Commented Feb 3, 2013 at 16:10
@m0skit0 The code is indeed working (used to traverse graphs), but I don't understand what could be the advantages for passing a pointer as a variable and not a simple variable (enqueue(queue q, int x)) ? — user1611830
– user1611830, Commented Feb 3, 2013 at 16:12
1) you don't need the last element, only first+count. 2) using unsigned types for sizes, counts, and indexes is preferable (you do not want a negative index or size) — wildplasser
– wildplasser, Commented Feb 3, 2013 at 16:21

Déjà vu · Accepted Answer · 2013-02-03 16:32:07Z

enqueue takes a queue queue (queue of type queue) and add an element in it (which is made of an integer.

queue *q is a pointer, since, probably

there could be more than one queue, and the parameter tells what queue we're talking about
in order to avoid a global variable, the queue is given as parameter - we want a reference to the queue so that it can be modified, and the modification will stay live even after exiting enqueue

Passing a queue by value, as

enqueue(queue q, int x) { ...

would mean

a lot of data given as parameter (copy of the queue myqueue to the q parameter)
when q is modified, the modification is made on q within the enqueue function. The initially provided queue (myqueue) as parameter would not be modified

For instance

enqueue(queue q, int x) { 
  q.count++; // only the local q.count is changed, not myqueue.count
  // ...
}

// ...

queue myqueue;
// ...
enqueue (myqueue, 3); // enqueue changes its local parameter, myqueue is not affected

Besides, the enqueue function implementation could be optimized... (see wildplasser answer below who suggests a better queue implementation)

wildplasser · Accepted Answer · 2013-02-03 20:57:02Z

struct queue {
        unsigned first;
        unsigned count;
        int q[QUEUESIZE];
        };

int enqueue(struct queue *q, int x)
{
  if (q->count >= QUEUESIZE) {
        fprintf(stderr, "Warning: queue overflow enqueue x=%d\n", x);
        return -1;
        }

  q->q[ (q->first+q->count++) % QUEUESIZE ] = x;
  return 0; /* success */ 
}

A few points:

diagnostic output should go to stderr
Using unsigned types for counts and offsets will (in most cases) avoid numerical underflow (or will transform it into overflow, which will fail faster ;-)
you don't need three elements {head, tail, count}, only two {head, count} will suffice
fewer variables := fewer assignments := fewer lines = less chance for error.
The QUEUESIZE in the range check and modulo division should probably be replaced by sizeof q->q / sizeof q->q[0], which is more robust.

Collectives™ on Stack Overflow

Using pointers for queue type

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related