# queue

### What is a queueFirst come first come“Queue” “queue” “queue” “queue” “queue” “queue” “queue” “queue” “queue” “queue” “queue” “queue” “queue” “queue” Two basic operations on queues:The teamPut a data to the end of the queue;Out of the teamRetrieves an element from the head of the queue. A queue is another oneOperation-constrained linear table data structuresIt has a first-in, first-out feature that allows elements to be inserted at the end of the queue and deleted at the head of the queue. The concept of queues is easy to understand, and the application of queues is very wide, such as: circular queue, blocking queue, concurrent queue, priority queue, etc. ### sequence pairs### loop columns• When rear==front==0, the pairs are empty • C1, C2, and C3 are in pairs (from rear), front is not moving • C1, C2 are in pairs (from front), rear is not moving • C3, C4, C5 are in pairs c3, C4, and C5 are in pairs If the judge rear = = front at this time Is full of column, but actual column is not full, can cause the false All put forward the circular queue is equivalent to a circle, the array can imagine into a straight line, we let the line break into a circle, is the circular queue, in order to more image, says we can see pictured belowAs shown in the figure above, the size of the queue is size = 11, the head of the queue points to 5, and the end of the queue fail points to 10. When an element F is added to the end of the queue, fail = 0; when another element G is added to the end of the queue, fail = 1. The queue will look like the following figureThe difficulty of circular queue is how to determine the conditions of empty queue and full queue and the changes of HEAD and FAIL. So to summarize the rule, the change in fail, when fail=10, how do you make fail= 0? Fail = (fail+1)%size; Head =(head+1)%size.

How to determine the full line? If (fail+1)%size == head, the queue will be full. However, there is no data in the position pointed to by FAIL. This means that the circular queue wasted a storage space and traded space for time

So in order to determine whether the queue is full, a blank position is left blank. Q.ear == q.ear Determine the queue is full. (q.ear + 1) % MAXSIZE == q.ear ##### The sequential storage structure of the circular queue

typedef int Status; typedef int QElemType; /* the QElemType type depends on the actual situation, where the type is int */ /* the sequential storage structure of the loop queue */ typedef struct {QElemType data[MAXSIZE]; int front; /* header pointer */ int rear; /* the last pointer to the last element of the queue, if not empty */}SqQueue;Copy the code

##### loop initializes column sequential storage

Status InitQueue(SqQueue *Q){
    Q->front = 0;
    Q->rear = 0;
    return OK;
}
Copy the code

##### Loop column sequence storage is cleared

Status ClearQueue(SqQueue *Q){
    
    Q->front = Q->rear = 0;
    return OK;
}
Copy the code

##### loop nulls the sequential storage of columns

Status QueueEmpty(SqQueue Q){// QueueEmpty if (q.front == q.ear) return TRUE; else return FALSE; }Copy the code

##### The length of the sequential storage of the circular pair columns

int QueueLength(SqQueue Q){
    return (Q.rear - Q.front + MAXSIZE)%MAXSIZE;
}
Copy the code

##### The element that the loop stores sequentially for the column

Status GetHead(SqQueue Q,QElemType *e){// The queue is empty if (q.front == q.ear) return ERROR; *e = Q.data[Q.front]; return OK; }Copy the code

##### loop columns store the enqueued elements sequentially

Status EnQueue(SqQueue *Q,QElemType e){// Queue is full if((Q->rear+1)%MAXSIZE == Q->front) return ERROR; // Assign element e to queue end Q->data[Q->rear] = e; // Rear moves the pointer back one bit, to the array header; Q->rear = (Q->rear+1)%MAXSIZE; return OK; }Copy the code

##### loop pairs store pairs sequentially

Status DeQueue(SqQueue *Q,QElemType *e){if (Q->front == Q->rear) {return ERROR; } // assign the header element to e *e = Q->data[Q->front]; Q->front = (Q->front+1)%MAXSIZE; return OK; }Copy the code

##### loop for sequential storage traversal of columns

Status QueueTraverse(SqQueue Q){ int i; i = Q.front; while ((i+Q.front) ! = Q.rear) { printf("%d ",Q.data[i]); i = (i+1)%MAXSIZE; } /* while ((i+Q.front)%MAXSIZE ! = Q.rear) { printf("%d ",Q.data[(i+Q.front)%MAXSIZE]); i = (i+1)%MAXSIZE; } */ printf("\n"); return OK; }Copy the code

### chain alignment##### pin-chain storage node structure

Typedef struct QNode */ {QElemType data; struct QNode *next; }QNode,*QueuePtr; Typedef struct /* QueuePtr front,rear; }LinkQueue;Copy the code

##### initializes chained storage

Status InitQueue(LinkQueue *Q){ //1. Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode)); // create a new node if (! Q->front) { return ERROR; } //3. Q->front->next = NULL; return OK; }Copy the code

##### collaterally linked storage destroys collaterals

While (Q->front) {Q->rear = Q->front->next; free(Q->front); Q->front = Q->rear; } return OK; }Copy the code

##### empty the chained storage

Status ClearQueue(LinkQueue *Q){
    
    QueuePtr p,q;
    Q->rear = Q->front;
    p = Q->front->next;
    Q->front->next = NULL;
    
    while (p) {
        
        q = p;
        p = p->next;
        free(q);
        
    }
    
    return OK;
}
Copy the code

##### nullity of chained storage

Status QueueEmpty(LinkQueue Q){
    if (Q.front == Q.rear)
        return TRUE;
    else
        return FALSE;
}
Copy the code

##### Length of pair-chain storage

int QueueLength(LinkQueue Q){ int i= 0; QueuePtr p; p = Q.front; while (Q.rear ! = p) { i++; p = p->next; } return i; }Copy the code

##### join the queue for chained storage

Status EnQueue(LinkQueue *Q,QElemType e){ QueuePtr s = (QueuePtr)malloc(sizeof(QNode)); If (! s) { return ERROR; } // add a new node (s) to the data field. s->next = NULL; Q->rear->next = s; // change the queue pointer Q->rear = s; return OK; }Copy the code

##### pair chain store pair

Status DeQueue(LinkQueue *Q,QElemType *e){ QueuePtr p; // Check whether the queue is empty; if (Q->front == Q->rear) { return ERROR; } p p = Q->front->next; E *e = p->data; Q->front->next = p->next; If (Q->rear == p) Q->rear = Q->front; free(p); return OK; }Copy the code

##### stores header elements in pairs

Status GetHead(LinkQueue Q,QElemType *e){// The queue is not empty if (q.field! *e = q.front ->next->data; return TRUE; } return FALSE; }Copy the code

##### chain storage traversal

Status QueueTraverse(LinkQueue Q){
    
    QueuePtr p;
    p = Q.front->next;
    while (p) {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}
Copy the code

[demo](