Queue operation---

queue

queue , It is also a sequential storage structure , Its basic operation ： Additions and deletions , Sentenced to empty , Full contract operation

1. initialization

#include<stdio.h>
#define Maxsize 10 // The maximum number of elements in the stack 
typedef struct{
    
ElemType data[Maxsize];  // Static array elements 
int front,rear;          // Team head pointer and team tail pointer 

}SqQueue;

void InitQueue(SqQueue &Q){
    
         // initialization   The pointer at the head and tail of the team points to 0
   Q.front=Q.rear=0;

}

void testQueue{
    
    Queue Q;  // Declare a queue , Allocate space for it 
    // Follow up operation 
    InitStack(Q);
}

2. Empty operation （ The head pointer equals the tail pointer ）

bool QueueEmpty(SqQueue Q){
    
    if(Q.front==Q.rear)
        return true;     // Team space 
    else
        return false;
}

3. Joining operation

bool EnQueue(SqQueue &Q,ElemType x){
    
    if((Q.rear+1)%MaxSize==Q.front)   // Judge that the team is full   Not at all  Q.rear==Q.front , One unit must be sacrificed 
        return false;   
    Q.data[Q.rear]=x; // take x Insert the line 
    Q.rear=(Q.rear+1)%Maxsize;   // Move the pointer back at the end of the line 
    return true;
}

4. Out of line operation

bool DeQueue(SqQueue &Q,ElemType &x){
    
    if(Q.rear==Q.front)
        return false;   // The team reported an error  
    x=Q.data[Q.front]; // Take out the deleted value 
    Q.front=(Q.front+1)%Maxsize;   // The team leader pointer changes  
    return true;
}

The change of the operation pointer of leaving and entering the team is the same
Q.rear=(Q.rear+1)%Maxsize
Q.front=(Q.front+1)%Maxsize
5. Get the value of the team head element

bool GetHead(SqQueue &Q,ElemType &x){
    
    if(Q.rear==Q.front)
            return false;   // The team reported an error  
    x=Q.data[Q.front];    // Directly output the value of the team head element 
    return true;
}

If you don't sacrifice a space What shall I do? ？？
Method 2
use size Record the current length of the queue , On initialization size=0;
Insert the success size++
Delete successful size–
size=Maxsize Full for the team
size=0 Empty for team

typedef struct{
    
ElemType data[Maxsize];  // Static array elements 
int front,rear;          // Team head pointer and team tail pointer 
int size;           // Current queue length 

}SqQueue;

Method 3
Put a tag To record the recent deletion and insertion , Such as
Every time the deletion succeeds , Make tag=0;
Every time the insertion succeeds , Make tag=1;
The judging team is full of ：if（Q.frontQ.rear &&tag1）
Judge whether the team is empty ：if（Q.frontQ.rear &&tag====0）

typedef struct{
    
ElemType data[Maxsize];  // Static array elements 
int front,rear;          // Team head pointer and team tail pointer 
int tag;           // Recently deleted or inserted 

}SqQueue;

6. Determine the number of elements in the queue

Number of queue elements =(rear+MaxSize-front)%MaxSize

One more ： If rear When the pointer points to the tail element , The time to join the team is
Q.rear=(Q.rear+1)%Maxsize;
Q.data[Q.rear]=x;

At this time, the initial pointer is

Judge team empty ：(Q.rear+1)%Maxsize==Q.front;
The team is full ：

Sacrifice storage units or add auxiliary variables