Introduction and implementation of queue (detailed explanation)

One 、 What is a queue

queue （queue） It is only allowed to insert at one end , A linear table with deletion at the other end

Two 、 The structure of the queue

A queue is a first in, first out （First In First Out） The linear table , abbreviation FIFO.

Team head ： The end allowed to be deleted is called the team leader
A party ： The end allowed to be inserted is called the end of the queue

Suppose the queue is q=(A1,A2,A3·····An), that A1 For the team leader element ,An End of team element . We deleted it from A1 Start , Insert from An Start .

Pictured ：

3、 ... and 、 Implementation of queues

I implemented it in a chain storage structure , You can also use a linear storage structure .

First create the queue structure

head： When creating nodes , We need to head The pointer points to the head of the team
tail： need head The pointer points to the end of the queue

next： Pointer to the domain , Used to connect nodes
data： data

typedef int QDataType;

struct queue
{
    
	struct QListNode*head;
	struct QListNode*tail;
	
};

struct QListNode
{
    
	struct QlistNode*next;
	QDataType data;
};

1. Initialize queue operation

First initialize the queue .

void InitQueue(struct queue*qst)
{
    
	qst->head = NULL;
	qst->tail = NULL;

}

2. Queue exists , Then destroy the queue

First of all, make an assertion qst
When destroying the queue, we must release the dynamically opened space , Avoid memory leaks .

void DestroyQueue(struct queue*qst)
{
    
	assert(qst);
	struct QListNode*cur = qst->head;
	
	while (cur)
	{
    
		struct QListNode*next = cur->next;
		free(cur);
		cur = next;
	}
	qst->head = NULL;
	qst->tail = NULL;
}

3. The queue to empty

Without releasing space , Put... Directly tail Point to the team leader .

void ClearQueue(struct queue*qst)
{
    
	assert(qst);
	assert(!EmptyQueue(qst));		
	qst->tail = qst->head;
}

4. Determines if the queue is empty

Determine whether there are nodes .

QDataType EmptyQueue(struct queue*qst)
{
    
	assert(qst);
	return qst->head == NULL;
}

5. Returns the queue header element

QDataType GetHead(struct queue*qst)
{
    
	assert(qst);
	assert(!EmptyQueue(qst));// Asserts whether the queue is empty 
	return qst->head->data;// Returns the header element 

}

6. Returns the number of queue elements

Count the number of elements by counting

QDataType SizeQueue(struct queue*qst)// The number of elements in the queue 
{
    
	assert(qst);
	assert(!EmptyQueue(qst));
	int count = 0;
	struct QListNode*cur = qst->head;
	while (cur)
	{
    
		count++;
		cur = cur->next;

	}
	return count;

}

7. Insert

Let's say first , Then judge whether there is a node , And connect them .
Open up space next To be empty

void PuchQueue(struct queue*qst, QDataType x)
{
    
	assert(qst);
	struct QListNode*newhead =(struct QListNode*) malloc(sizeof(struct QListNode));
	if (newhead == NULL)
	{
    
		printf("malloc fail");
		exit(-1);
	}
	newhead->next = NULL;
	newhead->data = x;
	if (qst->head == NULL)// There was no node in the queue 
	{
    
		qst->head = qst->tail = newhead;// The head and tail of the team point directly to the new node 
	}
	else
	{
    

		struct QListNode*cur = qst->head;
		cur->next = newhead;// Connecting nodes 
		qst->tail = newhead;// The end of the queue points to the new node , Change the tail of the team 
	}

}

8. Delete

Delete an element , Namely free Drop this node , The head of the queue will also change .

void PopQueue(struct queue*qst)
{
    
	assert(qst);
	assert(!EmptyQueue(qst));
	if (qst->head->next == NULL)// The queue has only one node 
	{
    
		free(qst->head);
		qst->head = NULL;
		qst->tail = NULL;
	}
	else// The queue has multiple nodes 
	{
    
		struct QListNode*cur = qst->head;
		cur = cur->next;

		free(qst->head);
		qst->head = cur;
	}

}