C language implements sequential queue, circular queue and chain queue

C The language implements sequential queues 、 Circular queues and chained queues

One . Sequential queue

The implementation of sequential queue is relatively simple , Use the array to store . Because this method is static storage , That is, once the memory size is specified, it cannot be changed , Therefore, overflow may occur , Therefore, it is not of great value in practical use . So I only do a simple implementation here , Realize the basic functions of entering and leaving the team, and judge whether the team is empty or full .

Definition of sequential queue

#define MaxSize 5 // Sequential queue uses sequential storage , Manually specify the maximum capacity  
typedef int ElemType;
//------  Structure definition  -------// 
typedef struct SqlQueue
{
    
	ElemType data[MaxSize];// Storing data in an array  
	int front,rear;// Team leader and team leader  
}SqlQ;

The initial state ( Team air condition )：Q->front == Q->rear == 0;

The team ： When the team is dissatisfied , First send the value to the end of the queue element , Then put the tail pointer +1;

Out of the team ： When the team is not empty , Take the value of the team head element first , Then put the team head pointer +1;

( Here, please refer to Wang Dao's postgraduate entrance examination textbook )

Sequence queue all codes

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h> // according to C99 standard ,C Language use bool Type needs to add this header file 
#define MaxSize 5 // Sequential queue uses sequential storage , Manually specify the maximum capacity  

typedef int ElemType;

//------  Structure definition  -------// 
typedef struct SqlQueue
{
    
	ElemType data[MaxSize];// Storing data in an array  
	int front,rear;// Team leader and team leader  
}SqlQ;
//------  Structure definition  -------// 

//---------  Function declaration  ---------// 
void MainMenu();// The main menu , Used for display  
void InitQueue(SqlQ *Q);// Initialization of the queue  
bool EnQueue(SqlQ *Q, ElemType e);	// The team  
bool DeQueue(SqlQ *Q, ElemType *x);// Out of the team 
bool GetFront(SqlQ *Q, ElemType *head);// Get team leader elements  
//---------  Function declaration  ---------// 

int main()
{
    
	SqlQ Q;// Declare a queue  
	InitQueue(&Q);// initialization  
	ElemType element;
	int ch; 
	ElemType x;// Get out of the team elements , Easy to return  
	ElemType head;// Get team leader elements  
	
	while(1)
	{
    
		MainMenu(); 
		printf(" Please enter the action you want to perform :");
		scanf("%d",&ch);
		
		switch(ch)
		{
    
			case 0:		printf(" Thank you for using , Exited ！");	exit(0);	break;
			case 1:		printf(" Please enter the element you want to join the team :\n");
						scanf("%d",&element); 
						if(EnQueue(&Q,element))
							printf(" Team success ！\n");
						else
							printf(" Team entry failure ！ The team is full ！\n");
						break;
			case 2:		
						if(DeQueue(&Q,&x))
							printf(" Team out success ！ The element of leaving the team is ：%d\n",x);
						else
							printf(" Failure to leave the team ！ The team is empty ！\n");
						break;		
			case 3:		
						if(GetFront(&Q,&head))
							printf(" Get the team head element successfully ！ The current team head element is :%d\n",head);
						else
							printf(" Failed to get queue header element ！ The team is empty ！\n");
						break; 
			default:	printf(" The operation instruction you entered is incorrect ！ Please re-enter ！");
		}
	}
	
	return 0;
}

// The main menu , Show  
void MainMenu()
{
    
	printf("\n\n\n");
	printf("\t ************* Implementation of sequential queue ************\n\n"); 
	printf("\t ------- 0. sign out  \n\n");
	printf("\t ------- 1. Queue data \n\n");
	printf("\t ------- 2. Perform an out of line operation \n\n");
	printf("\t ------- 3. Get the current team header element \n\n");
	printf("\t *************************************\n");
}


void InitQueue(SqlQ *Q)// Initialization of the queue 
{
    
	Q->front = Q->rear = 0;// Now the team is empty , Let the header pointer point to the header element , Let the tail pointer point to the next position of the tail element  
} 

// The team : When the team is dissatisfied , First send the value to the end of the queue element , Then put the tail pointer +1 
bool EnQueue(SqlQ *Q, ElemType e)
{
    
	if(Q->rear == MaxSize)
		return false;
	Q->data[Q->rear] = e;
	Q->rear++;
	return true;
}

// Out of the team : When the team is not empty , Take the value of the team head element first , Then put the team head pointer +1 
bool DeQueue(SqlQ *Q, ElemType *x)
{
    
	if(Q->front == Q->rear ) 
		return false;
	
	*x = Q->data[Q->front];
	Q->front++;
	return true;
} 

// Get the team leader element  
bool GetFront(SqlQ *Q, ElemType *head)
{
    
	if(Q->front == Q->rear) 
		return false;
	*head = Q->data[Q->front];
	return true;
}

test ：

️ Be careful ： This implementation will have some minor flaws , That is to say, when I have a full deposit and go out of the team in turn , here It's not a team in the real sense , Because no more elements can be queued . Of course, other methods can also be adopted , For example, modify the pointer , Then rejoin the team , Because this kind of sequential queue is not practical , So you only need to know the general process .

Two . Circular queue

The concept of circular queue

Circular queue is another implementation of sequential queue , Just think of the sequential queue as a ring . As shown in the figure below （ Refer to the data structure textbook of Wangdao postgraduate entrance examination ）：

When the head of the team Q->front = MaxSize - 1 after , One more position will automatically arrive 0, This can be done using division and remainder operations (%) To achieve . Therefore, there are the following situations ：

① At the beginning ：Q->front = Q->rear = 0;

② The leader of the team scored one ：Q->front = (Q->front+1)%MaxSize ;

③ At the end of the line, the pointer goes one ：Q->rear = (Q->rear+1)%MaxSize

When you go out and join the team , The pointer moves one clockwise .

Then the conditions for team empty and team full are Q->front == Q->rear . So in order to distinguish between empty and full teams , Yes 3 Treatment methods ：

1️⃣ Sacrifice a unit to distinguish between empty and full teams , Use one less queue unit when joining the team , This is a common practice , It is agreed that “ The head of the team pointer is at the next position of the tail of the team pointer as a sign that the team is full ”.

At this time there is :

Team full conditions ：(Q->rear+1)%MaxSize == Q->front

Team air condition ：Q->front == Q->rear

The queue length ：(Q->rear - Q->front + MaxSize) % MaxSize

2️⃣ Add a data member representing the number of elements in the type . such , The condition for the team to be empty is ：Q.size == 0; The condition of full team is Q.size == MaxSize. In both cases Q->front == Q->rear.

3️⃣ Added in type tag Data member , To distinguish whether the team is full or empty .tag be equal to 0 when , If... Is caused by deletion Q->front == Q->rear, The team is empty ; tag be equal to 1 when , If due to insertion Q->front == Q->rear The team is full .

Here I choose the second 2 Methods .

The relevant operation

1. initialization

void InitQueue(CirQ *Q)// Initialization of the queue 
{
    
	Q->front = Q->rear = 0;// Now the team is empty , Let the header pointer point to the header element , Let the tail pointer point to the next position of the tail element  
	Q->size = 0;// There are no elements stored at the beginning  
} 

2. The team

// The team 
bool EnQueue(CirQ *Q, ElemType e)
{
    
	// Determine if the queue is full 
	if(Q->size==MaxSize)
		return false;
	Q->data[Q->rear] = e; // Put values in  
	
	Q->rear = (Q->rear + 1)% MaxSize;// Change the pointer  
	Q->size++;// Number of elements in the queue +1 
	return true;
}

3. Out of the team

// Out of the team 
bool DeQueue(CirQ *Q, ElemType *x)
{
    
	if(Q->size == 0)// Determine whether the queue is empty 
		return false;
	*x = Q->data[Q->front];// Get out of line elements  
	Q->front = (Q->front + 1)% MaxSize; 
	Q->size--;// Number of elements in the queue -1 
	return true;
} 

4. Get team leader elements

// Get the team leader element  
bool GetFront(CirQ *Q, ElemType *head)
{
    
	if(Q->size == 0)// Determine whether the queue is empty 
		return false;
	*head = Q->data[Q->front];// Get the team leader  
	return true;
}

Loop queue full code

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h> // according to C99 standard ,C Language use bool Type needs to add this header file 
#define MaxSize 5 // Circular queues are stored sequentially , Manually specify the maximum capacity  

typedef int ElemType;

//------  Structure definition  -------// 
typedef struct CircularQueue
{
    
	ElemType data[MaxSize];// Storing data in an array  
	int front,rear;// Team leader and team leader  
	int size;// Indicates the number of actual storage in the queue  
}CirQ;
//------  Structure definition  -------// 

//---------  Function declaration  ---------// 
void MainMenu();// The main menu , Used for display  
void InitQueue(CirQ *Q);// Initialization of the queue  
bool EnQueue(CirQ *Q, ElemType e);	// The team  
bool DeQueue(CirQ *Q, ElemType *x);// Out of the team 
bool GetFront(CirQ *Q, ElemType *head);// Get team leader elements  
//---------  Function declaration  ---------// 

int main()
{
    
	CirQ Q;// Declare a queue  
	InitQueue(&Q);// initialization  
	ElemType element;
	int ch; 
	ElemType x;// Get out of the team elements , Easy to return  
	ElemType head;// Get team leader elements  
	
	while(1)
	{
    
		MainMenu(); 
		printf(" Please enter the action you want to perform :");
		scanf("%d",&ch);
		
		switch(ch)
		{
    
			case 0:		printf(" Thank you for using , Exited ！");	exit(0);	break;
			case 1:		printf(" Please enter the element you want to join the team :\n");
						scanf("%d",&element); 
						if(EnQueue(&Q,element))
							printf(" Team success ！\n");
						else
							printf(" Team entry failure ！ The team is full ！\n");
						break;
			case 2:		
						if(DeQueue(&Q,&x))
							printf(" Team out success ！ The element of leaving the team is ：%d\n",x);
						else
							printf(" Failure to leave the team ！ The team is empty ！\n");
						break;		
			case 3:		
						if(GetFront(&Q,&head))
							printf(" Get the team head element successfully ！ The current team head element is :%d\n",head);
						else
							printf(" Failed to get queue header element ！ The team is empty ！\n");
						break; 
			default:	printf(" The operation instruction you entered is incorrect ！ Please re-enter ！");
		}
	}
	
	return 0;
}

// The main menu , Show  
void MainMenu()
{
    
	printf("\n\n\n");
	printf("\t ************* Implementation of circular queue ************\n\n"); 
	printf("\t ------- 0. sign out  \n\n"); 
	printf("\t ------- 1. Queue data \n\n");
	printf("\t ------- 2. Perform an out of line operation \n\n");
	printf("\t ------- 3. Get the current team header element \n\n");
	printf("\t *************************************\n");
}


void InitQueue(CirQ *Q)// Initialization of the queue 
{
    
	Q->front = Q->rear = 0;// Now the team is empty , Let the header pointer point to the header element , Let the tail pointer point to the next position of the tail element  
	Q->size = 0;// There are no elements stored at the beginning  
} 

// The team 
bool EnQueue(CirQ *Q, ElemType e)
{
    
	// Determine if the queue is full 
	if(Q->size==MaxSize)
		return false;
	Q->data[Q->rear] = e; // Put values in  
	
	Q->rear = (Q->rear + 1)% MaxSize;// Change the pointer  
	Q->size++;// Number of elements in the queue +1 
	return true;
}

// Out of the team 
bool DeQueue(CirQ *Q, ElemType *x)
{
    
	if(Q->size == 0)// Determine whether the queue is empty 
		return false;
	*x = Q->data[Q->front];// Get out of line elements  
	Q->front = (Q->front + 1)% MaxSize; 
	Q->size--;// Number of elements in the queue -1 
	return true;
} 

// Get the team leader element  
bool GetFront(CirQ *Q, ElemType *head)
{
    
	if(Q->size == 0)// Determine whether the queue is empty 
		return false;
	*head = Q->data[Q->front];// Get the team leader  
	return true;
}

test ：

3、 ... and . Chain queues （ Leading node ）

The chain queue with chain storage is actually a single linked list with both the head pointer and the tail pointer , And follow the characteristics that the queue only goes out at the head of the queue and enters at the end of the queue .

Storage type definition

typedef struct Node
{
    
	ElemType data;
	struct LinkNode *next;// The subsequent pointer of the node  
}LinkNode;

// Chain queue  
typedef struct 
{
    
	LinkNode *front,*rear;// The head and tail pointers of the queue  
	int len;// Number of elements in the chain queue  
}LinkQueue;

Above , Two structures are defined , One is the node , One is the queue .

The team

// The team  
bool EnQueue(LinkQueue *Q, ElemType e)
{
    
	// First apply for a node 
	LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
	s->data = e;// Put the elements to be queued into the node 
	s->next = NULL;// Because at the end of the team , So it doesn't point to any element 
	
	// Modify the tail pointer 
	Q->rear->next = s;
	Q->rear = s; // Because the end of the queue pointer has been specified to point to the last node  
	
	Q->len++;
	
	return true;
}

When you join the team , You need to apply for a node first , Then insert this node into the end of the queue .

Out of the team

// Out of the team  
bool DeQueue(LinkQueue *Q, ElemType *x)
{
    
	if(Q->len==0)// If the number of elements in the queue is 0, Description is empty 
		return false;
	
	LinkNode *p = Q->front->next;// Points to the next node of the head node 
	
	// Get the value of the extracted team element first 
	*x = p->data;
	// Then modify the pointer 
	Q->front->next = p->next;
	
	if(Q->rear==p)// If there is only one node left in the queue , Empty after deletion 
		Q->rear = Q->front;
	free(p); 
	Q->len--;
	return true; 
}

When the team , Delete elements at the head of the team .

Chain queue all codes

Because of aesthetic fatigue , I changed the font to healthy green . Reference article ：https://blog.csdn.net/qq_31975227/article/details/51758461

#include<stdio.h>
#include <windows.h>
#include<stdbool.h> // according to C99 standard ,C Language use bool Type needs to add this header file 
#include<stdlib.h>

typedef int ElemType;

typedef struct Node
{
    
	ElemType data;
	struct LinkNode *next;// The subsequent pointer of the node  
}LinkNode;

// Chain queue  
typedef struct 
{
    
	LinkNode *front,*rear;// The head and tail pointers of the queue  
	int len;// Number of elements in the chain queue  
}LinkQueue;

//---------  Function declaration  ----------//
void MainMenu();
void color(short x);
void InitQueue(LinkQueue *Q);// Initialization of the queue  
bool EnQueue(LinkQueue *Q, ElemType e);	// The team  
bool DeQueue(LinkQueue *Q, ElemType *x);// Out of the team 
bool GetFront(LinkQueue *Q, ElemType *head);// Get team leader elements 
//---------  Function declaration  ----------//

int main()
{
    
	int ch;
	ElemType element,head,x;
	
	LinkQueue Q;// Create a chain queue  
	InitQueue(&Q); 
	while(1)
	{
    
		MainMenu(); 
		printf(" Please enter the action you want to perform :");
		scanf("%d",&ch);
		
		switch(ch)
		{
    
			case 0:		printf(" Thank you for using , Exited ！");	exit(0);	break;
			case 1:		printf(" Please enter the element you want to join the team :\n");
						scanf("%d",&element); 
						if(EnQueue(&Q,element))
							printf(" Team success ！\n");
						else
							printf(" Team entry failure ！\n");
						break;
			case 2:		
						if(DeQueue(&Q,&x))
							printf(" Team out success ！ The element of leaving the team is ：%d\n",x);
						else
							printf(" Failure to leave the team ！ The team is empty ！\n");
						break;		
			case 3:		
						if(GetFront(&Q,&head))
							printf(" Get the team head element successfully ！ The current team head element is :%d\n",head);
						else
							printf(" Failed to get queue header element ！ The team is empty ！\n");
						break; 
			default:	printf(" The operation instruction you entered is incorrect ！ Please re-enter ！");
		}
	}
	return 0;
} 

// The main menu , Show  
void MainMenu()
{
    
	color(2);// Set the font to green  
	printf("\n\n\n");
	printf("\t ************* The implementation of chain queue ************\n\n"); 
	printf("\t ------- 0. sign out  \n\n"); 
	printf("\t ------- 1. Queue data \n\n");
	printf("\t ------- 2. Perform an out of line operation \n\n");
	printf("\t ------- 3. Get the current team header element \n\n");
	printf("\t *************************************\n");
}


void color(short x)	// The custom function changes the color according to the parameters  
{
    
    if(x>=0 && x<=15)// Parameter in 0-15 Range color 
    	SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), x);	// There is only one parameter , Change font color  
    else// The default color is white 
    	SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7);
}

