Click here to Skip to main content
15,867,453 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Hi.. I'm pretty new to programming and trying to wrap my head around DS.

I was trying to implement Queue on my own before I check the original solution and wrote the following code (so the code might not be the best way to implement a queue).

C++
typedef struct queue {
    size_t size;
    size_t start;
    int end; // int is used as in newQueue() function I set end = -1
    int* array;
} queue_t;

size_t isFull(queue_t* q) {
    return q->end >= q->size - 1; // == works but >= doesn't
}

queue_t* newQueue(size_t size) {
    queue_t* q = (queue_t*)malloc(sizeof(queue_t));
    q->end = -1;
    q->start = 0;
    q->size = size;
    q->array = (int*)malloc(sizeof(int) * q->size);
    return q;
}


The above isFull() function returns wrong result i.e. FALSE which means that q->end (-1) is greater than q->size - 1 (5 - 1). I set size as 5

However, if I use

C++
typedef struct queue {
    int size;
    int start;
    int end; // int is used as in newQueue() function I set end = -1
    int* array;
} queue_t;


then everything seems to work fine. But I think if the size and start can't be zero then why to use int unnecessarily.

What I have tried:

I tried this small program to check what is going on with size_t and int and it gives wrong result too. I'm totally confused what is going on. Should we not compare int with size_t? That is what I'm inferring. But when I check online I found someanswers where it is mentioned that we can compare the size_t with int.

Should we not compare -ve int with size_t?

C++
#include <stdio.h>

int check(int n, size_t m) {
    return n >= m - 1;
}

int main(int argc, char const *argv[]) {
    int end = -1;
    size_t start = 5;
    printf("%d\n", check(end, start));
    return 0;
}
Posted
Updated 17-Mar-21 0:55am
v2

size_t is an unsigned datatype - it has no concept of negative numbers, so when you cast the integer value -1 to size_t what you get is a very large value because negative integers are stored with the top bit set: an eight bit value for -1 would be 11111111 in binary, and -2 would be 11111110 and so on. So when you subtract one from zero, it "overflows" to create a negative number:
Dec  Binary
 1   00000001
 0   00000000
-1   11111111

The best way to implement a queue to to have start and end initially both zero: if they are the same value then the queue is empty, if they aren't there are elements. Add an element, and you move start, remove one, you move end (which would better be called "inIndex" and "outIndex" to better reflect what you do with them - "start" and "end" are fixed indexes for the start and end of the actual buffer space, not the values in the buffer itself)
 
Share this answer
 
v2
Thanks for the explanation. After implementing the Queue myself I will surely check how the instructor has implemented it and where I have deviated.

Thanks mate.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900