Catalogue of series articles

preface

1, Concept and structure of queue

1. Concept of queue

Queue: a special linear table that only allows inserting data at one end and deleting data at the other end. The queue has a first in first out FIFO(First In First Out) into the queue: the end of the queue where the inserting operation is performed is called the end of the queue; the end of the queue where the deleting operation is performed is called the head of the queue.

2. Queue structure

2, Implementation of queue

The queue can also be implemented in the structure of array and linked list. It is better to use the structure of linked list, because if the structure of array is used, the efficiency will be relatively low.

1. Define the queue struct QueueNode represented by the linked list

The code is as follows:

typedef int QDataType;
struct QueueNode             //Queue structure, represented by linked list
{
	struct QueueNode* next;
	QDataType data;
};

2. Define the queue head and tail pointers struct Queue

The code is as follows:

struct Queue                //Queue head and tail pointer
{
	struct QueueNode* head;
	struct QueueNode* tail;
};

3. Queue initialization function QueueInit

The code is as follows:

void QueueInit(struct Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}

4. Queue destroy function

Traverse the queue and remember to store the address of the next node before free.
The code is as follows:

void QueueDestroy(struct Queue* pq)
{
	assert(pq);
	struct QueueNode* cur = pq->head;
	while (cur)
	{
		struct QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

5. Queue tail in data function QueuePush

First open up a node. In two cases, in one case, there is no node in the queue, which can be used as a node directly. In the second case, there are nodes in the queue at the beginning, and the data can be inserted at the end.
The code is as follows:

void QueuePush(struct Queue* pq, QDataType x)   //Tail in data
{
	assert(pq);
	struct QueueNode* newnode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
	if (newnode == NULL)
	{
		printf("Development failure!\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)   //No node
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

6. Queue header out data function QueuePop

The code is as follows:

void QueuePop(struct Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->head->next==NULL)  //Only one node
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		struct QueueNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

7. Queue header data function QueueFront

Remember to judge whether the queue is empty before fetching data each time. If not, proceed to the next step.
The code is as follows:

QDataType QueueFront(struct Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

8. Get the end of queue data function QueueBack

Remember to judge whether the queue is empty before fetching data each time. If not, proceed to the next step.
The code is as follows:

QDataType QueueBack(struct Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

9. Whether the queue is empty function QueueEmpty

The code is as follows:

bool QueueEmpty(struct Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

10. Queue length function QueueSize

The code is as follows:

int QueueSize(struct Queue* pq)
{
	int size = 0;
	assert(pq);  
    struct QueueNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

summary

The above is what we want to talk about today. This paper only briefly introduces the use of queue, and provides some simple methods for queue to help us solve problems, and functions and methods that enable us to process data quickly and conveniently. In addition, although this structure is simpler than the linked list and easier to write with code, we should also study it carefully. In the future, we will find that the queue structure will bring many advantages, which we must master. In addition, if there is a private letter that needs the source code, I can. Also, if there are any problems above, please understand my brother's advice, but it doesn't matter. It's mainly because I can insist. I hope some students who study together can help me correct them. But if you can be gentle, please tell me that love and peace are the eternal theme and love you all.