Queue storage and circular queue

One 、 The storage structure of the queue

1、 The physical storage of queues can be in a sequential storage structure , Chain storage structure can also be used . The storage methods of corresponding queues are also divided into two types , namely Sequential and chained queues .

2、 Sequential queues can be represented by one-dimensional arrays as follows ：

#define MAXQSIZE 100 // Maximum queue length

Typedef struct {

QElemType *base; // Initialize the dynamic allocation of storage space

int front; // The head pointer

int rear; // Tail pointer

}SqQueue;

Two 、 Basic operation statement of circular queue

1、 Initial of queue ：front=rear=0;

2、 Element entry ：base[rear]=x; rear++;

3、 Element queue ：x=base[front];front++;

4、 Air force sign ：front==rear;

5、 The team is full ： In order to prevent the team full sign from being the same as the team empty sign , It will use one less element space , That is, the queue space size is m when , Yes m-1 The first element is considered to be the team full . In this way, the conditions for judging the team empty remain the same , Immediate leadership 、 When the value of the tail pointer is the same , The team thinks it's empty ; When the tail pointer adds... In the sense of loop 1 Followed by a pointer equal to the head , Think the team is full . therefore , The condition for a full queue in a circular queue is :(rear+1)%MAXQSIZE==front.

3、 ... and 、 False overflow of sequential queue

1、 Definition ： The array storage area used by the system as a queue is not full yet , But the queue overflowed , We call this phenomenon " False spillover ".

2、 reason ： Because when the elements join the team The head pointer When the element moves forward and out of the queue, the tail pointer also moves forward , When the head pointer is out of vector space , At this time, the whole vector space and queue are not full, but " Overflow " The phenomenon .

3、 resolvent ： Think of team space as a circular table , I.e. assigned to the queue m Storage units can be recycled , When rear by maxqsize when , If the beginning of the vector is empty , You can use the empty space from the beginning . When front by maxqsize when , Is the same .

Four 、 Circular alignment

1、 Storage mode of circular queue ：base[0] Connect to base[MAXQSIZE -1] after , if rear+1==M, Then order rear=0;

2、 Loop queue insert elements and delete

① Insert elements : Q.base[Q.rear]=x;

                Q.rear= (Q.rear+ 1)% MAXQSIZE;

② Remove elements : x= Q.base[s.front]

                Q.front=(Q.front+ 1)% MAXQSIZE