// initialization  
void InitQueue(LinkQueue *Q)
{
    
	// Apply for a head node space , And both the head pointer and the tail pointer are equal to it 
	Q->front = Q->rear = (LinkNode *)malloc(sizeof(LinkNode));
	Q->front->next = NULL;// The initial value of the header pointer next It's empty , Because the element has not been inserted yet  
	Q->len = 0;
} 

// The team  
bool EnQueue(LinkQueue *Q, ElemType e)
{
    
	// First apply for a node 
	LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
	s->data = e;// Put the elements to be queued into the node 
	s->next = NULL;// Because at the end of the team , So it doesn't point to any element 
	
	// Modify the tail pointer 
	Q->rear->next = s;
	Q->rear = s; // Because the end of the queue pointer has been specified to point to the last node  
	
	Q->len++;
	
	return true;
}

// Out of the team  
bool DeQueue(LinkQueue *Q, ElemType *x)
{
    
	if(Q->front==Q->rear)// If the number of elements in the queue is 0, Description is empty 
		return false;
	
	LinkNode *p = Q->front->next;// Points to the next node of the head node 
	
	// Get the value of the extracted team element first 
	*x = p->data;
	// Then modify the pointer 
	Q->front->next = p->next;
	
	if(Q->rear==p)// If there is only one node left in the queue , Empty after deletion 
		Q->rear = Q->front;
	free(p); 
	Q->len--;
	return true; 
}

// Get team leader elements  
bool GetFront(LinkQueue *Q, ElemType *head)
{
    
	if(Q->len==0)// If the number of elements in the queue is 0, Description is empty 
		return false;
	LinkNode *q = Q->front->next;// Points to the next node of the head node 
	*head = q->data;
 
	return true;
}

test ：

Reference material

Refer to the data structure textbook of Wangdao postgraduate entrance examination .