Implementation of queue

Catalog

1. The concept and structure of queue

2. Implementation of queues

  Initialize queue

Tail in queue

// Team leader out of line

// Get queue header elements

// Get queue tail element

// Get the number of valid elements in the queue

// Destroy queue

---

1. The concept and structure of queue

queue ： Data insertion is only allowed at one end , A special linear table that deletes data at the other end , Queue has first in first out
FIFO(First In First Out) Queue entry ： The end of the insertion is called the end of the queue

                                         Outgoing queue ： The end of the delete operation is called the queue head

2. Implementation of queues

Queues can also be implemented in the structure of arrays and linked lists , It is better to use the structure of linked list , Because if you use the structure of an array , Out of the queue, out of the data on the array header , It will be less efficient .

typedef int QDataType;
//  The chain structure ： Represents a queue 
typedef struct QListNode
{
    struct QListNode* _pNext;
    QDataType _data;
}QNode;
//  The structure of the queue 
typedef struct Queue
{
    QNode* _front;
    QNode* _rear;
}Queue;
//  Initialize queue 
void QueueInit(Queue* q);
//  Tail in queue 
void QueuePush(Queue* q, QDataType data);
//  Team leader out of line 
void QueuePop(Queue* q);
//  Get queue header elements 
QDataType QueueFront(Queue* q);
//  Get queue tail element 
QDataType QueueBack(Queue* q);
//  Get the number of valid elements in the queue 
int QueueSize(Queue* q);
//  Check if the queue is empty , If NULL, return non-zero result , If not null, return 0
int QueueEmpty(Queue* q);
//  Destroy queue 
void QueueDestroy(Queue* q);

  Initialize queue

 void QueueInit(Queue* q);// No matter what structure , We all need to initialize first .

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

}

Tail in queue

void QueuePush(Queue*  q, QDataType data);// Because the queue is FIFO , So it can only be inserted from the tail

void QueuePush(Queue* pq, QDataType x)// Insert , Insert... At the end of the line ; fifo 
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));// Every time you insert a data, you open up a space 
	if (newnode == NULL)// Judge whether the development fails 
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)// When no data is inserted for the first time 
	{
		pq->head = pq->tail = newnode; 
	}
	else// With data 
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

// Team leader out of line

void QueuePop(Queue* q);// Outgoing queue , The first one is the data of the team leader , Make sure it's first in, first out .

void QueuePop(Queue* pq)// It is equivalent to deleting the team header data 
{
	assert(pq);
	assert(!QueueEmpty(pq));// Determines if the queue is empty 
	// A node 
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	// Multiple nodes 
	else
	{
		Queue* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

// Get queue header elements

QDataType QueueFront(Queue* q);// First judge the capacity of the queue , Then return to the team head element

QDataType QueueFront(Queue* pq)// Get the correct header data 
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

// Get queue tail element

QDataType QueueBack(Queue* q);// First judge the queue capacity , Then return the tail data

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

// Get the number of valid elements in the queue

int QueueSize(Queue* q);// Create a current pointer , Go back one by one ,size Count the quantity for size .

int QueueSize(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;// Create a pointer to the current element 
	int size = 0;// Used to count the number of elements 
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}

// Check if the queue is empty , If NULL, return non-zero result , If not null, return 0

int QueueEmpty(Queue* q);// here return It's to judge first pq->head Is it equal to empty , Return to true later , Return false before waiting .

bool QueueEmpty(Queue* pq)// Judge capacity ;
{
	assert(pq);
	return pq->head == NULL;

}

// Destroy queue

void QueueDestroy(Queue* q); Because we have opened up space , So we have to release one by one in the end .

void Queuestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)// Release space one by one 
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

Expand ：

In practice, we sometimes use a queue called circular queue . For example, when the operating system course explains the producer consumer model, you can use the circular queue . Ring queues can be implemented using arrays , You can also use a circular linked list to achieve .