c language implementation of queue

Sequential implementation of queues

typedef struct{
    int data[MaxSize];
    int front,rear;
} SqQueue;

For the initialization of the sequence queue, front points to the queue head element, and rear points to the next position of the queue tail element, that is, the next position that should be inserted.

void Init(SqQueue q){
    q.front=0;
    q.rear=0;
}

Judge whether the queue is empty

bool QueueEmpty(SqQueue q){
    if (q.rear==q.front) {
        return true;
    }else{
        return false;
    }
}

Insert operation of circular queue

Because it is rear==front to judge whether the queue is empty, the only way to judge whether the queue is full is if the rear is one less than the front, that is, only one storage unit can be sacrificed to judge whether it is full. The storage space is logically changed into a ring by modular operation

bool EnQueue(SqQueue *q,int x){
    if ((q->rear+1)%MaxSize==q->front) {
        return false;
    }
    q->data[q->rear]=x;
    q->rear=(q->rear+1)%MaxSize;
    return true;
}

Outgoing operation

bool DeQueue(SqQueue *q,int *x){
    if (q->front==q->rear) {
        return false;
    }
    *x=q->data[q->front];
    q->front=(q->front+1)%MaxSize;
    return true;
}

Number of queue elements:

(rear-front+MaxSize)%MaxSize

A method to judge that the queue is full without wasting storage space

1. Add a size member to the structure to represent the current length of the queue. Compare it with MaxSize to determine whether it is full

2. Set a variable tag in the structure. 0 is the latest deletion, 1 is the addition. When rear=front, 0 will only be empty when deleting, and 1 will only be full when adding.

Chain implementation of queue

typedef struct LinkNode{
    int data;
    struct LinkNode *next;
}LinkNode;

typedef struct{
    LinkNode *rear,*front;
} LinkQueue;

Initialize the queue (the head node). At the beginning, both front and rear point to the head node

void InitQueue(LinkQueue *q){
    q->front=q->rear=(LinkNode*)malloc(sizeof(LinkNode));
    q->front->next=NULL;
}

Judge whether the queue is empty

bool IsEmpty(LinkQueue q){
    if (q.rear==q.front) {
        return true;
    }else{
        return false;
    }
}

Initialize the queue (do not take the lead node)

Both front and rear point to NULL

To judge whether the queue is empty is to judge whether the front is NULL

Pay attention to the queue without the leading node. The rear refers to the location of the current queue tail, which is different from the leading node

New elements join the team (leading node)

void EnQueue(LinkQueue *q,int x){
    LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    q->rear->next=s;
    q->rear=s;
}

Join the team (do not lead the node)

void EnQueue(LinkQueue *q,int x){
    LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    if (q->front==NULL) {
        q->front=s;
        q->rear=s;
    }else{
        q->rear->next=s;
        q->rear=s;
    }
}

When the queue element is out of the stack, take the lead node. Note that if the last element is out of the queue, special processing should be carried out to point the rear to the front, because the rear is out of the queue.

p points to the node out of the queue this time

bool DeQueue(LinkQueue *q,int *x){
    if (q->rear==q->front) {
        return false;
    }
    LinkNode *p=q->front->next;
    *x=p->data;
    q->front->next=p->next;
    if (p==q->rear) {
        q->rear=q->front;
    }
    free(p);
    return true;
}

The queue element is out of the stack. It does not take the lead node. p points to the node out of the queue this time. When rear is equal to p, it means that the last node is out of the queue and needs to be returned to the empty queue status

bool DeQueue(LinkQueue *q,int *x){
    if (q->front==NULL) {
        return false;
    }
    LinkNode *p=q->front;
    q->front=p->next;
    if (q->rear==p) {
        q->front=NULL;
        q->rear=NULL;
    }
    free(p);
    return true;
}

Double ended queue

Tags: C Big Data Algorithm data structure

Posted by natbrazil on Fri, 01 Jul 2022 21:46:43 +0300