Redefining queue with different front and rear

Question

#include <stdio.h>
#include <limits.h>

#define MAX_SIZE 5
#define FULL INT_MAX
#define EMPTY INT_MIN

int Q[MAX_SIZE]; // linear queue //
int rear = -1;
int front = 0;


 // condition for empty is Qsize is zero (front > rear)                 //
// condition for full is rear is at last index (rear == MAX_SIZE - 1)  //


// basic operations on Queue // 

int add_Q(int item);     // if full returns (INT_MAX) else  returns item inserted          // 
int delete_item_in_Q(); // if empty returns (INT_MIN) else returns deleted item           // 
size_t Qsize();        // returns 0 if (front > rear) else returns the current size of Q //

// read operations   //

int rear_data();   // if empty returns (INT_MIN) else returns rear data              //
int front_data(); //  if empty returns (INT_MIN) else returns front data            //
void read_Q();

void delete_Q();  
void get_Q(size_t size);



int main(void){
    int size;

    printf("\nenter your size(positive) for Queue (less than %d) : ",MAX_SIZE);
    scanf("%d",&size);

    get_Q(size);
    read_Q();

    add_Q(66);
    read_Q();

    delete_item_in_Q();
    read_Q();

    delete_Q();
    read_Q(); 

return 0;

}

void get_Q(size_t size){
    int item;
    if(size > MAX_SIZE){
        printf("enter valid size \n");
        return;
    }

    for(int i = 0 ; i < size ; i ++){
        printf("enter your queue elements : ");
        scanf("%d",&item);
        add_Q(item);
    }
}

int add_Q(int item){
    return rear == (MAX_SIZE - 1) ? FULL : (Q[++rear] = item); 
}

int delete_item_in_Q(){
    return Qsize() ? Q[front++]:EMPTY; 
}

size_t Qsize(){
    if(front > rear){
        front = 0;rear = -1;
    }
return (rear - front + 1);
}

int front_data(){
    return Qsize() ? Q[front]:EMPTY;
}
int rear_data(){
    return Qsize() ? Q[rear]:EMPTY;
}
void read_Q(){

    if(!Qsize()){
        printf("\nthe queue is empty\n");
        return;
    }

    int i = front;
    printf("\nthe queue is : ");

    while(1){
        printf("%d=>",Q[i++]);

        if(i == MAX_SIZE){
            printf("\nqueue is full\n");
            return;
        }
        else if (i > rear){
            putchar('\n');
            return;
        }
    }

}

void delete_Q(){

    while(1){
        if(!Qsize()){
            printf("\nthe queue is empty\n");
            return;
        }
        printf("the deleted element is : %d\n",Q[front++]);

       }
}

In my queue(linear) rear = -1 and front = 0 unlike(front = rear = -1) and assumes user doesn't enter INT_MIN or INT_MAX. I am not checking the return values of many functons like scanf(),add_Q() for simplicity.

rear and front points to valid data if (front <= rear) empty if (front > rear). Qsize() always reinitialize the index back to original in empty state

In order to access queue the above conditions must be "strictly" met or else we say it is empty,

so is this queue a valid one ? my teacher said that it is not a good one (rear or front is pointing at locations inside the array in empty conditions).

Is there any problem in my code ? I have tried to look for errors but none was found (based on my definition).

and I need a better solution that doesn't assume user never enter INT_MIN or INT_MAX (but it should return the added or deleted data).

read_Q() also looks bad. I need a better one for it.

Answer 1

Your teacher is right. This is not a good FIFO.

Is there any problem in my code ?

We're not ready to go there, yet. Let's first worry about problems with the design. We want to implement a queue that others would want to use, and currently this doesn't fit the bill.

---

production use, 24x7

It is perfectly valid for a consumer to do this all day long:

    add_Q(get_val());

    while (TRUE) {
        add_Q(get_val());
        add_Q(get_val());

        process(delete_item_in_Q(),
                delete_item_in_Q());
    }

That is, the queue receives an unbounded stream of values, and queue depth is bounded, it always hovers between 1 .. 3 inclusive. It never becomes EMPTY. And that's ok. It definitely never becomes FULL, though in your implementation it would.

---

circular reasoning

How can we accommodate such a usage pattern?

Malloc / free of Linked List nodes is certainly one way. I'm glad you didn't go that route.

Another way is to use a fixed size array as you have, but allow it to begin at any element, wherever rear points to. As elements are added, we wrap around using modulo MAX_SIZE.

Let front always be the index of a free element, and rear (potentially) points at the oldest valid element.

When front == rear, the queue is empty, there is no valid element.

