1. Characteristics of queues

Queue is a special finite data structure in linear structure, which has the following characteristics:

  • 1. Feature queues of linear structures are available. For feature queues of linear structures, see article # 01– Sequential storage of linear tables.
  • 2. The special limiting characteristics of the queue are:First in first out;
  • 3. The queue byTeam up in one direction.Out in one direction. We call the orientation of the teamA party, the direction of exitTeam head.

Second, queue sequential storage analysis

The following describes the design and implementation of queue in sequential storage, which is characterized by contiguous and limited memory. Combining the characteristics of queue and sequential storage, we analyze how queue achieves sequential storage.

Suppose we design a sequential array to hold the queue, as shown below:

  • 1. When the queue is empty, rear equals 0.
  • 2. Add C1, C2, and C3 to the team in sequence. In this case, front is 0, rear is 3;
  • 3. Remove C1 and C2 from the team. At this point, the front of the team moves to the position of 2, rear is 3;
  • 4. Put C4, C5, C6 into the team, then put C3, C4 out of the team, then the front of the team is 4, rear is 5.

Through the above operations, the final queue with the maximum length of 6 has valid data stored at positions 4 and 5, rear = 6-1 is 5, that is, the array is full, but positions 0 to 3 have no valid data stored. This situation is called the false overflow problem.

Circular queue

A circular queue can be used to solve the false overflow problem, as shown below:

  • 1. Initialize a queue. Rear equals 0.
  • 2. A, B and C enter the team, rear pointing to 3;
  • 3. A leaves the queue and the front of the queue points to 1.
  • 4. D, E, F, G enter the team. At this time, the front and rear point to the same position.

According to the above steps, when the team is empty and the team is full, the front and rear of the team are equal, so it is impossible to determine whether the team is empty or full. The solution to this problem is to always leave a space between the head of the queue and the back of the queue, sacrificing one storage unit, which does not affect the storage space of the queue much.

Through the above analysis, we can conclude as follows:

  • 1. Design oneCircular queueTo implement the queueSequential storage;
  • 2. Between the end of the line and the end of the line foreverFor a freeLocation, easy to judgeThe team is fullThe situation;
  • 3.Team is emptyThe judgment condition is the team leaderFront equals rear;
  • 4.The team is fullThe judgment condition of isTeam head rear + 1Pair array lengthMAXSIZEodieIs equal to theTeam head front;
  • 5.Circular queueThe realization of the team in the teamModify thePosition, to positionDie toThe length of the arrayMAXSIZE, can ensure the effective use of storage space, will not appearFalse overflowIs a problem.

Fourth, the design of the circular queue

1. Preparation

Define some state values and type redefinitions

#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 20 */ typedef int Status; typedef int QElemType; /* QElemType The QElemType type depends on the actual situation. Here, int */ is assumedCopy the code

The queue design

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
  • 1. Design a structure, data array is the sequential storage space of the queue;
  • 2. The frontTeam head, rearA party.

1. Initialization

Status InitQueue(SqQueue *Q){
    Q->front = 0;
    Q->rear = 0;

    return OK;
}
Copy the code

In the initial state of the queue, the queue is empty, and front and rear point to the same position 0.

2, empty

Status ClearQueue(SqQueue *Q){
    Q->front = Q->rear = 0;

    return OK;
}
Copy the code

When the queue is empty: Front equals rear equals 0.

3. Queue emptying

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

The condition of the queue is: front equals rear equals 0.

4. Length of queue

int QueueLength(SqQueue Q){

    return (Q.rear - Q.front + MAXSIZE)%MAXSIZE;

}
Copy the code

Since it is a circular order, rear at the end of the queue may be larger or smaller than front at the head, so rear-front+MAXSIZE is required.

5. Obtain team head data

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

Front points to the head of the queue. Fetch the data directly from the front of the data.

6. The team

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
  • 1.The team is fullJudgment conditions of:(rear+1) %MAXSIZE == front;
  • 2. There is no valid data for the position pointing to the end of the team, so when joining the team, you can assign a value to the rear position first, and then set the rear+1.
  • 3. Because it isCirculation order teamSo the rear rear plus one is going toDie toMAXSIZE.

7. Out of the team

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
  • 1. The queueSentenced to emptyThe conditions of the:front == rear;
  • 2. The position of the queue head has valid data, so it can be directly evaluated.
  • 3. When leaving the team, the head of the team should be close to the tail of the team, so the head and tail of the team should move in the same direction;
  • 4. Because it isCircular queue“So team leaderfront+1He wanted to be whenDie toMAXSIZE.

8. Traverse the queue data

Status QueueTraverse(SqQueue Q){ int i; i = Q.front; while ((i+Q.front) ! = Q.rear) { printf("%d ",Q.data[i]); i = (i+1)%MAXSIZE; } printf("\n"); return OK; }Copy the code
  • 1. From the head of the team to the end of the team;
  • 2. Because it is traversal, soCan'tchange-of-queueThe originalStructure, so we’re going to use a temporary variable I to add up from the head of the queue to the end of the queuei+front == rear;
  • 3. Pay attention toCircular queueAfter the position is changedDie toMAXSIZE, to prevent arrays from going out of bounds.

Five, the summary

In order to realize queue storage, attention should be paid to the problem of false overflow and queue full judgment. The solution is to use a circular queue and leave a position between the head and tail of queue to facilitate queue full judgment. Full and empty teams are judged as follows:

  • 1. rear == front;
  • (rear + 1)%MAXSIZE = front.

Because it’s a circular queue, when rear and front change, you want MAXSIZE to get the correct direction.