queue

First of all, what is a queue

Queue is a kind of special linear table. The special thing is that it only allows deletion at the front end of the table and insertion at the rear end of the table. Like stack, queue is a kind of linear table with limited operation. The end of the insertion operation is called the end of the queue, and the end of the deletion operation is called the head of the queue. When there are no elements in the queue, it is called an empty queue.
The data elements of a queue are also called queue elements. Inserting a queue element into a queue is called queuing, and deleting a queue element from a queue is called queuing. Because queues can only be inserted at one end and deleted at the other end, only the elements that enter the queue first can be deleted from the queue first. Therefore, queues are also called FIFO first in first out linear tables.

The sequence queue and chain queue are respectively realized as follows:

1. Sequence queue

.h file

#pragma once
#include<stddef.h>

typedef char SeqQueueType;

#define SeqQueueMaxSize 1000

typedef struct SeqQueue
{
    SeqQueueType data[SeqQueueMaxSize];
    size_t head;
    size_t tail;
    size_t size;
}SeqQueue;
void SeqQueueInit(SeqQueue* q);//Initialization
void SeqQueueDestroy(SeqQueue* q);//Destruction queue
void SeqQueuePush(SeqQueue* q,SeqQueueType value);//Queue entry
void SeqQueuePop(SeqQueue* q);//Outgoing queue
int SeqQueueFront(SeqQueue* q,SeqQueueType* value);//Team leader element

.c file

void SeqQueueInit(SeqQueue* q)
{
    if(q == NULL)
    {
        //illegal input
        return;
    }
    q->size = 0;
    q->head = 0;
    q->tail = 0;
    return;
}
void SeqQueueDestroy(SeqQueue* q)
{
    if(q == NULL)
    {
        //illegal input
        return;
    }
    q->size = 0;
    q->head = 0;
    q->tail = 0;
    return;
}
void SeqQueuePush(SeqQueue* q,SeqQueueType value)
{
    if(q == NULL)
    {
        //illegal input
        return;
    }
    if(q->size > SeqQueueMaxSize)//If the size of the queue is larger than the maximum size of the queue, the queue is full
    {
        //The queue is full
        return;
    }
    q->data[q->tail++] = value;//Assign value to the last element of the array and index the array element + 1
    if(q->tail > SeqQueueMaxSize)//If the subscript of the tail element has exceeded the maximum capacity, the next element will be queued from subscript 0
    {
        q->tail = 0;
    }
    ++q->size;//Queue size+1
    return;
}
void SeqQueuePop(SeqQueue* q)
{
    if(q == NULL)
    {
        //illegal input
        return;
    }
    if(q->size == 0)
    {
        //Empty queue cannot be queued
        return;
    }
    ++q->head;//Add the subscript of the header element + 1
    if(q->head >= SeqQueueMaxSize)//If the subscript of the header element has exceeded the maximum capacity, the next element will be queued from subscript 0
    {
        q->head = 0;
    }
    --q->size;//Queue size-1
    return;
}
int SeqQueueFront(SeqQueue* q,SeqQueueType* value)
{
    if(q == NULL || value == NULL)
    {
        //illegal input
        return 0;
    }
    if(q->size == 0)
    {
        return 0;
    }
    *value = q->data[q->head];//Assign the value of the queue header element to value
    return 1;
}

Here is the test code:

#if 1
#include<stdio.h>
#define TEST_HEADER printf("\n==========================%s===========================\n",__FUNCTION__);
void TestSeqQueue()
{
    TEST_HEADER;
    SeqQueue queue;
    SeqQueueInit(&queue);
    SeqQueuePush(&queue,'a');
    SeqQueuePush(&queue,'b');
    SeqQueuePush(&queue,'c');
    SeqQueuePush(&queue,'d');

    SeqQueueType value;
    int ret = SeqQueueFront(&queue,&value);
    printf("ret expected 1,actual %d\n",ret);
    printf("value expected a,actual %c\n",value);
    SeqQueuePop(&queue);
    ret = SeqQueueFront(&queue,&value);
    printf("ret expected 1,actual %d\n",ret);
    printf("value expected b,actual %c\n",value);
    SeqQueuePop(&queue);
    ret = SeqQueueFront(&queue,&value);
    printf("ret expected 1,actual %d\n",ret);
    printf("value expected c,actual %c\n",value);
    SeqQueuePop(&queue);
    ret = SeqQueueFront(&queue,&value);
    printf("ret expected 1,actual %d\n",ret);
    printf("value expected d,actual %c\n",value);
}
int main()
{
    TestSeqQueue();
    return 0;
}
#endif

2. Chain queue

.h file

#pragma once

typedef char LinkType;

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

