The characteristics of queues and the implementation of sequential storage have been introduced in # 06- Sequential implementation of queues. This article will start with the design of chained storage for queues.

First, the chain implementation design of the queue

Characteristics of queues:

  • 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.

Let’s design a chained implementation of queues combining queue and characteristics with the properties of chained storage.

Second, preparation

Design some callback state 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

3. Design of nodes

Here we choose a one-way list to implement the chained implementation of the queue. The node design is as follows:

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

Data represents the data field, and next is the pointer field, pointing to the next node.

According to the characteristics of unidirectional lists and queues (see # 01– unidirectional lists for the characteristics of unidirectional lists), we design the following structure as a chained implementation of queues:

Typedef struct /* QueuePtr front,rear; }LinkQueue;Copy the code

Front at the head of the team, rear at the back.

Queue operations

Queue operations include initializing the queue, destroying the queue, emptying the queue, emptying the queue, getting the queue length, joining the queue, dequeuing, getting the queue head element, and traversing the queue.

1. Initialize the queue

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
  • 1. Design oneThe first nodeAs a queueIs emptyAt the head of the line and the back of the lineUnified point toSee the article on the benefits of designing headers in linked lists# 01– One-way linked lists;
  • 2. The queueIs emptyWhen,Team headThe front andA partyRear point toThe same location, i.e.,The first nodeWhen there is only a header, its next points to NULL;
  • 3.The head of the team is the position out of the team.At the end of the line is the position to join the team, it points toThe first nodeThe next of the header points toThe nextNode. As shown below:

  • 1. According to the design as above, whenThe teamYou just need to create a new nodeInsert behind rearCan;
  • 2.Out of the teamWhen you get frontnextNode A, then take the next node of A, namely node B, release node A, and then point the front next to B to achieve the team.

2. Destroy the queue

While (Q->front) {Q->rear = Q->front->next; free(Q->front); Q->front = Q->rear; } return OK; }Copy the code
  • 1. When the queue is destroyed, front and rear at the front and rear at the back of the queue no longer exist, so they can be regarded asAuxiliary spaceUse;
  • 2. When the queue is destroyed,The first nodeThere’s no need for it to exist, so you can go from the beginning node to the last node, and release them in turn;
  • 3. Front points to the head node, and rear points to the next node of the node to be deleted as the auxiliary space to facilitate the next deletion.

3. Clear the queue

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
  • 1. When clearing a queue,The first nodeNeed to bekeepTo facilitate the next team entry;
  • 2. If the queue is empty,A partyRear andTeam headThe front toThe same location, which is the header;
  • 3. If the queue is empty,Team head nextPointing toNULL;
  • 4. Take all nodes behind the head of the queue, iterate and release them.

4. Queue emptying

Status QueueEmpty(LinkQueue Q){

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

When the queue is empty, the front rear points to the same position.

5. Obtain the queue length

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
  • From 1.Team head frontNext traverses toA party, add 1 each time to get the length of the queue.
  • 2. You can also add the length of the queue when designing the structure of the queuelength, when performing operations such as queue entry, queue exit, and queue clearingModify theThe value of length.

6. The team

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
  • 1. Queue chain implementation when joining queueDon't need to full;
  • 2. Create a node and add the new node to the end of the queue becauseA partyIn a one-way linked listThe last oneNode, so the new node inserted into the queue becomesThe new party, soThe new nodeThe next point toNULL;
  • 3. The new nodeThe teamAfter, remember willOf the rearPoint to theThe new node.

7. Out of the team

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
  • 1. Check whether the queue is in a queueIs empty, for the time not out of the team;
  • 2. Team headfrontPoint to theThe first node, of the headernextqueue-pointingThe first oneValid data;
  • 3. You need it before you leaveNode to be deletedAnd the node to be deletedThe nextNode, delete the node to be deleted, willThe first nodeNext points to the deleted nodeThe nextNode;
  • 4. IfdeleteThe node isA party, and need to beOf the rearPoint to theTeam head front.

8. Get the header element

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
  • 1. To obtainTeam headData when neededSentenced to empty;
  • 2. Because the head of the line is pointing toThe first node, so getTeam head dataWhat you should get isfront->nextThe data.

9. Traverse the queue

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

Queue traversal is the same as one-way linked list traversal, starting at next, the head of the queue, and ending when next points to NULL.

Five, the summary

The realization of queue chain storage uses the data structure of one-way linked list, and cleverly designed a head node, the head of the queue front to the head node, convenient queue; The rear of the team points to the last node of the one-way linked list, which is convenient for joining the team.