Is it right to implement queue with single linked list?

Question

My Code ↓

Some macros defined by

#include <stdio.h>
#include <malloc.h>

#define  ElementType int

#define  ERROR 0


// 队列用单链表实现
struct Node {
    ElementType Data;
    struct Node *Next;
};

struct QNode {
    struct Node *rear;
    struct Node *front;
};
typedef struct QNode *Queue;

Add an element to the end of the queue

void AddQ(Queue PtrQ, ElementType item) {

    struct Node *rearCell;
    rearCell = (struct Node *) malloc(sizeof(struct Node));
    rearCell->Data = item;
    rearCell->Next = NULL;

    if (PtrQ->front == PtrQ->rear && PtrQ->rear == NULL) {
        PtrQ->front = PtrQ->rear = rearCell;
    } else {
        PtrQ->rear->Next = rearCell;
        PtrQ->rear = rearCell;
    }

}

Delete the element from the beginning of the queue and return the element value.

ElementType DeleteQ(Queue PtrQ) {
    struct Node *FrontCell;
    ElementType FrontElement;
    if (PtrQ->front == NULL) {
        printf("队列空");
        return ERROR;
    }
    FrontCell = PtrQ->front;
    if (PtrQ->front == PtrQ->rear)
        PtrQ->front = PtrQ->rear = NULL;
    else
        PtrQ->front = PtrQ->front->Next;
    FrontElement = FrontCell->Data;
    free(FrontCell);
    return FrontElement;
}

Initializing queues and calling

int main() {

    Queue PtrQ = (Queue) malloc(sizeof(struct QNode));
    PtrQ->front = NULL;
    PtrQ->rear = NULL;

    AddQ(PtrQ, 999);
    AddQ(PtrQ, 88);
    AddQ(PtrQ, 77);

    ElementType value = DeleteQ(PtrQ);

    printf("%d\n", value);

    ElementType value1 = DeleteQ(PtrQ);

    printf("%d\n", value1);

    ElementType value2 = DeleteQ(PtrQ);

    printf("%d\n", value2);

    return 0;
}

It worked out as I expected.

question if (ptrq-> front = = ptrq-> rear & & ptrq-> rear = = null)in AddQ. Is there a better judgment? and some other improvements

I'm learning to implement queues in C.

Answer 1

The function AddQ can be declared and defined the following way

int AddQ( Queue PtrQ, ElementType item ) 
{
    struct Node *rearCell = malloc( sizeof( struct Node ) );
    int success = rearCell != NULL;

    if ( success )
    {
        rearCell->Data = item;
        rearCell->Next = NULL;

        if ( PtrQ->front == NULL ) 
        {
            PtrQ->front = rearCell;
        }
        else
        {
            PtrQ->rear->Next = rearCell;
        }

        PtrQ->rear = rearCell;
    }

    return success;
}

The function name DeleteQ is confusing. The function does not delete the queue. Instead you should write three functions named for example PushQ, PopQ and TopQ.

And such a function should not issue any message. It is the caller of the function that will decide whether to issue a message.

Pay attention to that it is not a good idea to introduce a typedef for pointers like this

typedef struct QNode *Queue;

This makes the code unclear.

Also there is no any great sense to allocate an object of the type struct QNode dynamically

Queue PtrQ = (Queue) malloc(sizeof(struct QNode));

Instead you could write

struct QNode {
    struct Node *rear;
    struct Node *front;
};
typedef struct QNode Queue;

// ...

Queue queue = { .rear = NULL, .front = NULL };

In this case the function AddQ can be called like

int AddQ( Queue *PtrQ, ElementType item );

//...

AddQ( &queue, 999 );

or

if ( !AddQ( &queue, 999 ) ) puts( "Error: not enough memory!" );

And you need to write a function that will clear the queue.