-2

I want to implement the queue ADT in C language.

I have the following:

// node structure:

typedef int ElementType;
typedef struct node {
    ElementType key;
    struct node* left_child;
    struct node* right_sib;
}* Node;
typedef Node Item;

// queue structure:

struct queue {
  Item* contents;
  int head;
  int tail;
  int dim;
};
typedef struct queue* Queue;


Queue initqueue();                  // create a queue
int queueEmpty(Queue q);            // queue empty?
void enqueue(Queue q, Item elem);   // insert item
int size(Queue q);                  // size of the queue?


Queue initqueue() {
    Queue q = (Queue)malloc(sizeof(struct queue));
    q -> contents = (Item*)malloc(sizeof(Item));
    q -> head = 0;
    q -> tail = 0;
    q -> dim = 1;
    return q;
}

int queueEmpty(Queue q) {
    return (q -> head == q -> tail);
}

void enqueue(Queue q, Item elem) {
    if (q -> head == (q -> tail % q -> dim) + 1 || q -> dim == 1)
        q -> contents = (Item*)realloc(q -> contents, (q -> dim) * 2);
    q -> contents[q -> tail] = elem;
    q -> tail = (q -> tail + 1) % (q -> dim);
}

int size(Queue q) {
    if (q -> tail < q -> head)
        return ((q -> dim) - (q -> head) + (q -> tail) - 1);
    else
        return (q -> tail - q -> head);
}


int main() {
    Queue q;
    Item i = (Item)malloc(sizeof(struct node));
    i -> key = 4;
    q = initqueue();
    enqueue(q, i);
    printf("%d\n", queueEmpty(q));
    printf("%d\n", size(q));

    return 0;
}

I don't understand why the output is 0 and 1, that is the queue is empty and its size is 0.

dbush
  • 205,898
  • 23
  • 218
  • 273
Pine Code
  • 2,466
  • 3
  • 18
  • 43
  • 1
    [Please see this discussion on why not to cast the return value of `malloc()` and family in `C`.](http://stackoverflow.com/q/605845/2173917). – Sourav Ghosh Jan 04 '17 at 14:56
  • 2
    SO isn't a debugging service. Compile with symbols, run the code inside a debugger to trace through the program(s) line by line inspecting the values of the relevant variables to learn what is really going on. If then a *specific* question arises feel free to come back here. – alk Jan 04 '17 at 15:01
  • 1
    Believe it or not, but a program *can* be made harder to follow by adding `typedef`s. The more names you have for something, the harder it is to keep track off its use. – StoryTeller - Unslander Monica Jan 04 '17 at 15:02
  • Please note that the dot `.` and arrow `->` operators bind very tightly and should not be surrounded by any spaces. – Jonathan Leffler Jan 04 '17 at 15:11
  • 2
    See also [Is it a good idea to `typedef` pointers?](http://stackoverflow.com/questions/750178/is-it-a-good-idea-to-typedef-pointers) — the short answer is "usually No". – Jonathan Leffler Jan 04 '17 at 15:12
  • You don't adjust `q->dim` when you `realloc()` more space. That may not be the whole problem, but it is one problem. Also, the idiom `old_ptr = realloc(old_ptr, new_size);` is an incipient memory leak. If the `realloc()` fails, you've just overwritten the pointer to the still allocated memory with NULL. Use: `new_ptr = realloc(old_ptr, new_size); if (new_ptr == 0) { …deal with out of memory error… }; old_ptr = new_ptr;`. – Jonathan Leffler Jan 04 '17 at 15:16

1 Answers1

0

You forgot to adjust q->dim, so q->tail is still zero (1 % 1) after the enqueue.

molbdnilo
  • 64,751
  • 3
  • 43
  • 82