I implement queue with C I

Catalog

One 、 Nature of queues ：

Two 、 The structure of the queue ：

3、 ... and 、 Code implementation

The header file ：

Function function ：

---

One 、 Nature of queues ：

        Last time we learned stack , Understand that the way the stack stores and releases data is ： First in, then out

        The queue is the opposite , The queue is ： fifo , last in last out .

Two 、 The structure of the queue ：

        Multiple linked list nodes +  Head to tail pointer    （ Linked list queue ）

        List nodes Responsible for storing data ; Head node Responsible for locating advanced starting data , Convenient first out ;

        Tail node Be responsible for recording tail data , It is convenient to determine the current status of the queue .

       

3、 ... and 、 Code implementation

The header file ：

It is convenient to call uniformly , Define the head and tail pointers as a structure . 

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int Quetype;          // Define the data type of the queue 

typedef struct QueNode        // Define data nodes 
{
	struct QueNode* Next;
	Quetype data;
}QueNode;

typedef struct Quetail        
{                         
	struct QueNode* head;     // Define the head and tail pointer 
	struct QueNode* tail;
}Quetail;

void Que_Init(Quetail* pq);                // Initialization of the queue 
void Que_Destory(Quetail* pq);             // Destruction of queues 
void Que_push(Quetail* pq ,Quetype data);  // insert data 
void Que_pop(Quetail* pq);                 // Delete data 
bool Que_Empty(Quetail* pq);               // Determines if the queue is empty 
int Que_size(Quetail* pq);                 // Count the queue length 
int Que_front(Quetail* pq);                // Find the header data of the queue 

Function function ：

1. Initialization of the queue ：

Set the head and tail pointer to NULL Convenient for subsequent use .

void Que_Init(Quetail* pq)           // Initialization of the queue 
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

2. insert data ：

Create a linked list node >> Import data >> The header pointer points to the header node >> The tail pointer points to the tail node  

// insert data 
void Que_push(Quetail* pq,Quetype data)
{ 
	assert(pq);
	QueNode* NewNode = (QueNode*)malloc(sizeof(QueNode));// Create nodes 
	if (NewNode == NULL)
	{
		printf("Que_push->malloc");
		exit(-1);
	}
	NewNode->Next = NULL;          
	NewNode->data = data;
	if (pq->head == NULL)         // Determine whether to create a header node 
	{
		pq->head = NewNode;       // Update head pointer 
	}
	else
	{
		pq->tail->Next = NewNode; // Not a header node , It is normally linked after the tail node 
	}
	pq->tail = NewNode;           // Update tail pointer 
}

3. Delete data ：

  Record the next position of the header node >> Judge whether it is the last data >> Update head pointer

  Minutiae ： If there are more nodes left in the queue , After deleting the head node , The tail pointer always points to the tail node , No need to change ;

                But if there is only one data node left , After deletion, you need to set the tail pointer to null .

 

// Delete data 
void Que_pop(Quetail* pq)
{
	assert(pq);                       
	assert(!Que_Empty(pq));         // Determines if the queue is empty 
	QueNode* Next = pq->head->Next; // Record deleted data 

	if (pq->head == pq->tail)       // Determine whether it is the last data 
	{
		free(pq->head);
		pq->tail = NULL;            // Update tail pointer 
	}
	else
	{
		free(pq->head);             
	}
	pq->head = Next;                // Update head pointer 
}

4. Determine whether the list is empty ：

use bool As return type

 

// Determines if the queue is empty 
bool Que_Empty(Quetail* pq)
{
	assert(pq);
	return pq->head == NULL;
}

5. Find the header data of the queue ：

Determines if the queue is empty >> Return header data

// Find the header data of the queue 
Quetype Que_front(Quetail* pq)
{
	assert(pq);
	assert(!Que_Empty(pq));    // Determines if the queue is empty 
	return pq->head->data;     // Return header data 
}

6. system Count the length of the queue ：

It is to count the number of linked list nodes

int Que_size(Quetail* pq)
{
	assert(pq);
	int size;
	QueNode* pphead = pq->head;
	for (size = 0; pphead; pphead = pphead->Next, size++);
	return size;
}

7. Destruction of queues ：

   Delete data in turn >> Release the application space

  Minutiae ： Here you can reuse ： Determines if the queue is empty 、 Delete data

void Que_Destory(Quetail* pq)
{
	for (; !Que_Empty(pq); )  // Determines if the queue is empty 
	{
		Que_pop(pq);          // Delete data 
	}
}

  Thank you for your support ！！！