typedef struct LinkQueue
{
    LinkNode* head;
    LinkNode* tail;
}LinkQueue;
void LinkQueueInit(LinkQueue* q);//Initialization of queues
void LinkQueueDestroy(LinkQueue* q);//Destruction queue
void LinkQueuePush(LinkQueue* q,LinkType value);//Queue entry
void LinkQueuePop(LinkQueue* q);//Outgoing queue
int LinkQueueFront(LinkQueue* q,LinkType* value);//Team leader element

.c file

void LinkQueueInit(LinkQueue* q)
{
    if(q == NULL)
    {
        //illegal input
        return;
    }
    q->head = NULL;//Set head pointer to null
    q->tail = NULL;//Set to null pointer
    return;
}
void LinkQueueDestroy(LinkQueue* q)//Destruction queue
{
    if(q == NULL)
    {
        //illegal input
        return;
    }
    free(q->head);
    free(q->tail);
    q->head = q->tail = NULL;
    return;
}
void DestroyLinkNode(LinkNode* to_delete)
{
    if(to_delete == NULL)
    {
        return;
    }
    free(to_delete);//Release node
    to_delete = NULL;
    return;
}
LinkNode* CreateLinkNode(LinkType value)
{
    LinkNode* tmp = (LinkNode*)malloc(sizeof(LinkNode));
    if(!tmp)//Failed to create node
    {
        printf("CreateLinkNode error!\n");
        return NULL;
    }
    tmp->data = value;
    tmp->next = NULL;
    return tmp;
}
void LinkQueuePush(LinkQueue* q,LinkType value)
{
    if(q == NULL)
    {
        //illegal input
        return;
    }
    LinkNode* temp = CreateLinkNode(value);//Create a new node temp
    if(q->head == NULL)//If there are no elements in the queue
    {
        q->head  = temp;
        q->tail = temp;
        return;
    }
    //If there are elements in the queue
    q->tail->next = temp;//Insert a node at the end of the original queue
    q->tail = temp;//Move the tail pointer back
    return;
}
void LinkQueuePop(LinkQueue* q)
{
    if(q == NULL)
    {
        //illegal input
        return;
    }
    LinkNode* to_delete = q->head;//To "delete" points to the team head node
    q->head = q->head->next;//Update header pointer
    DestroyLinkNode(to_delete);//Destroy header node
    return;
}
int LinkQueueFront(LinkQueue* q,LinkType* value)
{
    if(q == NULL )
    {
        //illegal input
        return 0;
    }
    *value = q->head->data;//Assign the value of team leader element to value
    return 1;
}

Here is the test code:

#if 1
#define TEST_HEADER printf("\n======================%s========================\n",__FUNCTION__);
void LinkQueuePrintChar(LinkQueue* q,const char* msg)
{
    printf("[%s]\n",msg);
    LinkNode* cur = q->head;
    for(;cur!= NULL;cur=cur->next)
    {
        printf("[%c][%p]<- ",cur->data,cur);
    }
    printf("NULL\n");
    printf("\n");

}
void TestQueue()
{
    TEST_HEADER;
    LinkQueue queue;
    LinkQueueInit(&queue);
    LinkQueuePush(&queue,'a');
    LinkQueuePush(&queue,'b');
    LinkQueuePush(&queue,'c');
    LinkQueuePush(&queue,'d');
    LinkQueuePrintChar(&queue,"Print queue");

    LinkType value;
    int ret = LinkQueueFront(&queue,&value);
    printf("ret expected 1,actual %d\n",ret);
    printf("value expected a,actual %c\n",value);

    LinkQueuePop(&queue);
    ret = LinkQueueFront(&queue,&value);
    printf("ret expected 1,actual %d\n",ret);
    printf("value expected b,actual %c\n",value);

    LinkQueuePop(&queue);
    ret = LinkQueueFront(&queue,&value);
    printf("ret expected 1,actual %d\n",ret);
    printf("value expected c,actual %c\n",value);

    LinkQueuePop(&queue);
    ret = LinkQueueFront(&queue,&value);
    printf("ret expected 1,actual %d\n",ret);
    printf("value expected d,actual %c\n",value);

    LinkQueue queue1;
    LinkQueueInit(&queue1);
    LinkQueuePush(&queue1,'a');
    LinkQueuePush(&queue1,'b');
    LinkQueuePush(&queue1,'c');
    LinkQueuePush(&queue1,'d');
    LinkQueuePrintChar(&queue1,"Print queue");

    LinkQueueDestroy(&queue1);
    LinkQueuePrintChar(&queue1,"Print queue");
}
int main()
{
    TestQueue();
    return 0;
}
#endif