When (front + 1) % MAX_SIZE == rear then we have wrapped all the way around, and the queue is full. It will not accept any new elements. Notice that we "waste" one cell in that instance, since front == rear is reserved for the empty case rather than the full case. Define the constant to be "one more" if needed by your requirements.

---

code style

If an_identifier starts with lower case, good, stick with that, avoid tacking on a capital letter.

Prefer ternary a ? b : c for read-only expressions. Clearly you can do a ? readonly : sideeffect as in the OP, and it will work. But that doesn't mean it is easily readable by others. Prefer if (a) { b } else { c } for side effects, even in the case that if (a) { return b } else { return c } needs a pair of return statements.

Find a code formatter / pretty-printer, and use it. Doesn't matter if it's GNU, Google, K&R, or another style, as long as it's consistent throughout the code.

Find a C unit test framework and use it. Automated tests "know the answer", to give Red / Green bar results upon running. They don't require the user to eyeball what was printed and decide whether that was the right result.

Answer 2

I agree with J_H that this needs to be redesigned, but there are a few basic issues in the code. It is never a good idea for a number that can be an index into an array to ever go negative, this can lead to out of bounds which can be very difficult to debug. C does not provide runtime checking on array bounds. The rear and front variables should both probably be size_t although they could alternatively be pointers.

It should also be noted that scanf() returns a value that is being ignored. This may lead to possible errors.

Avoid Global Variables

It is very difficult to read, write, debug and maintain programs that use global variables. Global variables can be modified by any function within the program and therefore require each function to be examined before making changes in the code. In C and C++ global variables impact the namespace and they can cause linking errors if they are defined in multiple files. The answers in this Stack Overflow question provide a fuller explanation.

In this program the scope of all the variables and functions can be limited by making all functions and variables static functions or variables except for the main() function which must be a global entry point.

Code Organization

Function prototypes are very useful in large programs that contain multiple source files, and that in case they will be in header files. In a single file program like this it is better to put the main() function at the bottom of the file and all the functions that get used in the proper order above main(). Keep in mind that every line of code written is another line of code where a bug can crawl into the code. The function Qsize() should probably be declared first since it is used in multiple functions; the function add_Q() should be declared second.

static int rear = -1;
static int front = 0;


static size_t Qsize() {
    if (front > rear) {
        front = 0; rear = -1;
    }
    return (rear - front + 1);
}

static int add_Q(int item) {
    return rear == (MAX_SIZE - 1) ? FULL : (Q[++rear] = item);
}

static void get_Q(size_t size) {
    int item;
    if (size > MAX_SIZE) {
        printf("enter valid size \n");
        return;
    }

    for (int i = 0; i < size; i++) {
        printf("enter your queue elements : ");
        scanf("%d", &item);
        add_Q(item);
    }
}




 

Answer 3

Much already reviewed. Some additional thoughts:

Design flaw

return Qsize() ? Q[front++] : EMPTY; is bad as when code returns EMPTY, the caller does not know if that is due to an error or a valid value from the queue.

Note: add_Q(EMPTY) does not generate an error.

A better design would covey 2 pieces of information for a get() like function: the int value and the error code/flag.

Example:

// Return location_to_store_value on success
// Return NULL on error 
int *Q_get_front(int *location_to_store_value);

Enable all compiler warnings

Why should I always enable compiler warnings?

I found at least 3.

Improve presentation

Auto-format the code.

Use (void) for function declarations

Functions like int rear_data(); do not provide info about what arguments my be passed. (Perhaps this will change in C23)

No error/waring is generated with read_Q(5);.

Instead declare with

//int rear_data();
//int front_data();
//void read_Q();
int rear_data(void);
int front_data(void);
void read_Q(void);

Error messages

Consider moving error message to stderr. It is usually poor design for a function to exceptionally print to stdout.

// printf("\nthe queue is empty\n");
fprintf(stderr, "\nThe queue is empty.\n");

Error return value

if full returns (INT_MAX) else returns item inserted --> INT_MAX is a potentially valid return value with #define MAX_SIZE INT_MAX. Consider either returning an invalid index like INT_MIN, -1 or better: redesign and return and error code form add_Q(). 0 is success, any other vlaue is some error.

Organize namespace

Rather than use names from all over, consider an interesting common prefix.

// int delete_item_in_Q();
// size_t Qsize();
// int rear_data(); 
int SKQ_delete_item();
int SKQ_rear_data(); 
size_t SKQ_size();
...

Minor: Use sentence case

Improve output.

// printf("enter valid size \n");
printf("Enter valid size: \n");
//      ^               ^